Felix Brandt
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.
- N. Alon. Ranking tournaments. SIAM Journal on Discrete Mathematics, 20(1):137--142, 2006. Google Scholar
Digital Library
- K. J. Arrow and H. Raynaud. Social Choice and Multicriterion Decision-Making. MIT Press, 1986.Google Scholar
- D. Bouyssou, T. Marchant, M. Pirlot, A. Tsoukiàs, and P. Vincke. Evaluation and Decision Models: Stepping Stones for the Analyst. Springer-Verlag, 2006.Google Scholar
- F. Brandt. Minimal stable sets in tournaments. Technical report, http://arxiv.org/abs/0803.2138, 2009. Presented at the 9th International Meeting of the Society of Social Choice and Welfare.Google Scholar
- F. Brandt and F. Fischer. Computing the minimal covering set. Mathematical Social Sciences, 56(2):254--268, 2008.Google ScholarCross Ref
- F. Brandt and P. Harrenstein. Characterization of dominance relations in finite coalitional games. Theory and Decision, 2009. Forthcoming.Google Scholar
- F. Brandt, F. Fischer, and P. Harrenstein. The computational complexity of choice sets. Mathematical Logic Quarterly, 55(4):444--459, 2009.Google ScholarCross Ref
- F. Brandt, F. Fischer, P. Harrenstein, and M. Mair. A computational analysis of the tournament equilibrium set. Social Choice and Welfare, 2009. Forthcoming.Google Scholar
- V. Conitzer. Computing Slater rankings using similarities among candidates. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI), pages 613--619. AAAI Press, 2006. Google ScholarDigital Library
- J. Duggan and M. Le Breton. Dutta's minimal covering set and Shapley's saddles. Journal of Economic Theory, 70:257--265, 1996.Google ScholarCross Ref
- P. M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence, 77:321--357, 1995. Google ScholarDigital Library
- P. E. Dunne. Computational properties of argumentation systems satisfying graph-theoretic constraints. Artificial Intelligence, 171(10--15):701--729, 2007. Google ScholarDigital Library
- B. Dutta. On the tournament equilibrium set. Social Choice and Welfare, 7(4):381--383, 1990.Google ScholarCross Ref
- D. C. Fisher and J. Ryan. Tournament games and positive tournaments. Journal of Graph Theory, 19(2):217--236, 1995. Google ScholarDigital Library
- I. J. Good. A note on Condorcet sets. Public Choice, 10:97--101, 1971.Google ScholarCross Ref
- N. Houy. Still more on the tournament equilibrium set. Social Choice and Welfare, 32:93--99, 2009.Google ScholarCross Ref
- N. Houy. A few new results on TEQ. Unpublished Manuscript, 2009.Google Scholar
- G. Laffond, J.-F. Laslier, and M. Le Breton. More on the tournament equilibrium set. Mathématiques et sciences humaines, 31(123):37--44, 1993.Google Scholar
- G. Laffond, J.-F. Laslier, and M. Le Breton. The bipartisan set of a tournament game. Games and Economic Behavior, 5:182--201, 1993.Google ScholarCross Ref
- G. Laffond, J. Lainé, and J.-F. Laslier. Composition-consistent tournament solutions and social choice functions. Social Choice and Welfare, 13:75--93, 1996.Google ScholarCross Ref
- J.-F. Laslier. Tournament Solutions and Majority Voting. Springer-Verlag, 1997.Google ScholarCross Ref
- H. Moulin. Choosing from a tournament. Social Choice and Welfare, 3:271--291, 1986.Google ScholarCross Ref
- H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.Google Scholar
- T. Schwartz. Cyclic tournaments and cooperative majority voting: A solution. Social Choice and Welfare, 7: 19--29, 1990.Google ScholarCross Ref
- G. J. Woeginger. Banks winners in tournaments are difficult to recognize. Social Choice and Welfare, 20: 523--528, 2003.Google ScholarCross Ref
Index Terms
- Minimal retentive sets in tournaments
Recommendations
Minimal extending sets in tournaments
AAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systemsIn 2011, Brandt proposed a new tournament solution called the minimal extending set (ME). It was conjectured that ME satisfies a large number of desirable properties. In this paper, we non-constructively show that ME fails to satisfy most of these ...
Bounds on the disparity and separation of tournament solutions
A tournament solution is a function that maps a tournament, i.e., a directed graph representing an asymmetric and connex relation on a finite set of alternatives, to a non-empty subset of the alternatives. Tournament solutions play an important role in ...
On the 3-kings and 4-kings in multipartite tournaments
Koh and Tan gave a sufficient condition for a 3-partite tournament to have at least one 3-king in [K.M. Koh, B.P. Tan, Kings in multipartite tournaments, Discrete Math. 147 (1995) 171-183, Theorem 2]. In Theorem 1 of this paper, we extend this result to ...
Comments