Random ballot

Last updated

A random ballot or random dictatorship is a randomized electoral system where the election is decided on the basis of a single randomly-selected ballot. [1] [2] A closely-related 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.

Contents

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 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), [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:

RD also satisfies a property called agenda consistency. It is the only rule satisfying the following properties: [9]

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, SD-efficiency and SD-strategyproofness are incompatible when there are at least 4 agents and 4 alternatives. [10]

RD satisfies an axiom called population consistency, and an axiom called cloning-consistency, 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):

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:

Randomness in other electoral systems

There are various other elements of randomness (other than tie-breaking) in existing electoral systems.

Order of listed candidates

It is often observed that candidates who are placed in a high position on the ballot-paper 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 Hare-Clark STV-PR 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 ballot-papers 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 ballot-papers are transferred but are marked down in value to 0.1666 (one-sixth) of a vote each. This means that 1,000 votes "stay with" the elected candidate, while the value of the 1,200 ballot-papers 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

Related Research Articles

<span class="mw-page-title-main">Arrow's impossibility theorem</span> Proof all ranked voting rules have spoilers

Arrow's impossibility theorem is a key result in social choice theory, showing that no ranking-based decision rule can satisfy the requirements of rational choice theory. Most notably, Arrow showed that no such rule can satisfy independence of irrelevant alternatives, the principle that a choice between two alternatives A and B should not depend on the quality of some third, unrelated option C.

Independence of irrelevant alternatives (IIA) is a major axiom of decision theory which codifies the intuition that a choice between and should not depend on the quality of a third, unrelated outcome . There are several different variations of this axiom, which are generally equivalent under mild conditions. As a result of its importance, the axiom has been independently rediscovered in various forms across a wide variety of fields, including economics, cognitive science, social choice, fair division, rational choice, artificial intelligence, probability, and game theory. It is closely tied to many of the most important theorems in these fields, including Arrow's impossibility theorem, the Balinski-Young theorem, and the money pump arguments.

The Gibbard–Satterthwaite theorem is a theorem in voting theory. It was first conjectured by the philosopher Michael Dummett and the mathematician Robin Farquharson in 1961 and then proved independently by the philosopher Allan Gibbard in 1973 and economist Mark Satterthwaite in 1975. It deals with deterministic ordinal electoral systems that choose a single winner, and shows that for every voting rule of this form, at least one of the following three things must hold:

  1. The rule is dictatorial, i.e. there exists a distinguished voter who can choose the winner; or
  2. The rule limits the possible outcomes to two alternatives only; or
  3. The rule is not straightforward, i.e. there is no single always-best strategy.
<span class="mw-page-title-main">May's theorem</span> Social choice theorem on superiority of majority voting

In social choice theory, May's theorem, also called the general possibility theorem, says that majority vote is the unique ranked social choice function between two candidates that satisfies the following criteria:

<span class="mw-page-title-main">Social choice theory</span> Academic discipline

Social choice theory is a branch of welfare economics that analyzes methods of combining individual opinions, beliefs, or preferences to reach a collective decision or create measures of social well-being. It contrasts with political science in that it is a normative field that studies how societies should make decisions, whereas political science is descriptive. Social choice incorporates insights from economics, mathematics, philosophy, political science, and game theory to find the best ways to combine individual preferences into a coherent whole, called a social welfare function.

Allan Fletcher Gibbard is the Richard B. Brandt Distinguished University Professor of Philosophy Emeritus at the University of Michigan, Ann Arbor. Gibbard has made major contributions to contemporary ethical theory, in particular metaethics, where he has developed a contemporary version of non-cognitivism. He has also published articles in the philosophy of language, metaphysics, and social choice theory: in social choice, he first proved the result known today as Gibbard-Satterthwaite theorem, which had been previously conjectured by Michael Dummett and Robin Farquharson.

In game theory, and particularly mechanism design, participation constraints or individual rationality constraints are said to be satisfied if a mechanism leaves all participants at least as well-off as they would have been if they hadn't participated.

<span class="mw-page-title-main">Ranked‐choice voting</span> Single-winner ranked-choice electoral system

Ranked-choice voting (RCV), preferential voting (PV), or the alternative vote (AV), is a multi-round elimination rule based on first-past-the-post. In academic contexts, the system is generally called instant-runoff voting (IRV) to avoid conflating it with other methods of ranked voting in general. The rule works by simulating a series of primary and runoff elections, where the last-place finisher according to a plurality vote is eliminated in each round. RCV falls under the pluralitarian family of voting methods and is most closely related to first-past-the-post and two-round rules like partisan and nonpartisan primaries.

<span class="mw-page-title-main">Dictatorship mechanism</span> Theoretical rule in social choice theory

In social choice theory, a dictatorship mechanism is a degenerate voting rule or mechanism where the result depends on only one person's preferences, without considering any other voters. A serial dictatorship is similar, but also designates a series of "backup dictators", who break ties in the original dictator's choices when the dictator is indifferent.

There are a number of different criteria which can be used for voting systems in an election, including the following

<span class="mw-page-title-main">Arunava Sen</span> Indian researcher and teacher

Arunava Sen is a professor of economics at the Indian Statistical Institute. He works on Game Theory, Social Choice Theory, Mechanism Design, Voting and Auctions.

<span class="mw-page-title-main">Maximal lotteries</span> Probabilistic Condorcet method

Maximal lotteries refers to a probabilistic voting rule. The method uses preferential ballots and returns a probability distribution of candidates that a majority of voters would weakly prefer to any other.

In economics, dichotomous preferences (DP) are preference relations that divide the set of alternatives to two subsets, "Good" and "Bad".

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

  1. The process is dictatorial, i.e. there is a single voter whose vote chooses the outcome.
  2. The process limits the possible outcomes to two options only.
  3. The process is not straightforward; the optimal ballot for a voter "requires strategic voting", i.e. it depends on their beliefs about other voters' ballots.
<span class="mw-page-title-main">Multiwinner approval voting</span> Family of proportional election methods

Multiwinner approval voting, sometimes also called approval-based committee (ABC) voting, refers to a family of multi-winner electoral systems that use approval ballots. Each voter may select ("approve") any number of candidates, and multiple candidates are elected.

<span class="mw-page-title-main">Fractional social choice</span>

Fractional, stochastic, or weighted social choice is a branch of social choice theory in which the collective decision is not a single alternative, but rather a weighted sum of two or more alternatives. For example, if society has to choose between three candidates, then in standard social choice exactly one of these candidates is chosen. By contrast, in fractional social choice it is possible to choose any linear combination of these, e.g. "2/3 of A and 1/3 of B".

<span class="mw-page-title-main">Fractional approval voting</span>

In fractional social choice, fractional approval voting refers to a class of electoral systems using approval ballots, in which the outcome is fractional: for each alternative j there is a fraction pj between 0 and 1, such that the sum of pj is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins and the other candidates lose. The fractions pj can be interpreted in various ways, depending on the setting. Examples are:

Budget-proposal aggregation (BPA) is a problem in social choice theory. A group has to decide on how to distribute its budget among several issues. Each group-member has a different idea about what the ideal budget-distribution should be. The problem is how to aggregate the different opinions into a single budget-distribution program.

The median voting rule or median mechanism is a rule for group decision-making along a one-dimensional domain. Each person votes by writing down his/her ideal value, and the rule selects a single value which is the median of all votes.

References

  1. ↑ 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.
  2. ↑ Zeckhauser, Richard (1973). "Voting Systems, Honest Preferences and Pareto Optimality". American Political Science Review. 67 (3): 938–940. doi:10.2307/1958635. ISSN   0003-0554. 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.
  3. ↑ Gibbard, Allan (1973). "Manipulation of Voting Schemes: A General Result". Econometrica. 41 (4): 592–593. doi:10.2307/1914083. ISSN   0012-9682. 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.
  4. ↑ 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 2006-08-31.
  5. ↑ Gibbard, Allan (1973). "Manipulation of Voting Schemes: A General Result". Econometrica. 41 (4): 587–601. doi:10.2307/1914083. ISSN   0012-9682. JSTOR   1914083.
  6. ↑ Akhil Reed Amar (1 January 1995). "Lottery Voting: A Thought Experiment".
  7. 1 2 Felix Brandt (2017-10-26). "Probabilistic Social Choice". In Endriss, Ulle (ed.). Trends in Computational Social Choice. Lulu.com. ISBN   978-1-326-91209-3.
  8. ↑ Gibbard, Allan (1977). "Manipulation of Schemes that Mix Voting with Chance". Econometrica. 45 (3): 665–681. doi:10.2307/1911681. hdl: 10419/220534 . ISSN   0012-9682. JSTOR   1911681.
  9. ↑ Pattanaik, Prasanta K.; Peleg, Bezalel (1986). "Distribution of Power under Stochastic Social Choice Rules". Econometrica. 54 (4): 909–921. doi:10.2307/1912843. ISSN   0012-9682. JSTOR   1912843.
  10. ↑ Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian (2018-01-31). "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   0004-5411. S2CID   1135734.
  11. 1 2 Aziz, Haris; Brandt, Felix; Brill, Markus (2013-12-01). "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   0165-1765. S2CID   14384249.
  12. ↑ Aziz, Haris; Mestre, Julián (2014-11-01). "Parametrized algorithms for random serial dictatorship". Mathematical Social Sciences. 72: 1–6. arXiv: 1403.0974 . doi:10.1016/j.mathsocsci.2014.07.002. ISSN   0165-4896. S2CID   6719832.
  13. ↑ Bogomolnaia, Anna; Moulin, Hervé; Stong, Richard (2005-06-01). "Collective choice under dichotomous preferences". Journal of Economic Theory. 122 (2): 165–184. doi:10.1016/j.jet.2004.05.005. ISSN   0022-0531.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.