Editing Random ballot (section)

== Random dictatorship and random serial dictatorship ==
The dictatorship rule is obviously unfair, but it has a variant that is fair in expectation. In the '''random dictatorship (RD)''' rule,  one of the voters is selected uniformly at random, and the alternative most preferred by that voter is selected. This is one of the common rules for [[random social choice]]. When used in multi-constituency bodies, it is sometimes called [[random ballot]].

Similarly to dictatorship, random dictatorship too should handle the possibility of indifferences; the common solution is to extend it to '''random serial dictatorship (RSD),'''<ref name=":0">{{Cite book |last=Felix Brandt |title=Trends in Computational Social Choice |date=2017-10-26 |publisher=Lulu.com |isbn=978-1-326-91209-3 |editor-last=Endriss |editor-first=Ulle |language=en |chapter=Probabilistic Social Choice |chapter-url=https://books.google.com/books?id=0qY8DwAAQBAJ&dq=multiwinner++voting+a+new+challenge&pg=PA27}}</ref>{{Rp|6}} also called '''random priority'''. In this mechanism, a [[random permutation]] of the voters is selected, and each voter in turn narrows the existing alternatives to the ones they most prefer, from the ones still available. It is a common mechanism in allocating indivisible objects among agents; see [[random priority item allocation]].

===Properties===
[[Allan Gibbard]] proved the '''random dictatorship theorem'''.<ref>{{Cite journal |last=Gibbard |first=Allan |date=1977 |title=Manipulation of Schemes that Mix Voting with Chance |url=https://www.jstor.org/stable/1911681 |journal=Econometrica |volume=45 |issue=3 |pages=665–681 |doi=10.2307/1911681 |issn=0012-9682 |jstor=1911681 |hdl-access=free |hdl=10419/220534}}</ref> It says that RD is the only rule that satisfies the following three properties:

* [[Anonymity (social choice)|'''Anonymity''']]: the lottery does not discriminate in advance between different voters.
* '''[[Strategyproofness]]''': any false report by an agent results in an outcome that is weakly [[Stochastic dominance|stochastically dominated]].
* [[Pareto-efficiency|'''Ex post Pareto-efficiency''']]: the outcome is Pareto-efficient.
** In fact, with strict preferences, RD satisfies a stronger efficiency property called ''SD-efficiency'': the resulting lottery is not stochastically dominated. With weak preferences, RSD satisfies ex-post efficiency, but violates SD-efficiency.
** Even with strict preferences, RD violates the stronger property called PC-efficiency: the resulting lottery might be dominated in the sense of pairwise-comparisons (for each agent, the probability that another lottery yields a better alternative than the RD lottery is larger than the other way around).

RD also satisfies a property called agenda consistency. It is the only rule satisfying the following properties:<ref>{{Cite journal |last1=Pattanaik |first1=Prasanta K. |last2=Peleg |first2=Bezalel |date=1986 |title=Distribution of Power under Stochastic Social Choice Rules |url=https://www.jstor.org/stable/1912843 |journal=Econometrica |volume=54 |issue=4 |pages=909–921 |doi=10.2307/1912843 |issn=0012-9682 |jstor=1912843|url-access=subscription }}</ref>

* Strong contraction consistency ("regularity"): probabilities cannot decrease when removing arbitrary alternatives.
* Ex-post efficiency.
* A probabilistic version of [[independence of irrelevant alternatives]].

Subsequent research have provided alternative proofs, as well as various extensions.<ref name=":0" />{{Rp|15}} One impossibility result relates to extending the theorem to weak preferences. It says that, with weak preferences, the properties of anonymity, SD-efficiency and SD-strategyproofness are incompatible when there are at least 4 agents and 4 alternatives.<ref>{{Cite journal |last1=Brandl |first1=Florian |last2=Brandt |first2=Felix |last3=Eberl |first3=Manuel |last4=Geist |first4=Christian |date=2018-01-31 |title=Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving |url=https://doi.org/10.1145/3125642 |journal=Journal of the ACM |volume=65 |issue=2 |pages=6:1–6:28 |arxiv=1604.05692 |doi=10.1145/3125642 |issn=0004-5411 |s2cid=1135734}}</ref>

RD satisfies an axiom called ''population consistency'', and an axiom called ''cloning-consistency'', but violates ''composition consistency''.{{Clarify|reason=What is composition consistency?|date=July 2024}}

=== Computation ===
It is easy to implement both the RD and the RSD mechanisms in practice: just pick a random voter, or a random permutation, and let each dictator in turn pick the best option. However, sometimes one wants to compute in advance, what is the probability that a certain alternative would be chosen. With RD (when the preferences are strict), this is easy too: the probability that alternative ''x'' is chosen equals the number of voters who rank ''x'' first, divided by the total number of voters. But the situation is different with RSD (when there are indifferences):

* Computing the probabilities is [[♯P|#P]]-hard;<ref name=":1">{{Cite journal |last1=Aziz |first1=Haris |last2=Brandt |first2=Felix |last3=Brill |first3=Markus |date=2013-12-01 |title=The computational complexity of random serial dictatorship |url=https://www.sciencedirect.com/science/article/abs/pii/S0165176513004138 |journal=Economics Letters |language=en |volume=121 |issue=3 |pages=341–345 |arxiv=1304.3169 |doi=10.1016/j.econlet.2013.09.006 |issn=0165-1765 |s2cid=14384249}}</ref>
* There is an efficient algorithm for computing the support (the alternatives chosen with a positive probability);<ref name=":1" />
* There are algorithms with tractable [[parameterized complexity]], where the parameters are: number of objects, number of alternatives, and number of voter types.<ref>{{Cite journal |last1=Aziz |first1=Haris |last2=Mestre |first2=Julián |date=2014-11-01 |title=Parametrized algorithms for random serial dictatorship |url=https://www.sciencedirect.com/science/article/abs/pii/S0165489614000584 |journal=Mathematical Social Sciences |language=en |volume=72 |pages=1–6 |arxiv=1403.0974 |doi=10.1016/j.mathsocsci.2014.07.002 |issn=0165-4896 |s2cid=6719832}}</ref>
* There is an exponential-time algorithm for computing the probabilities in the context of [[fractional approval voting]].<ref name=":02">{{Cite journal |last1=Bogomolnaia |first1=Anna |last2=Moulin |first2=Hervé |last3=Stong |first3=Richard |date=2005-06-01 |title=Collective choice under dichotomous preferences |url=https://www.sciencedirect.com/science/article/abs/pii/S0022053104001322 |journal=Journal of Economic Theory |language=en |volume=122 |issue=2 |pages=165–184 |doi=10.1016/j.jet.2004.05.005 |issn=0022-0531}}</ref>{{Rp|Appendix}}

===For multimember bodies===
If the random ballot is used to select the members of a multi-constituency body, it can create a kind of [[proportional representation]] on average across elections. If the winner of each race is chosen randomly, then as the number of seats in a legislature grows, the percentage representation of each party in the elected body will get closer and closer to their actual proportion of the vote across the entire electorate. At the same time, the chance of a randomly selected highly unrepresentative body diminishes.

For example, say a minority party has 1% of the vote. This party would, in a 50-person assembly, have a vanishingly small chance of winning a majority. Using the [[binomial distribution]], the probability is given by:

:<math> \sum_{k=0}^{24} {50 \choose k} \left(\frac{99}{100}\right)^k\left(\frac{1}{100}\right)^{50-k} = I_{1/100}(26, 25) \approx 10^{-38} </math>