skip to main content
10.1145/1160633.1160755acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
Article

Strategic voting when aggregating partially ordered preferences

Published: 08 May 2006 Publication History

Abstract

Preferences of a single agent are often partially ordered. For example, it may be hard to compare a novel with a biography. In such a situation, the agent may want the novel and the biography to be considered incomparable. We consider here how to aggregate the partially ordered preferences of multiple agents in order to return a set of most preferred outcomes. We define the notion of strategy-proofness for such a scenario. This is when preference aggregation cannot be manipulated. We prove that if there is no dictator, agents can manipulate the result by voting strategically to determine the most preferred outcomes. This extends the well-known theorem by Gibbard and Satterthwaite for total orders.

References

[1]
K. J. Arrow and A. K. Sen and K. Suzumara. Handbook of Social Choice and Welfare. North-Holland, Elsevier, 2002.
[2]
S. Barbera. Strategy-Proofness and Pivotal Voters: A Direct Proof of the Gibbard-Satterthwaite Theorem. International Economic Review, Vol.24, No.2, pages 413--417, 1983.
[3]
A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41, 1973.
[4]
K. Konczak and J. Lang. Voting procedures with incomplete preferences. IJCAI 05 Workshop on Advances in Preference Handling, 2005.
[5]
E. Muller and M. A. Satterthwaite. The equivalence of strong positive association and strategy-proofness. Economic Theory, 14, 1977.
[6]
M. S. Pini, F. Rossi, K. B. Venable, T. Walsh. Aggregating partially ordered preferences: impossibility and possibility results. Proc. TARK X, ACM Digital Library, June 2005.
[7]
M. A. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187--217, 1975.

Cited By

View all
  • (2016)An Axiomatic Approach to Community DetectionProceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science10.1145/2840728.2840748(135-146)Online publication date: 14-Jan-2016
  • (2010)Comparing multiagent systems research in combinatorial auctions and votingAnnals of Mathematics and Artificial Intelligence10.1007/s10472-010-9205-y58:3-4(239-259)Online publication date: 24-Jul-2010
  • (2008)Constraints and Preferences: Modelling Frameworks and Multi-agent settingsPreferences and Similarities10.1007/978-3-211-85432-7_13(305-320)Online publication date: 2008
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems
May 2006
1631 pages
ISBN:1595933034
DOI:10.1145/1160633
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 May 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. gibbard satterthwaite theorem
  2. partial orders
  3. preference aggregation
  4. strategy-proofness

Qualifiers

  • Article

Conference

AAMAS06
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)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)An Axiomatic Approach to Community DetectionProceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science10.1145/2840728.2840748(135-146)Online publication date: 14-Jan-2016
  • (2010)Comparing multiagent systems research in combinatorial auctions and votingAnnals of Mathematics and Artificial Intelligence10.1007/s10472-010-9205-y58:3-4(239-259)Online publication date: 24-Jul-2010
  • (2008)Constraints and Preferences: Modelling Frameworks and Multi-agent settingsPreferences and Similarities10.1007/978-3-211-85432-7_13(305-320)Online publication date: 2008
  • (2007)A Short Introduction to Computational Social ChoiceProceedings of the 33rd conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-540-69507-3_4(51-69)Online publication date: 20-Jan-2007
  • (2005)Mechanism Design for Preference Aggregation over CoalitionsPrinciples and Practice of Constraint Programming - CP 200510.1007/11564751_90(852-852)Online publication date: 2005
  • (2005)Some representation and computational issues in social choiceProceedings of the 8th European conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty10.1007/11518655_3(15-26)Online publication date: 6-Jul-2005

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