Minimal retentive sets in tournaments

Felix Brandt, Markus Brill, Felix A. Fischer, Paul HarrensteinAAMAS 2010 · OpenReview

Abstract

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 any given tournament solution S, there is another tournament solution S, which returns the union of all inclusion-minimal sets that satisfy S-retentiveness, a natural stability criterion with respect to S. Schwartz's tournament equilibrium set (TEQ) is then defined as TEQ = TEQ. Due to this unwieldy recursive definition, preciously little is known about TEQ. Contingent on a well-known conjecture about TEQ, we show that S inherits a number of important and desirable properties from S. We thus obtain an infinite hierarchy of attractive and efficiently computable tournament solutions that "approximate" TEQ, which itself is intractable. This hierarchy contains well-known tournament solutions such as the top cycle (TC) and the minimal covering set (MC). We further prove a weaker version of the conjecture mentioned above, which establishes TC as an attractive new tournament solution.
BibTeX
@inproceedings{brandt2010minimal,
  author = {Felix Brandt and Markus Brill and Felix A. Fischer and Paul Harrenstein},
  title = {{Minimal retentive sets in tournaments}},
  booktitle = {AAMAS},
  year = {2010},
  url = {https://openreview.net/forum?id=fjTJ6twtIp},
}

Loading related content...

Figure