The Library
Possible and necessary winners of partial tournaments
Tools
Aziz, Haris, Brill, Markus, Fischer, Felix, Harrenstein, Paul, Lang, Jerome and Seedig, Hans Georg (2015) Possible and necessary winners of partial tournaments. Journal of Artificial Intelligence Research, 54 . pp. 493-534. doi:10.1613/jair.4856 ISSN 1076-9757.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1613/jair.4856
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Journal of Artificial Intelligence Research | ||||
Publisher: | AAAI Press | ||||
ISSN: | 1076-9757 | ||||
Official Date: | 16 December 2015 | ||||
Dates: |
|
||||
Volume: | 54 | ||||
Page Range: | pp. 493-534 | ||||
DOI: | 10.1613/jair.4856 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |