Paper Info
Title
Dealing with Incomplete Agents' Preferences and an Uncertain Agenda in Group Decision Making via Sequential Majority Voting.
Abstract
We consider multi-agent systems where agents' pref- erences are aggregated via sequential majority voting: each decision is taken by performing a sequence of pair- wise comparisons where each comparison is a weighted majority vote among the agents. Incompleteness in the agents' preferences is common in many real-life set- tings due to privacy issues or an ongoing elicitation process. In addition, there may be uncertainty about how the preferences are aggregated. For example, the agenda (a tree whose leaves are labelled with the deci- sions being compared) may not yet be known or fixed. We therefore study how to determine collectively op- timal decisions (also called winners) when preferences may be incomplete, and when the agenda may be uncer- tain. We show that it is computationally easy to deter- mine if a candidate decision always wins, or may win, whatever the agenda. On the other hand, it is compu- tationally hard to know whether a candidate decision wins in at least one agenda for at least one completion of the agents' preferences. These results hold even if the agenda must be balanced so that each candidate de- cision faces the same number of majority votes. Such results are useful for reasoning about preference elicita- tion. They help understand the complexity of tasks such as determining if a decision can be taken collectively, as well as knowing if the winner can be manipulated by appropriately ordering the agenda.
Year
Venue
Keywords
2008
KR
group decision making,multi agent system,majority voting
Field
DocType
Volume
Pairwise comparison,Data mining,Preference elicitation,Computer science,Majority rule,Group decision-making
Conference
abs/0909.4
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Maria Silvia Pini135330.28
Francesca Rossi22067176.42
Kristen Brent Venable335137.00
Toby Walsh44836416.00