A joint Politics and Economics series 
Social choice and electoral systems 


A random ballot or random dictatorship is a randomized electoral system where the election is decided on the basis of a single randomlyselected ballot.^{[1]}^{[2]} A closelyrelated variant is called random serial (or sequential) dictatorship, which repeats the procedure and draws another ballot if multiple candidates are tied on the first ballot.
Random dictatorship was first described in 1977 by Allan Gibbard, who showed it to be the unique social choice rule that treats all voters equally while still being strategyproof in all situations.^{[3]} Its application to elections was first described in 1984 by Akhil Reed Amar.^{[4]}
The rule is rarely, if ever, proposed as a genuine electoral system, as such a method (in Gibbard's words) "leaves too much to chance".^{[5]} However, the rule is often used as a tiebreaker to encourage voters to cast honest ballots, and is sometimes discussed as a thought experiment.^{[6]}
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 multiconstituency 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),^{[7]}^{: 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.^{[8]} It says that RD is the only rule that satisfies the following three properties:
 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 stochastically dominated.
 Ex post Paretoefficiency: the outcome is Paretoefficient.
 In fact, with strict preferences, RD satisfies a stronger efficiency property called SDefficiency: the resulting lottery is not stochastically dominated. With weak preferences, RSD satisfies expost efficiency, but violates SDefficiency.
 Even with strict preferences, RD violates the stronger property called PCefficiency: the resulting lottery might be dominated in the sense of pairwisecomparisons (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:^{[9]}
 Strong contraction consistency ("regularity"): probabilities cannot decrease when removing arbitrary alternatives.
 Expost efficiency.
 A probabilistic version of independence of irrelevant alternatives.
Subsequent research have provided alternative proofs, as well as various extensions.^{[7]}^{: 15 } One impossibility result relates to extending the theorem to weak preferences. It says that, with weak preferences, the properties of anonymity, SDefficiency and SDstrategyproofness are incompatible when there are at least 4 agents and 4 alternatives.^{[10]}
RD satisfies an axiom called population consistency, and an axiom called cloningconsistency, but violates composition consistency.^{[clarification needed]}
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 #Phard;^{[11]}
 There is an efficient algorithm for computing the support (the alternatives chosen with a positive probability);^{[11]}
 There are algorithms with tractable parameterized complexity, where the parameters are: number of objects, number of alternatives, and number of voter types.^{[12]}
 There is an exponentialtime algorithm for computing the probabilities in the context of fractional approval voting.^{[13]}^{: Appendix }
For multimember bodies
If the random ballot is used to select the members of a multiconstituency 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 50person assembly, have a vanishingly small chance of winning a majority. Using the binomial distribution, the probability is given by:
Randomness in other electoral systems
There are various other elements of randomness (other than tiebreaking) in existing electoral systems.
Order of listed candidates
It is often observed that candidates who are placed in a high position on the ballotpaper will receive extra votes as a result, from voters who are apathetic (especially in elections with compulsory voting) or who have a strong preference for a party but are indifferent among individual candidates representing that party (when there are two or more). For this reason, many societies have abandoned traditional alphabetical listing of candidates on the ballot in favour of either ranking by the parties (e.g., the Australian Senate), placement by lot, or rotation (e.g. the HareClark STVPR system used in Tasmania and the Australian Capital Territory). When candidates are ordered by lot on the ballot, the advantage of donkey voting can be decisive in a close race.
Transfer votes
In some single transferable vote (STV) systems of proportional representation, an elected candidate's surplus of votes over and above the quota is transferred by selecting the required number of ballot papers at random. Thus, if the quota is 1,000 votes, a candidate who polls 1,200 first preference votes has a surplus of 200 votes that s/he does not need. In some STV systems (Ireland since 1922, and Australia from 1918 to 1984), electoral officials select 200 ballotpapers randomly from the 1,200. However, this has been criticised since it is not replicable if a recount is required. As a result, Australia has adopted a variant of fractional transfer, a.k.a. the "Gregory method", by which all 1,200 ballotpapers are transferred but are marked down in value to 0.1666 (onesixth) of a vote each. This means that 1,000 votes "stay with" the elected candidate, while the value of the 1,200 ballotpapers transferred equals only 200 votes.
Selecting winners
Sortition is a voting method which – rather than choosing ballots – chooses candidates directly by lot, with no input from the voters (except perhaps a nominating or screening process). This is not the same as random ballot, since random ballot is weighted in favor of candidates who receive more votes. Random ballot would behave identically to random winner only if all candidates received the same number of votes.
See also
References
 ^ Sewell, Roger; MacKay, David; McLean, Iain (January 2009). "Probabilistic electoral methods, representative probability, and maximum entropy". Voting Matters. 26: 22.
A voter is picked at random and the output ordering of the election is set to be the ordering given by that voter.
 ^ Zeckhauser, Richard (1973). "Voting Systems, Honest Preferences and Pareto Optimality". American Political Science Review. 67 (3): 938–940. doi:10.2307/1958635. ISSN 00030554. JSTOR 1958635. S2CID 147293110.
Each individual writes the name of a candidate on a ballot. The voters' ballots are collected and placed in a revolving drum. After shuffling, a ballot is chosen at random. The name on the chosen ballot is the elected candidate.
 ^ Gibbard, Allan (1973). "Manipulation of Voting Schemes: A General Result". Econometrica. 41 (4): 592–593. doi:10.2307/1914083. ISSN 00129682. JSTOR 1914083. S2CID 17069971.
In other words, each voter writes his first choice on a ballot; a single ballot is drawn at random; and the choice on that ballot is selected.
 ^ Akhil Reed Amar (June 1984). "Choosing representatives by lottery voting" (PDF). Yale Law Journal. 93 (7): 1283–1308. doi:10.2307/796258. JSTOR 796258. Archived from the original (PDF) on 20060831.
 ^ Gibbard, Allan (1973). "Manipulation of Voting Schemes: A General Result". Econometrica. 41 (4): 587–601. doi:10.2307/1914083. ISSN 00129682. JSTOR 1914083.
 ^ Akhil Reed Amar (1 January 1995). "Lottery Voting: A Thought Experiment".
 ^ ^{a} ^{b} Felix Brandt (20171026). "Probabilistic Social Choice". In Endriss, Ulle (ed.). Trends in Computational Social Choice. Lulu.com. ISBN 9781326912093.
 ^ Gibbard, Allan (1977). "Manipulation of Schemes that Mix Voting with Chance". Econometrica. 45 (3): 665–681. doi:10.2307/1911681. hdl:10419/220534. ISSN 00129682. JSTOR 1911681.
 ^ Pattanaik, Prasanta K.; Peleg, Bezalel (1986). "Distribution of Power under Stochastic Social Choice Rules". Econometrica. 54 (4): 909–921. doi:10.2307/1912843. ISSN 00129682. JSTOR 1912843.
 ^ Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian (20180131). "Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving". Journal of the ACM. 65 (2): 6:1–6:28. arXiv:1604.05692. doi:10.1145/3125642. ISSN 00045411. S2CID 1135734.
 ^ ^{a} ^{b} Aziz, Haris; Brandt, Felix; Brill, Markus (20131201). "The computational complexity of random serial dictatorship". Economics Letters. 121 (3): 341–345. arXiv:1304.3169. doi:10.1016/j.econlet.2013.09.006. ISSN 01651765. S2CID 14384249.
 ^ Aziz, Haris; Mestre, Julián (20141101). "Parametrized algorithms for random serial dictatorship". Mathematical Social Sciences. 72: 1–6. arXiv:1403.0974. doi:10.1016/j.mathsocsci.2014.07.002. ISSN 01654896. S2CID 6719832.
 ^ Bogomolnaia, Anna; Moulin, Hervé; Stong, Richard (20050601). "Collective choice under dichotomous preferences". Journal of Economic Theory. 122 (2): 165–184. doi:10.1016/j.jet.2004.05.005. ISSN 00220531.