Olivier HUDRY
Groupe Mathématiques de l'Informatique et des Réseaux
Equipe membre de l'URA 820 - CNRS
Télécom Paris (école nationale supérieure des télécommunications)
46, rue Barrault - 75634 Paris Cedex 13

Talk: Links Between Some Tournamente Solutions


Consider a competition organized in such a way that each competitor plays once against each one of the other competitors. If we assume that ties cannot occur, then the result of this pairwise comparison is a tournament T: the vertices of T are the competitors and there is an arc from x to y if x defeats y. Then, a "tournament solution" S can be defined as a way to choose, from the set X of vertices of any tournament T = (X, U), a subset S(X) of X whose elements can be considered as better than the others: the "winners" of T according to S. It may happen that, in the competition, there is a player (a vertex) who defeated all the other ones; such a player is called a "Condorcet Winner" and can (must?) reasonably be considered as the unique winner for any tournament solution S. But it may happen also that there is no Condorcet Winner in T. Then answering the question "who are the best players?" is no longer an easy task.       In this talk, we discuss the properties of and the links between several tournament solutions, namely: - the Copeland solution, based on the out-degrees of the vertices; - a solution based on the maximum eigenvalue of the matrix associated with the tournament; - a Markovian solution; - the Slater solution, based on linear orders at minimum distance; - the Banks solution, based on maximal transitive subtournaments; - the tournament equilibrium set (TEQ); - solutions based on covering relations.