Possible and Necessary Winners of Partial Tournaments

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

JAIR 2015 pp. 493-534

doi:10.1613/JAIR.4856 /jair/2015/aziz2015jair-possible/

Abstract

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.

PDF JAIR Semantic Scholar

Cite

Text

Aziz et al. "Possible and Necessary Winners of Partial Tournaments." Journal of Artificial Intelligence Research, 2015. doi:10.1613/JAIR.4856

Markdown

[Aziz et al. "Possible and Necessary Winners of Partial Tournaments." Journal of Artificial Intelligence Research, 2015.](https://mlanthology.org/jair/2015/aziz2015jair-possible/) doi:10.1613/JAIR.4856

BibTeX

@article{aziz2015jair-possible,
  title     = {{Possible and Necessary Winners of Partial Tournaments}},
  author    = {Aziz, Haris and Brill, Markus and Fischer, Felix A. and Harrenstein, Paul and Lang, Jérôme and Seedig, Hans Georg},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2015},
  pages     = {493-534},
  doi       = {10.1613/JAIR.4856},
  volume    = {54},
  url       = {https://mlanthology.org/jair/2015/aziz2015jair-possible/}
}