Confirmed Talk
 

Olivier HUDRY

Title: Links between some tournament solutions

Abstract:

����� 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.