Abstract | ||
---|---|---|
Given the preferences of several agents over a common set of candidates, voting trees can be used to select a candidate (the winner) by a sequence of pairwise competitions modelled by a binary tree (the agenda). The majority graph compactly represents the preferences of the agents and provides enough information to compute the winner. When some preferences are missing, there are various notions of winners, such as the possible winners (that is, winners in at least one completion) or the necessary winners (that is, winners in all completions). In this generalized scenario, we show that using the majority graph to compute winners is not correct, since it may declare as winners candidates that are not so. Nonetheless, the majority graph can be used to compute efficiently an upper or lower approximation of the correct set of winners. |
Year | DOI | Venue |
---|---|---|
2011 | 10.5555/2030470.2030516 | AAMAS |
Keywords | Field | DocType |
common set,enough information,possible winner,binary tree,necessary winner,generalized scenario,correct set,majority graph compactly,majority graph,winners candidate | Graph,Pairwise comparison,Voting,Computer science,Binary tree,Artificial intelligence,Machine learning | Conference |
ISBN | Citations | PageRank |
0-9826571-5-3 | 4 | 0.47 |
References | Authors | |
4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maria Silvia Pini | 1 | 353 | 30.28 |
Francesca Rossi | 2 | 2067 | 176.42 |
Kristen Brent Venable | 3 | 351 | 37.00 |
Toby Walsh | 4 | 4836 | 416.00 |