Skip Navigation



Journal of Logic and Computation Advance Access published online on April 30, 2008
Journal of Logic and Computation, 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

Original Papers

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 inear 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][ISI]
  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][ISI]
  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][ISI]
  8. Doyle J, Wellman MP. Impediments to universal preference-based default theories. In: Artificial Intelligence (1991) 49:97–128.[CrossRef][ISI]
  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][ISI]
  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][ISI]
  13. Fishburn PC. Impossibility theorems without the social completeness axiom. In: Econometrica (1974) 42:695–704.[CrossRef][ISI]
  14. Gärdenfors P. Manipulation of social choice functions. In: Journal of Economic Theory (1976) 13:217–228.[CrossRef][ISI]
  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][ISI]
  17. Gibbard A. Manipulation of voting schemes: a general result. In: Econometrica (1973) 41:587–601.[CrossRef][ISI]
  18. Kelly JS. Strategy-proofness and social choice functions without resoluteness. In: Econometrica (1977) 45:439–446.[CrossRef][ISI]
  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][ISI]
  31. Rodriguez-Alvarez C. On the manipulation of social choice correspondences. In: Social Choice and Welfare (2007) 29:175–199.[CrossRef][ISI]
  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][ISI]
  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][ISI]
  39. Zhou L, Ching S. Multi-valued strategy-proof social choice rules. In: Social Choice and Welfare (2002) 19:569–580.[CrossRef][ISI]

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?