Thumbnail

Possible and necessary winners of partial tournaments

Aziz, Haris; Harrenstein, Paul; Brill, Markus; Lang, Jérôme; Fischer, Felix; Seedig, Hans Georg (2012), Possible and necessary winners of partial tournaments, in Padgham, Lin; van der Hoek, Wiebe; Conitzer, Vincent; Winikoff, Michael, Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012) - Volume 2, IFAAMAS, p. 585-592

View/Open
Type
Communication / Conférence
Date
2012
Conference title
11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012)
Conference date
2012-06
Conference city
Valencia
Conference country
Spain
Book title
Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012) - Volume 2
Book author
Padgham, Lin; van der Hoek, Wiebe; Conitzer, Vincent; Winikoff, Michael
Publisher
IFAAMAS
ISBN
978-0-9817381-2-3
Number of pages
1508
Pages
585-592
Metadata
Show full item record
Author(s)
Aziz, Haris
Department of Informatics of the Technische Universität München
Harrenstein, Paul
Department of Informatics of the Technische Universität München
Brill, Markus
Department of Informatics of the Technische Universität München
Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Fischer, Felix
Université de Cambridge
Seedig, Hans Georg
Department of Informatics of the Technische Universität München
Abstract (EN)
We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.
Subjects / Keywords
Social Choice Theory; Tournament Solutions; Possible and Necessary Winners; Computational Complexity