Top

Social Choice and Welfare

Published in:

01-09-2015

Distance rationalization of voting rules

Authors: Edith Elkind, Piotr Faliszewski, Arkadii Slinko

Published in: Social Choice and Welfare | Issue 2/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The concept of distance rationalizability allows one to define new voting rules or rationalize existing ones via a consensus, i.e., a class of elections that have a unique, indisputable winner, and a distance over elections: A candidate is declared an election winner if she is the consensus candidate in one of the nearest consensus elections. Many classic voting rules are defined or can be represented in this way. In this paper, we focus on the power and the limitations of the distance rationalizability approach. Lerer and Nitzan (J Econ Theory 37(1):191–201, 1985) and Campbell and Nitzan (Soc Choice Welf 3(1):1–16, 1986) show that if we do not place any restrictions on the notions of distance and consensus then essentially all voting rules can be distance-rationalized. We identify a natural class of distances on elections—votewise distances—which depend on the submitted votes in a simple and transparent manner, and investigate which voting rules can be rationalized via distances of this type. We also study axiomatic properties of rules that can be defined via votewise distances.

previous article Implementation and axiomatization of discounted Shapley values

next article Further results on dictatorial domains

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

We refer to this result, proved by Lerer and Nitzan (1985) and generalized by Campbell and Nitzan (1986), as the ‘universal distance rationalizability theorem’. Unaware of these papers, we have rediscovered the universal distance rationalizability theorem in a conference paper (Elkind et al. 2010). We would like to thank the reviewer who brought the papers of Lerer and Nitzan and of Campbell and Nitzan to our attention.

We have rediscovered a slightly stronger version of this result (Elkind et al. 2010, 2011).

We follow the terminology of Lerer and Nitzan (1985) here.

We remark that Lerer and Nitzan (1985) refer to distances that are defined in this way as symmetric additively decomposable metrics; generalizing this class of distances is at the heart of this paper.

One can also consider situations in which the voters reach a consensus that several candidates are equally well qualified to be elected, but we do not discuss this possibility.

One might think that the term “\({\mathcal {K}}\)-consistent” would be more appropriate than “\({\mathcal {K}}\)-compatible.” Indeed, a voting rule that elects the Condorcet winner whenever one exists is usually referred to as Condorcet-consistent. Nonetheless, we decided to use the term “\({\mathcal {K}}\)-compatible” to avoid confusion with the normative axiom of consistency.

Technically, a norm is defined for a fixed value of \(n\), whereas voting rules are usually defined for any number of voters, i.e., we require a family of norms, one for each value of \(n\). Note that each \(p\)-norm, \(p\in \mathbb {Z}^+\cup \{\infty \}\), is indeed defined for all values of \(n\).

Known in statistics as Spearman’s footrule (Kendall and Gibbons 1990).

The proof is available on request.

This notion is due to Lerer and Nitzan (1985), who did not use the term “rank-monotonicity.” We introduce this term to distinguish this notion from relative monotonicity (Definition 12).

Aleskerov F, Chistyakov V, Kalyagin V (2010) The threshold aggregation. Econ Lett 107(2):261–262CrossRef

Arrow K (1951; revised edition, 1963) Social choice and individual values, Wiley, New York

Baigent N (1987a) Metric rationalisation of social choice functions according to principles of social choice. Math Soc Sci 13(1):59–65CrossRef

Baigent N (1987b) Preference proximity and anonymous social choice. Q J Econ 102(1):161–169CrossRef

Baigent N, Klamler C (2004) Transitive closure, proximity and intransitivities. Econ Theory 23(1):175–181CrossRef

Bartholdi J III, Tovey C, Trick M (1989) Voting schemes for which it can be difficult to tell who won the election. Soc Choice Welf 6(2):157–165CrossRef

Bauer F, Stoer J, Witzgall C (1961) Absolute and monotonic norms. Numerische Matematic 3:257–264CrossRef

Bogard K (1973) Preference structures I: distances between transitive preference relations. J Math Sociol 3:49–67CrossRef

Bogard K (1975) Preference structures II: distances between transitive preference relations. SIAM J Appl Math 29:254–262CrossRef

Boutilier C, Procaccia A (2012, July) A dynamic rationalization of distance rationalizability. In: Proceedings of the 26th AAAI conference on artificial intelligence. AAAI Press, pp 1278–1284

Brams S, Fishburn P (2002) Voting procedures. In: Arrow K, Sen A, Suzumura K (eds) Handbook of social choice and welfare, vol 1. Elsevier, Amsterdam, pp 173–236CrossRef

Brandt F (2009) Some remarks on Dodgson’s voting rule. Math Logic Q 55(4):460–463CrossRef

Campbell D, Nitzan S (1986) Social compromise and social metrics. Soc Choice Welf 3(1):1–16CrossRef

Caragiannis I, Procaccia A, Shah N (2013) When do noisy votes reveal the truth?. In: Proceedings of the 13th ACM Conference on electronic commerce, pp 143–160

Chebotarev PY, Shamis E (1998) Characterizations of scoring methods for preference aggregation. Ann Oper Res 80:299–332CrossRef

Condorcet J (1785) Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. (Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale)

Conitzer V, Rognlie M, Xia L (2009, July) Preference functions that score rankings and maximum likelihood estimation. In: Proceedings of the 21st international joint conference on artificial intelligence. AAAI Press, pp 109–115

Conitzer V, Sandholm T (2005, July) Common voting rules as maximum likelihood estimators. In: Proceedings of the 21st conference on uncertainty in artificial intelligence. AUAI Press, pp 145–152

Cook W, Seiford L (1978) Priority ranking and consensus information. Manag Sci 24:1721–1732CrossRef

Cook W, Seiford L (1982) On the Borda-Kendall consensus method for priority ranking problems. Manag Sci 28:621–637CrossRef

Deza MM, Deza E (2009) Encyclopedia of distances. Springer, BerlinCrossRef

Eckert D, Klamler C (2011) Distance-based aggregation theory. In: Herrera-Viedma E, Garca-Lapresta JL, Kacprzyk J, Fedrizzi M, Nurmi H, Zadrozny S (eds) Consensual processes. Springer, Berlin, pp 3–22CrossRef

Elkind E, Faliszewski P, Slinko A (2010, May) On the role of distances in defining voting rules. In: Proceedings of the 9th international conference on autonomous agents and multiagent systems, pp 375–382

Elkind E, Faliszewski P, Slinko A (2011) Homogeneity and monotonicity of distance-rationalizable voting rules. In: Proceedings of the 10th international conference on autonomous agents and multiagent systems, pp 821–828

Elkind E, Faliszewski P, Slinko A (2012) Rationalizations of Condorcet consistent rules via distances of hamming type. Soc Choice Welf 4(39):891–905CrossRef

Elkind E, Shah N (2014, July) Electing the most probable without eliminating the irrational: Voting over intransitive domains. In: Proceedings of the 30th conference on uncertainty in artificial intelligence

Elkind E, Slinko A (2015) Rationalizations of voting rules. In: Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (eds) Handbook of computational social choice, Chapt 8. Cambridge University Press, Cambridge

Farkas D, Nitzan S (1979) The Borda rule and Pareto stability : a comment. Econometrica 47:1305–1306CrossRef

Goldsmith J, Lang J, Mattei N, Perny P (2014) Voting with rank dependent scoring rules. In: Proceedings of the 28th AAAI conference on artificial intelligence. AAAI Press, pp 698–704

Hemaspaandra E, Hemaspaandra L, Rothe J (1997) Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. J ACM 44(6):806–825CrossRef

Hudry O, Monjardet B (2010) Consensus theories. An oriented survey. Math Soc Sci 190:139–167

Kendall M, Gibbons J (1990) Rank correlation methods. Oxford University Press, Oxford

Lerer E, Nitzan S (1985) Some general results on the metric rationalization for social decision rules. J Econ Theory 37(1):191–201CrossRef

Litvak B (1982) Information given by the experts. Methods of acquisition and analysis. Radio and Communication, Moscow

Litvak B (1983) Distances and consensus rankings. Cybernetics and systems analysis 19(1):71–81. (Translated from Kibernetika, No. 1, pp 57–63, January-February 1983)

Meskanen T, Nurmi H (2008) Closeness counts in social choice. In: Braham M, Steffen F (eds) Power, freedom, and voting. Springer, Berlin

Miller M, Osherson D (2009) Methods for distance-based judgment aggregation. Soc Choice Welf 4(32):575–601CrossRef

Moulin H (1991) Axioms of cooperative decision making. Cambridge University Press, Cambridge

Nitzan S (1981) Some measures of closeness to unanimity and their implications. Theory Decis 13(2):129–138CrossRef

Nitzan S (1989) More on preservation of preference proximity and anonymous social choice. Q J Econ 104(1):187–190CrossRef

Pfingsten A, Wagener A (2003) Bargaining solutions as social compromises. Theory Decis 55(4):359–389CrossRef

Pivato M (2013) Voting rules as statistical estimators. Soc Choice Welf 40(2):581–630CrossRef

Schechter E (1997) Handbook of analysis and its foundations. Academic Press, New York

Xia L, Conitzer V (2011, July) A maximum likelihood approach towards aggregating partial orders. In: Proceedings of the 22nd international joint conference on artificial intelligence, pp 446–451

Xia L, Conitzer V, Lang J (2010) Aggregating preferences in multiissue domains by using maximum likelihood estimators. In: Proceedings of the 9th international conference on autonomous agents and multiagent systems, pp 399–406

Young H (1975) Social choice scoring functions. SIAM J Appl Math 28(4):824–838CrossRef

Young H (1977) Extending Condorcet’s rule. J Econ Theory 16(2):335–353CrossRef

Young H, Levenglick A (1978) A consistent extension of Condorcet’s election principle. SIAM J Appl Math 35(2):285–300CrossRef

Title: Distance rationalization of voting rules
Authors: Edith Elkind
Piotr Faliszewski
Arkadii Slinko
Publication date: 01-09-2015
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 2/2015
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-015-0892-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2015

Implementation and axiomatization of discounted Shapley values

On existence of ex post Nash consistent representation for effectivity functions

On justifiable choice functions over opportunity sets

Dynamic stable set as a tournament solution

Further results on dictatorial domains

Bargaining with split-the-difference arbitration

Premium Partner