Paul Harrenstein: Minimal Retentive Sets in Tournaments

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)