Possible and necessary winners of partial tournaments
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...
| Huvudupphovsmän: | , , , , , |
|---|---|
| Materialtyp: | Journal article |
| Publicerad: |
Association for the Advancement of Artificial Intelligence
2016
|
| _version_ | 1826276269216497664 |
|---|---|
| author | Harrenstein, B Brill, M Lang, J Aziz, H Fischer, F Seedig, H |
| author_facet | Harrenstein, B Brill, M Lang, J Aziz, H Fischer, F Seedig, H |
| author_sort | Harrenstein, B |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T23:11:25Z |
| format | Journal article |
| id | oxford-uuid:659a9612-c220-4742-9093-b4ab38282d27 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:11:25Z |
| publishDate | 2016 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:659a9612-c220-4742-9093-b4ab38282d272022-03-26T18:26:33ZPossible and necessary winners of partial tournamentsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:659a9612-c220-4742-9093-b4ab38282d27Symplectic Elements at OxfordAssociation for the Advancement of Artificial Intelligence2016Harrenstein, BBrill, MLang, JAziz, HFischer, FSeedig, HWe 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. |
| spellingShingle | Harrenstein, B Brill, M Lang, J Aziz, H Fischer, F Seedig, H Possible and necessary winners of partial tournaments |
| title | Possible and necessary winners of partial tournaments |
| title_full | Possible and necessary winners of partial tournaments |
| title_fullStr | Possible and necessary winners of partial tournaments |
| title_full_unstemmed | Possible and necessary winners of partial tournaments |
| title_short | Possible and necessary winners of partial tournaments |
| title_sort | possible and necessary winners of partial tournaments |
| work_keys_str_mv | AT harrensteinb possibleandnecessarywinnersofpartialtournaments AT brillm possibleandnecessarywinnersofpartialtournaments AT langj possibleandnecessarywinnersofpartialtournaments AT azizh possibleandnecessarywinnersofpartialtournaments AT fischerf possibleandnecessarywinnersofpartialtournaments AT seedigh possibleandnecessarywinnersofpartialtournaments |