Tournament Solutions and Their Applications to Multiagent Decision Making

Given a finite set of alternatives and choices between all pairs of alternatives, how to choose from the entire set in a way that is faithful to the pairwise comparisons? This simple, yet captivating, problem is studied in the literature on tournament solutions. A tournament solution thus seeks to identify the “best” elements according to some binary dominance relation, which is usually assumed to be asymmetric and complete. As the ordinary notion of maximality may return no elements due to cyclical dominations, numerous alternative solution concepts have been devised and axiomatized.

Many problems in multiagent decision making can be addressed using tournament solutions. For instance, tournament solutions play an important role in

collective decision-making

(social choice theory), where the binary relation is typically defined via pairwise majority voting. Other application areas include

adversarial decision-making

(theory of zero-sum games) and

coalitional decision-making

(cooperative game theory) as well as multi-criteria decision analysis and argumentation theory.

In this talk, I will present an overview of some of the most common tournament solutions such as the uncovered set, the minimal covering set, and the bipartisan set and analyze them from an algorithmic point of view.