Random Dictatorship

In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies ''unrestricted domain'', ''Pareto efficiency'', and ''independence of irrelevant alternatives''. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only ''strategyproof'' rule.

Non-dictatorship is a property of more common voting rules, in which the results are influenced by the preferences of all individuals. This property is satisfied if there is no single voter ''i'' with the individual preference order P, such that P is always the societal ("winning") preference order. In other words, the preferences of individual ''i'' should not always prevail. Anonymous voting systems (with at least two voters) automatically satisfy the non-dictatorship property.

The dictatorship rule has variants that are useful in practice: ''serial dictatorship'', ''random dictatorship'', and ''random serial dictatorship'' (see below).

Formal definition

Non-dictatorship is one of the necessary conditions in Arrow's impossibility theorem. In ''Social Choice and Individual Values'', Kenneth Arrow defines non-dictatorship as:
:There is no voter ''i'' in such that, for every set of orderings in the domain of the constitution, and every pair of social states ''x'' and ''y'', ''x $P_i$ y'' implies ''x P y''.
Naturally, dictatorship is a rule that does not satisfy non-dictatorship.

Serial dictatorship

A dictatorship mechanism is well-defined only when the dictator has a single best-preferred option. When the dictator is indifferent between two or more best-preferred options, it is possible to choose one of them arbitrarily/randomly, but this will not be Pareto efficient. A more efficient solution is to appoint a second dictator, who has a right to choose, from among all the first dictator's best options, the one that they most prefer. If the second dictator is also indifferent between two or more options, then a third dictator chooses among them, and so on. This rule is called serial dictatorship. Another name for it is priority mechanism.

The priority mechanism is often used in problems of house allocation. For example, when allocating dormitory rooms to students, it is common to order the students by a pre-specified priority order (e.g. by age, grades, distance, etc.), and let each of them in turn choose their most preferred rooms from the available ones.

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), 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. It says that, when preferences are strict, RD is the only rule that satisfies the following three properties:

* Anonymity: the lottery does not discriminate in advance between different voters.
*Strong SD-strategyproofness: every false report by an agent results in an outcome that is weakly stochastically dominated.
*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:

* 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. 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. The proof was derived using an SMT solver and verified by an interactive theorem prover Isabelle/HOL.

RD satisfies an axiom called ''population consistency'', and an axiom called ''cloning-consistency'', but violates ''composition consistency''.

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-hard;
* There is an efficient algorithm for computing the support (the alternatives chosen with a positive probability);
* There are algorithms with tractable parameterized complexity, where the parameters are: number of objects, number of alternatives, and number of voter types.
*There is an exponential-time algorithm for computing the probabilities in the context of fractional approval voting.{{Rp, Appendix

References

Voting theory
Dictatorship
Social choice theory