skip to main content
10.5555/1402298.1402357acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Complexity of terminating preference elicitation

Published: 12 May 2008 Publication History

Abstract

Complexity theory is a useful tool to study computational issues surrounding the elicitation of preferences, as well as the strategic manipulation of elections aggregating together preferences of multiple agents. We study here the complexity of determining when we can terminate eliciting preferences, and prove that the complexity depends on the elicitation strategy. We show, for instance, that it may be better from a computational perspective to elicit all preferences from one agent at a time than to elicit individual preferences from multiple agents. We also study the connection between the strategic manipulation of an election and preference elicitation. We show that what we can manipulate affects the computational complexity of manipulation. In particular, we prove that there are voting rules which are easy to manipulate if we can change all of an agent's vote, but computationally intractable if we can change only some of their preferences. This suggests that, as with preference elicitation, a fine-grained view of manipulation may be informative. Finally, we study the connection between predicting the winner of an election and preference elicitation. Based on this connection, we identify a voting rule where it is computationally difficult to decide the probability of a candidate winning given a probability distribution over the votes.

References

[1]
J. Bartholdi and J. Orlin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4):341--354, 1991.
[2]
J. Bartholdi, C. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227--241, 1989.
[3]
D. Black. On the rationale of group decision-making. Journal of Political Economy, 56(1):23--34, 1948.
[4]
V. Conitzer. Computational Aspects of Preference Aggregation. PhD thesis, Computer Science Department, Carnegie Mellon University, 2006.
[5]
V. Conitzer. Eliciting single-peaked preferences using comparison queries. In Proc. of the Int. Conf. on Autonomous Agents and Multiagent Systems, 2007.
[6]
V. Conitzer, J. Lang, and T. Sandholm. How many candidates are needed to make elections hard to manipulate. In Proc. of the Conf. on Theoretical Aspects of Reasoning about Knowledge, 2003.
[7]
V. Conitzer and T. Sandholm. Complexity of manipulating elections with few candidates. In Proc. of the 18th National Conf. on AI. 2002.
[8]
V. Conitzer and T. Sandholm. Vote elicitation: Complexity and strategy-proofness. In Proc. of the 18th National Conf. on AI. 2002.
[9]
V. Conitzer and T. Sandholm. Universal voting protocol tweaks to make manipulation hard. In Proc. of 18th IJCAI, pages 781--788. 2003.
[10]
V. Conitzer and T. Sandholm. Nonexistence of voting rules that are usually hard to manipulate. In Proc. of the 21st National Conf. on AI. 2006.
[11]
V. Conitzer, T. Sandholm, and J. Lang. When are elections with few candidates hard to manipulate. Journal of the Association for Computing Machinery, 54, 2007.
[12]
E. Elkind and H. Lipmaa. Hybrid voting protocols and hardness of manipulation. In Proc. of the 16th Annual Int. Symposium on Algorithms and Computation (ISAAC'05), 2005.
[13]
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Llull and Copeland voting broadly resist bribery and control. In Proc. of the 22nd National Conf. on AI, pages 724--730. 2007.
[14]
A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41:587--601, 1973.
[15]
K. Konczak and J. Lang. Voting procedures with incomplete preferences. In Proc. of the IJCAI-2005 workshop on Advances in Preference Handling, 2005.
[16]
M. Pini, F. Rossi, B. Venable, and T. Walsh. Incompleteness and incomparability in preference aggregation. In Proc. of 20th IJCAI. 2007.
[17]
A. D. Procaccia and J. S. Rosenschein. Junta distributions and the average-case complexity of manipulating elections. Journal of Artificial Intelligence Research, 28:157--181, 2007.
[18]
M. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and socia l welfare functions. Journal of Economic Theory, 10:187--216, 1975.

Cited By

View all
  • (2011)Possible and necessary winners in voting treesThe 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/2030470.2030516(311-318)Online publication date: 2-May-2011
  • (2011)On the modelling and optimization of preferences in constraint-based temporal reasoningArtificial Intelligence10.1016/j.artint.2010.11.016175:7-8(1390-1409)Online publication date: 1-May-2011
  • (2011)Incompleteness and incomparability in preference aggregationArtificial Intelligence10.1016/j.artint.2010.11.009175:7-8(1272-1289)Online publication date: 1-May-2011
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2
May 2008
673 pages
ISBN:9780981738116

Sponsors

In-Cooperation

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 12 May 2008

Check for updates

Author Tags

  1. complexity
  2. elicitation
  3. preferences

Qualifiers

  • Research-article

Conference

AAMAS08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2011)Possible and necessary winners in voting treesThe 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/2030470.2030516(311-318)Online publication date: 2-May-2011
  • (2011)On the modelling and optimization of preferences in constraint-based temporal reasoningArtificial Intelligence10.1016/j.artint.2010.11.016175:7-8(1390-1409)Online publication date: 1-May-2011
  • (2011)Incompleteness and incomparability in preference aggregationArtificial Intelligence10.1016/j.artint.2010.11.009175:7-8(1272-1289)Online publication date: 1-May-2011
  • (2010)Is computational complexity a barrier to manipulation?Proceedings of the 11th international conference on Computational logic in multi-agent systems10.5555/1893859.1893861(1-7)Online publication date: 16-Aug-2010
  • (2009)Where are the really hard manipulation problems? the phase transition in manipulating the veto ruleProceedings of the 21st International Joint Conference on Artificial Intelligence10.5555/1661445.1661497(324-329)Online publication date: 11-Jul-2009
  • (2009)Compiling the votes of a subelectorateProceedings of the 21st International Joint Conference on Artificial Intelligence10.5555/1661445.1661462(97-102)Online publication date: 11-Jul-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media