Links und Funktionen

Sie sind hier: Startseite / Lehre / WS 2009/10 / Oberseminar / Paul Harrenstein: Minimal Retentive Sets in Tournaments


Paul Harrenstein: Minimal Retentive Sets in Tournaments

18.12.2009 14:15
Wann 14:15 15:45 18.12.2009
von bis
Wo Z1.09 (neu: L109)
Termin übernehmen vCal

Many problems in multiagent decision making can be addressed using tournament solutions, i.e., functions that associate with each complete and asymmetric relation on a set of alternatives a non-empty subset of the alternatives.  For a given tournament solution S, Schwartz calls a set of alternatives S-retentive if it satisfies a natural stability criterion with respect to S.  He then recursively defines the tournament equilibrium set (TEQ) as the union of all inclusion-minimal TEQ-retentive sets. This idea can be generalized to any tournament solution S. Accordingly, we define for each tournament solution S, S-ring as the union of all inclusion-minimal S-retentive sets. Assuming a well-known conjecture about TEQ, we show that most desirable properties of tournament solutions are inherited from S to S-ring.  We thus obtain an infinite hierarchy of efficiently computable tournament solutions that ``approximate'' TEQ, which is computationally intractable, while maintaining most of its desirable properties. This hierarchy contains well-known tournament solutions such as the top cycle (TC) and the minimal covering set (MC). We prove a weaker version of the conjecture mentioned above, which establishes TC-ring as an attractive new tournament solution.

 (joint work with Felix Brandt, Markus Brill, and Felix Fischer)



abgelegt unter: