Skip Navigation


Journal of Logic and Computation Advance Access originally published online on April 30, 2008
Journal of Logic and Computation 2009 19(3):475-502; doi:10.1093/logcom/exn012
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Pini, M. S.
Right arrow Articles by Walsh, T.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

This article appears in the following Journal of Logic and Computation issue: Special Issue: Connections between Belief Revision, Belief Merging and Social Choice [View the issue table of contents]

Original Articles

Aggregating Partially Ordered Preferences

Maria Silvia Pini, Francesca Rossi and Kristen Brent Venable

Department of Pure and Applied Mathematics, University of Padova, Padova, Italy.
E-mail: mpini{at}math.unipd.it; frossi{at}math.unipd.it; kvenable{at}math.unipd.it

Toby Walsh

NICTA and UNSW, Sydney, Australia.
E-mail: tw{at}cse.unsw.edu.au

Preferences are not always expressible via complete linear orders: sometimes it is more natural to allow for the presence of incomparable outcomes. This may hold both in the agents' preference ordering and in the social order. In this article, we consider this scenario and study what properties it may have. In particular, we show that, despite the added expressivity and ability to resolve conflicts provided by incomparability, classical impossibility results (such as Arrow's theorem, Muller–Satterthwaite's theorem and Gibbard–Satterthwaite's theorem) still hold. We also prove some possibility results, generalizing Sen's theorem for majority voting. To prove these results, we define new notions of unanimity, monotonicity, dictator, triple-wise value-restriction and strategy-proofness, which are suitable and natural generalizations of the classical ones for complete orders.

Keywords: Social choice; preference aggregation; partially ordered preferences; strategy-proofness



