"Computational Aspects of Covering in Dominance Graphs"

Speaker: Felix Fischer
Date: Thursday, 29 March 2007
Time: 11am
Place: Ross 201

Abstract:

Various problems in AI and multiagent systems can be tackled by
finding the "most desirable" elements of a set given some binary
relation.  Examples can be found in areas as diverse as voting theory,
game theory, and argumentation theory.  Some particularly attractive
solution sets are defined in terms of a covering relation---a
transitive subrelation of the original relation.  We consider three
different types of covering (upward, downward, and bidirectional) and
the corresponding solution concepts known as the uncovered set and the
minimal covering set.  We present the first polynomial-time algorithm
for finding the minimal bidirectional covering set (an acknowledged
open problem) and prove that finding a minimal upward or downward
covering set is NP-hard.  Furthermore, we obtain various
set-theoretical inclusions, which reveal a strong connection between
von Neumann-Morgenstern stable sets and upward covering on the one
hand, and the Banks set and downward covering on the other hand.

(joint work with Felix Brandt, see
http://www.tcs.ifi.lmu.de/~fischerf/publications/bf_covering.pdf)