Complexity of terminating preference elicitation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Complexity of terminating preference elicitation

Full text

Pdf (386 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2 table of contents

Estoril, Portugal

SESSION: Economic paradigms table of contents

Pages 967-974

Year of Publication: 2008

ISBN:978-0-9817381-1-6

Author

Toby Walsh

NICTA and UNSW, Sydney, Australia

Sponsors

AAAI : Association for the Advancement of Artifical Intelligence
ACM: Association for Computing Machinery

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 50, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	Vincent Conitzer , Tuomas Sandholm, Computational aspects of preference aggregation, Carnegie Mellon University, Pittsburgh, PA, 2006
	5	Vincent Conitzer, Eliciting single-peaked preferences using comparison queries, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329204]
	6	Vincent Conitzer , Jérôme Lang , Tuomas Sandholm, How many candidates are needed to make elections hard to manipulate?, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846268]
	7	Vincent Conitzer , Tuomas Sandholm, Complexity of manipulating elections with few candidates, Eighteenth national conference on Artificial intelligence, p.314-319, July 28-August 01, 2002, Edmonton, Alberta, Canada
	8	Vincent Conitzer , Tuomas Sandholm, Vote elicitation: complexity and strategy-proofness, Eighteenth national conference on Artificial intelligence, p.392-397, July 28-August 01, 2002, Edmonton, Alberta, Canada
	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	Vincent Conitzer , Tuomas Sandholm , Jérôme Lang, When are elections with few candidates hard to manipulate?, Journal of the ACM (JACM), v.54 n.3, p.14-es, June 2007 [doi>10.1145/1236457.1236461]
	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.