Journal article

Possible and necessary winners of partial tournaments

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.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Aziz, H., Brill, M., Fischer, F., Harrenstein, B., Lang, J., & Seedig, H. G. (2016). Possible and necessary winners of partial tournaments. Journal of Artificial Intelligence Research, 54, 493–534.

MLA Style

Aziz, H., et al. “Possible and Necessary Winners of Partial Tournaments.” Journal of Artificial Intelligence Research, vol. 54, Association for the Advancement of Artificial Intelligence, 2016, pp. 493–534.

Chicago Style

Aziz, H, M Brill, F Fischer, B Harrenstein, J Lang, and HG Seedig. 2016. “Possible and Necessary Winners of Partial Tournaments.” Journal of Artificial Intelligence Research 54: 493–534.
Share
Print

Access Document

Files:: Aziz_et_al_2015_Possible_and_necessary.pdf

(Preview, Version of record, pdf, 487.4KB, Terms of use)

Publisher copy:: 10.1613/jair.4856

Authors

+ Aziz, H More by this author

Role:: Author

+ Brill, M More by this author

Role:: Author

+ Fischer, F More by this author

Role:: Author

+ Harrenstein, B More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Role:: Author

+ Lang, J More by this author

Role:: Author

More authors...

+ European Research Council More from this funder

Funder identifier:: https://ror.org/0472cxd90
Grant:: 291528

+ Deutsche Forschungsgemeinschaft More from this funder

Funder identifier:: https://ror.org/018mejw64
Grant:: FI 1664/1-1

+ Australian Research Council More from this funder

Funder identifier:: https://ror.org/05mmh0f86

+ Alexander von Humboldt Foundation More from this funder

Funder identifier:: https://ror.org/012kf4317

+ Agence Nationale de la Recherche More from this funder

Funder identifier:: https://ror.org/00rbzpz17

More funders...

Publisher:: Association for the Advancement of Artificial Intelligence
Journal:: Journal of Artificial Intelligence Research More from this journal
Volume:: 54
Pages:: 493-534
Publication date:: 2016-12-16
DOI:: 10.1613/jair.4856
ISSN:: 1943-5037

Language:: English
Pubs id:: pubs:591930
UUID:: uuid:659a9612-c220-4742-9093-b4ab38282d27
Local pid:: pubs:591930
Source identifiers:: 591930
Deposit date:: 2016-01-20

Terms of use

Copyright holder:: AI Access Foundation
Copyright date:: 2015
Rights statement:: © 2015 AI Access Foundation. All rights reserved

Licence:: Other

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP