Skip to main content
Top
Published in: Social Choice and Welfare 1/2024

02-11-2023 | Original Paper

Stochastic same-sidedness in the random voting model

Authors: Sarvesh Bandhu, Abhinaba Lahiri, Anup Pramanik

Published in: Social Choice and Welfare | Issue 1/2024

Log in

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

search-config
loading …

Abstract

We study the implications of stochastic same-sidedness (SSS) axiom in the random voting model. At a given preference profile if one agent changes her preference ordering to an adjacent one by swapping two consecutively ranked alternatives, then SSS imposes two restrictions on the lottery selected by a voting rule before and after the swap. First, the sum of probabilities of the alternatives which are ranked strictly higher than the swapped pair should remain the same. Second, the sum of probabilities assigned to the swapped pair should also remain the same. We show that every random social choice function (RSCF) that satisfies efficiency and SSS is a random dictatorship provided that there are two voters or three alternatives. For the case of more than two voters and atleast four alternatives, every RSCF that satisfies efficiency, tops-onlyness and SSS is a random dictatorship.

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!

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!

Appendix
Available only for authorised users
Footnotes
1
SSS axiom implies that the sum of probabilities of the alternatives which are ranked strictly below the swapped pair should remain the same before and after the swap.
We note that one can also define SSS axiom imposing following two restrictions on RSCFs. Firstly, the sum of probabilities of the alternatives which are ranked strictly higher than the swapped pair should remain the same before and after the swap and secondly, the sum of probabilities of the alternatives which are ranked strictly below the swapped pair should remain the same before and after the swap.
 
2
In Sect. 3, we discuss the relationship between bounded response and stochastic same-sidedness in details.
 
3
Mennle and Seuken (2021) show that sd-strategy-proofness is equivalent to the combination of three axioms, swap monotonicity upper invariance, and lower invariance. Upper-contour strategy-proofness is equivalent to the combination of upper invariance and lower invariance.
 
4
Gibbard (1977) showed that any unanimous and sd-strategy-proof RSCF on the unrestricted domain is a randomization over unanimous and strategy-proof DSCFs. Such DSCFs are known to be dictatorships (Gibbard (1973); Satterthwaite (1975)).
 
