Possible and Necessary Winners of Partial Tournaments

Aziz, Haris; Brill, Markus; Fischer, Felix; Harrenstein, Paul; Lang, Jérôme; Seedig, Hans Georg

Aziz, Haris; Brill, Markus; Fischer, Felix; Harrenstein, Paul; Lang, Jérôme; Seedig, Hans Georg (2015), Possible and Necessary Winners of Partial Tournaments, The Journal of Artificial Intelligence Research, 54, p. 493-534. 10.1613/jair.4856

Type

Article accepté pour publication ou publié

Date

2015

Journal name

The Journal of Artificial Intelligence Research

Volume

Publisher

Morgan Kaufmann Publishers

Pages

493-534

Publication identifier

10.1613/jair.4856

Metadata

Show full item record

Author(s)

Aziz, Haris
University of South Wales
Brill, Markus

Fischer, Felix

Harrenstein, Paul
Oxford University
Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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

computational social choice