Sequential Majority Voting with Incomplete Profiles

Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh

In sequential majority voting, preferences are aggregated by a sequence of pairwise comparisons (also called an agenda) between candidates. The result of each comparison is determined by a weighted majority vote between the agents. In this paper we consider the situation where the agents may not have revealed all their preferences. This is common in real-life settings, due to privacy issues or an ongoing elicitation process. We study the computational complexity of determining the winner(s), given that some preferences may not yet be revealed and the agenda is not yet known or decided. We show that it is easy to determine if a candidate must win whatever the agenda. On the other hand, it is hard to know whether a candidate can win in at least one agenda for at least one completion of unrevealed preferences. This is also true if the agenda is balanced (that is, each candidate must win the same number of pairwise competitions to win overall).

Subjects: 15.5 Decision Theory; 7.1 Multi-Agent Systems

Submitted: May 15, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.