5
Note that \(U(P_i, A(P_i,P'_i))\) may be empty. Also, if \(P_i\) and \(P'_i\) are adjacent, then \(U(P_i, A(P_i,P'_i))=U(P'_i, A(P_i,P'_i))\).
 
6
The DSCF f satisfies efficiency, if for all \(P\in {\mathbb {P}}^n\) and for all \(a,b\in A\) such that \(a\;P_i\;b\) for all \(i\in N\), we have \(f(P)\ne b\). A much weaker notion of efficiency is unanimity. A DSCF f satisfies unanimity, if for all \(P\in {\mathbb {P}}^n\) and \(a\in A\) such that \(r_1(P_i)=a\) for all \(i\in N\), we have \(f(P)=a\).
 
7
The symbols \(\subseteq\) and \(\subset\) denote subset and proper subset respectively.
 
8
Apart from stochastic dominance, there are many ways one can compare lotteries and define strategy-proofness based on these comparisons. For instance, see (Aziz et al. 2018) for pairwise comparison strategy-proofness bilinear dominance strategy-proofness and sure thing strategy-proofness. Although all these notions are weaker than sd-strategy-proofness, we note that our SSS axiom is independent of these notions of incentives.
 
9
Infact, sd-strategy-proofness is standard incentive property in the random voting model. For instance, see Ehlers et al. (2002); Dutta et al. (2002); Chatterji et al. (2012); Peters et al. (2014); Chatterji et al. (2014); Pycia and Ünver (2015); Peters et al. (2017), Roy and Sadhukhan (2019, 2020) etc.. Recently, Roy et al. (2021) provides a survey on sd-strategy-proof rules in the voting model.
 
10
We thank an anonymous reviewer for suggesting these simple yet very intuitive examples.
 
11
One strain of literature weakens the notion of sd-strategy-proofness by requiring truth-telling to maximize a voter’s expected utility only for a limited class of vNM utility representations of the voter’s true preference ordering. See, for instance, limited-Comparison Strategy-proofness in Sen (2011), convex strategy-proofness in Balbuzanov (2016), partial strategy-proofness in Mennle and Seuken (2021) etc. All these notions are stronger than weak sd-strategy-proofness and we note that our SSS axiom is independent of these weaker notions of sd-strategy-proofness.
 
12
In particular, \(\text {Conv}[{\mathbb {F}}^{BR+EFF}]=\text {Conv}[{\mathbb {F}}^{SS+EFF}]=\Phi ^{SSS+EFF}\). Here, \({\mathbb {F}}^{BR+EFF}\) denotes the set of DSCFs that satisfy BR and efficiency.
 
13
Here, t is a positive integer and \(t=|{\mathbb {F}}^{SS}|\).
 
14
See, for instance, Birkhoff (1946) and Von Neumann (2016) for the Birkhoff-von Neumann Theorem.
 
Literature
go back to reference Aziz H, Brandl F, Brandt F, Brill M (2018) On the tradeoff between efficiency and strategyproofness. Games Econ Behav 110:1–18CrossRef Aziz H, Brandl F, Brandt F, Brill M (2018) On the tradeoff between efficiency and strategyproofness. Games Econ Behav 110:1–18CrossRef
go back to reference Balbuzanov I (2016) Convex strategyproofness with an application to the probabilistic serial mechanism. Social Choice Welf 46:511–520CrossRef Balbuzanov I (2016) Convex strategyproofness with an application to the probabilistic serial mechanism. Social Choice Welf 46:511–520CrossRef
go back to reference Birkhoff G (1946) Three observations on linear algebra,. Univ Nac Tacuman Rev Ser A 5:147–151 Birkhoff G (1946) Three observations on linear algebra,. Univ Nac Tacuman Rev Ser A 5:147–151
go back to reference Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J Econ Theory 100:295–328CrossRef Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J Econ Theory 100:295–328CrossRef
go back to reference Brandt F (2017) Rolling the dice: recent results in probabilistic social choice. Trends in Computational Social Choice, AI Access Brandt F (2017) Rolling the dice: recent results in probabilistic social choice. Trends in Computational Social Choice, AI Access
go back to reference Chatterji S, Roy S, Sen A (2012) The structure of strategy-proof random social choice functions over product domains and lexicographically separable preferences. J Math Econ 48:353–366CrossRef Chatterji S, Roy S, Sen A (2012) The structure of strategy-proof random social choice functions over product domains and lexicographically separable preferences. J Math Econ 48:353–366CrossRef
go back to reference Chatterji S, Sen A, Zeng H (2014) Random dictatorship domains. Games Econ Behav 86:212–236CrossRef Chatterji S, Sen A, Zeng H (2014) Random dictatorship domains. Games Econ Behav 86:212–236CrossRef
go back to reference Cho WJ (2016) Incentive properties for ordinal mechanisms. Games Econ Behav 95:168–177CrossRef Cho WJ (2016) Incentive properties for ordinal mechanisms. Games Econ Behav 95:168–177CrossRef
go back to reference Chun Y, Yun K (2020) Upper-contour strategy-proofness in the probabilistic assignment problem. Social Choice Welf 54:667–687CrossRef Chun Y, Yun K (2020) Upper-contour strategy-proofness in the probabilistic assignment problem. Social Choice Welf 54:667–687CrossRef
go back to reference Dutta B, Peters H, Sen A (2002) Strategy-proof probabilistic mechanisms in economies with pure public goods. J Econ Theory 106:392–416CrossRef Dutta B, Peters H, Sen A (2002) Strategy-proof probabilistic mechanisms in economies with pure public goods. J Econ Theory 106:392–416CrossRef
go back to reference Ehlers L, Peters H, Storcken T (2002) Strategy-proof probabilistic decision schemes for one-dimensional single-peaked preferences. J Econ Theory 105:408–434CrossRef Ehlers L, Peters H, Storcken T (2002) Strategy-proof probabilistic decision schemes for one-dimensional single-peaked preferences. J Econ Theory 105:408–434CrossRef
go back to reference Gibbard A (1973) Manipulation of voting schemes: a general result. Econometrica J Econ Soc: 587–601 Gibbard A (1973) Manipulation of voting schemes: a general result. Econometrica J Econ Soc: 587–601
go back to reference Gibbard A(1977) Manipulation of schemes that mix voting with chance. Econometrica J Econ Soc: 665–681 Gibbard A(1977) Manipulation of schemes that mix voting with chance. Econometrica J Econ Soc: 665–681
go back to reference Mennle T, Seuken S (2021) Partial strategyproofness: relaxing strategyproofness for the random assignment problem. J Econ Theory 191:105144CrossRef Mennle T, Seuken S (2021) Partial strategyproofness: relaxing strategyproofness for the random assignment problem. J Econ Theory 191:105144CrossRef
go back to reference Muto N, Sato S (2017) An impossibility under bounded response of social choice functions. Games Econ Behav 106:1–15CrossRef Muto N, Sato S (2017) An impossibility under bounded response of social choice functions. Games Econ Behav 106:1–15CrossRef
go back to reference Peters H, Roy S, Sen A, Storcken T (2014) Probabilistic strategy-proof rules over single-peaked domains. J Math Econ 52:123–127CrossRef Peters H, Roy S, Sen A, Storcken T (2014) Probabilistic strategy-proof rules over single-peaked domains. J Math Econ 52:123–127CrossRef
go back to reference Peters H, Roy S, Sadhukhan S, Storcken T (2017) An extreme point characterization of strategy-proof and unanimous probabilistic rules over binary restricted domains. J Math Econ 69:84–90CrossRef Peters H, Roy S, Sadhukhan S, Storcken T (2017) An extreme point characterization of strategy-proof and unanimous probabilistic rules over binary restricted domains. J Math Econ 69:84–90CrossRef
go back to reference Postlewaite A, Schmeidler D (1986) Strategic behaviour and a notion of ex ante efficiency in a voting model. Social Choice Welf 3:37–49CrossRef Postlewaite A, Schmeidler D (1986) Strategic behaviour and a notion of ex ante efficiency in a voting model. Social Choice Welf 3:37–49CrossRef
go back to reference Pycia M, Ünver MU (2015) Decomposing random mechanisms. J Math Econ 61:21–33CrossRef Pycia M, Ünver MU (2015) Decomposing random mechanisms. J Math Econ 61:21–33CrossRef
go back to reference Roy S, Sadhukhan S (2019) A characterization of random min-max domains and its applications. Econ Theory 68:887–906CrossRef Roy S, Sadhukhan S (2019) A characterization of random min-max domains and its applications. Econ Theory 68:887–906CrossRef
go back to reference Roy S, Sadhukhan S (2020) A unified characterization of the randomized strategy-proof rules. J Econ Theory:105131 Roy S, Sadhukhan S (2020) A unified characterization of the randomized strategy-proof rules. J Econ Theory:105131
go back to reference Roy S, Sadhukhan S, Sen A (2021) Recent results on strategy-proofness of random social choice functions. In: Game Theory and Networks. Springer, 63–87 Roy S, Sadhukhan S, Sen A (2021) Recent results on strategy-proofness of random social choice functions. In: Game Theory and Networks. Springer, 63–87
go back to reference Sato S (2013) A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one. J Econ Theory 148:259–278CrossRef Sato S (2013) A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one. J Econ Theory 148:259–278CrossRef
go back to reference Satterthwaite MA (1975) Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J Econ Theory 10:187–217CrossRef Satterthwaite MA (1975) Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J Econ Theory 10:187–217CrossRef
go back to reference Sen A (2011) The Gibbard random dictatorship theorem: A generalization and a new proof. SERIEs: J Span Econ Assoc 2:515–527 Sen A (2011) The Gibbard random dictatorship theorem: A generalization and a new proof. SERIEs: J Span Econ Assoc 2:515–527
go back to reference Von Neumann J (2016) A Certain Zero-sum Two-person Game Equivalent to the Optimal Assignment Problem. In: Volume II (ed) Contributions to the Theory of Games (AM-28). Princeton University Press, pp 5–12 Von Neumann J (2016) A Certain Zero-sum Two-person Game Equivalent to the Optimal Assignment Problem. In: Volume II (ed) Contributions to the Theory of Games (AM-28). Princeton University Press, pp 5–12
Metadata
Title
Stochastic same-sidedness in the random voting model
Authors
Sarvesh Bandhu
Abhinaba Lahiri
Anup Pramanik
Publication date
02-11-2023
Publisher
Springer Berlin Heidelberg
Published in
Social Choice and Welfare / Issue 1/2024
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-023-01491-1

Other articles of this Issue 1/2024

Social Choice and Welfare 1/2024 Go to the issue

Original Paper

Ties

Premium Partner