References

  1. Arrow KJ. Social Choice and Individual Values (1951) New York: John Wiley & Sons, Inc. Chapman & Hall, London.
  2. Arrow KJ, Sen AK, Suzumara K. Handbook of Social Choice and Welfare (2002) North-Holland, Amsterdam.
  3. Barbera S. Strategy-proofness and pivotal voters: a direct proof of the Gibbard–Satterthwaite theorem. In: International Economic Review (1983) 24:413–17.[CrossRef][Web of Science]
  4. Barberà S, Bossert W, Pattanaik PK. Handbook of Utility Theory. Volume II Extensions (2004) Kluwer.
  5. Barberà S, Dutta B, Sen A. Strategy-proof social choice correspondences. In: Journal of Economic Theory (2002) 101:374–394.[CrossRef][Web of Science]
  6. Barthelemy JP. Arrow's theorem: unusual domains and extended codomains. In: Matematical Social Sciences (1982) 3:79–89.[CrossRef]
  7. Benoït J-P. Strategic manipulation in voting games when lotteries and ties are permitted. In: Journal of Economic Theory (2002) 102:421–436.[CrossRef][Web of Science]
  8. Doyle J, Wellman MP. Impediments to universal preference-based default theories. In: Artificial Intelligence (1991) 49:97–128.[CrossRef][Web of Science]
  9. Dubois D, Fargier H, Perny P. On the limitations of ordinal approaches to decision making. In: In Proceedings KR 2002 (2002) San Francisco, CA: Morgan Kaufmann. 133–144.
  10. Duggan J, Schwartz T. Strategic manipulability without resoluteness or shared beliefs: Gibbard–Satterthwaite generalized. In: Social Choice and Welfare (2000) 17:85–93.[CrossRef][Web of Science]
  11. Feldman A. A strategic analysis of nonranked voting systems. In: SIAM Journal of Applied Mathematics (1978) 35:488–495.[CrossRef]
  12. Feldman A. Nonmanipulable multi-valued social decision functions. In: Public Choice (1979) 34:177–188.[CrossRef][Web of Science]
  13. Fishburn PC. Impossibility theorems without the social completeness axiom. In: Econometrica (1974) 42:695–704.[CrossRef][Web of Science]
  14. Gärdenfors P. Manipulation of social choice functions. In: Journal of Economic Theory (1976) 13:217–228.[CrossRef][Web of Science]
  15. Gärdenfors P. On definitions of manipulation of social choice functions. In: In Aggregation and Revelation of Preferences, Vol. 2, Studies in Public Economics—Laffont JJ, ed. (1979) Amsterdam: North-Holland. 29–36.
  16. Geanakoplos J. Three brief proofs of Arrow's impossibility theorem. In: Economic Theory (2005) 26:211–215.[CrossRef][Web of Science]
  17. Gibbard A. Manipulation of voting schemes: a general result. In: Econometrica (1973) 41:587–601.[CrossRef][Web of Science]
  18. Kelly JS. Strategy-proofness and social choice functions without resoluteness. In: Econometrica (1977) 45:439–446.[CrossRef][Web of Science]
  19. Kelly JS. Arrow Impossibility Theorems (1978) New York: Academic Press.
  20. Kelly JS. Social Choice Theory: An introduction (1988) Berlin: Springer-Verlag.
  21. Konczak K. Voting procedures with incomplete preferences. In: In Proceedings of IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling—Brafman Ronen, Junker Ulrich, eds. (2005) Scotland: Edinburgh.
  22. Pini MS, Rossi F, Venable KB, Walsh T. Incompleteness and incomparability in preference aggregation. In: In Proceedings of IJCAI 2007 (2007) Menlo Park, CA: AAAI Press. 1464–1469.
  23. Lang J, Pini MS, Rossi F, Venable KB, Walsh T. Winner determination in sequential majority voting. In: In Proceedings of IJCAI 2007 (2007) Menlo Park, CA: AAAI Press. 1372–1377.
  24. Mas-Colell A, Sonnenschein H. General possibility theorems for group decisions. In: Review of Economic Studies (1972) 39:165–192.
  25. Muller E, Satterthwaite MA. The equivalence of strong positive association and strategy-proofness. In: Economic Theory (1977) 14:412–418.[CrossRef]
  26. Pattanaik PK. Strategic voting without collusion under binary and democratic group decision rules. In: The Review of Economic Studies (1975) 42:93–103.[CrossRef]
  27. Pattanaik PK. On the stability of sincere voting situations. In: Journal of Economic Theory. 6:558–574.
  28. Pini MS, Rossi F, Venable KB, Walsh T. Strategic voting when aggregating partially ordered preferences. In: In Proceedings of AAMAS-06 (2006) New York: ACM Press. 685–687.
  29. Pini MS, Rossi F, Venable KB, Walsh Toby. Aggregating partially ordered preferences: impossibility and possibility results. In: In Proceeding of TARK-05 (2005) 193–206. ACM Digital Library, National University of Singapore.
  30. Reny P. Arrow's theorem and the Gibbard–Satterthwaite theorem: a unified approach. In: Economics Letters (2001) 70:99–105.[CrossRef][Web of Science]
  31. Rodriguez-Alvarez C. On the manipulation of social choice correspondences. In: Social Choice and Welfare (2007) 29:175–199.[CrossRef][Web of Science]
  32. Sato S. On the strategy-proof social choice correspondences. In: Social Choice and Welfare (2007) 29(4). Berlin / Heidelberg: Springer-Verlag.
  33. Satterthwaite MA. Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions. In: Economic Theory (1975) 10:187–217.[CrossRef]
  34. Sen A. Collective Choice and Social Wellfare (1970) Holden-Day.
  35. Tanaka Y. Generalized monotonicity and strategy-proofness for non-resolute social choice correspondences. In: Economic Bulletin (2001) 4:1–8.
  36. Tanaka Y. Oligarchy for social choice correspondences and strategy proofness. In: Theory and Decision (2003) 55:273–287.[CrossRef][Web of Science]
  37. Taylor AD. The manipulability of voting systems. In: The American Mathematical Monthly (2002) 109:321–333.[CrossRef]
  38. Weymark JA. Arrow's theorem with social quasi-orderings. In: Public Choice (1984) 42:235–246.[CrossRef][Web of Science]
  39. Zhou L, Ching S. Multi-valued strategy-proof social choice rules. In: Social Choice and Welfare (2002) 19:569–580.[CrossRef][Web of Science]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Pini, M. S.
Right arrow Articles by Walsh, T.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?