Состоялось заседание научного семинара «Математическое моделирование» учебного плана ОПМИ (руководитель проф., д.т.н. Миркин Борис Григорьевич), совмещенное с внеочередным заседанием общемосковского семинара «Математические методы анализа решений в экономике, бизнесе и политике» (руководители Ф.Т.Алескеров, В.В. Подиновский и Б.Г. Миркин)

Olivier Hudry (ENST Paris France) - "Tournament solutions"

Аннотация доклада:

In voting theory, the result of a paired comparison method as the one suggested by Condorcet [1] can be represented by a tournament T, i.e., a complete asymmetric directed graph, when there is no tie. More precisely, the vertices of T are the candidates of the election, and there is a directed edge from x towards y when a majority of voters prefer x to y. When there is no Condorcet winner, i.e., a candidate preferred to any other candidate by a majority of voters, it is not always easy to decide who is the winner of the election. Different methods, called tournament solutions (see [3]), have been proposed to define the winners. They differ by their properties and usually lead to different winners. The aim of this talk is to depict these tournament solutions, to describe their properties and their relationships. Among these properties, we consider combinatorial aspects as well as some algorithmic ones. In particular, we consider the complexity of the most usual tournament solutions: some are polynomial, some are NP-hard (see [2]).

 Keywords: voting theory, majority tournament, Copeland solution, maximum likelihood, self-consistent choice rule, Markovian solution, uncovered set, minimal covering set, Banks solution, Slater solution, tournament equilibrium set, eigenvector solution, complexity.

Рабочий язык: английский

Текст доклада: Hudry 01.11.10.pdf

* Olivier Hudry http://perso.telecom-paristech.fr/~hudry/

Список публикаций http://en.scientificcommons.org/olivier_hudry