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).
Non-dictatorship is one of the necessary conditions in Arrow's impossibility theorem. [1] In Social Choice and Individual Values , Kenneth Arrow defines non-dictatorship as:
Naturally, dictatorship is a rule that does not satisfy non-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. [2] : 6 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.
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), [2] : 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.
Allan Gibbard proved the random dictatorship theorem. [3] It says that, when preferences are strict, 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: [4]
Subsequent research have provided alternative proofs, as well as various extensions. [2] : 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. The proof was derived using an SMT solver and verified by an interactive theorem prover Isabelle/HOL. [5]
RD satisfies an axiom called population consistency, and an axiom called cloning-consistency, but violates composition consistency.
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):
Arrow's impossibility theorem, the general possibility theorem or Arrow's paradox is an impossibility theorem in social choice theory that states that when voters have three or more distinct alternatives (options), no ranked voting electoral system can convert the ranked preferences of individuals into a community-wide ranking while also meeting the specified set of criteria: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives. The theorem is often cited in discussions of voting theory as it is further interpreted by the Gibbard–Satterthwaite theorem. The theorem is named after economist and Nobel laureate Kenneth Arrow, who demonstrated the theorem in his doctoral thesis and popularized it in his 1951 book Social Choice and Individual Values. The original paper was titled "A Difficulty in the Concept of Social Welfare".
The independence of irrelevant alternatives (IIA), also known as binary independence or the independence axiom, is an axiom of decision theory and the social sciences that describes a necessary condition for rational behavior. The axiom says that adding "pointless" (rejected) options should not affect behavior. This is sometimes explained with a short story by philosopher Sidney Morgenbesser:
Morgenbesser, ordering dessert, is told by a waitress that he can choose between blueberry or apple pie. He orders apple. Soon the waitress comes back and explains cherry pie is also an option. Morgenbesser replies "In that case, I'll have blueberry."
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. It states that for every voting rule, one of the following three things must hold:
The random ballot, single stochastic vote, or lottery voting is an electoral system in which an election is decided on the basis of a single randomly selected ballot.
The liberal paradox, also Sen paradox or Sen's paradox, is a logical paradox proposed by Amartya Sen which shows that no means of aggregating individual preferences into a single, social choice, can simultaneously fulfill the following, seemingly mild conditions:
Kenneth Arrow's monograph Social Choice and Individual Values and a theorem within it created modern social choice theory, a rigorous melding of social ethics and voting theory with an economic flavor. Somewhat formally, the "social choice" in the title refers to Arrow's representation of how social values from the set of individual orderings would be implemented under the constitution. Less formally, each social choice corresponds to the feasible set of laws passed by a "vote" under the constitution even if not every individual voted in favor of all the laws.
In social choice theory, unrestricted domain, or universality, is a property of social welfare functions in which all preferences of all voters are allowed. Intuitively, unrestricted domain is a common requirement for social choice functions, and is a condition for Arrow's impossibility theorem.
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.
Maximal lotteries refers to a probabilistic voting system first considered by the French mathematician and social scientist Germain Kreweras in 1965. The method uses preferential ballots and returns so-called maximal lotteries, i.e., probability distributions over the alternatives that are weakly preferred to any other probability distribution. Maximal lotteries satisfy the Condorcet criterion, the Smith criterion, polynomial runtime, and probabilistic versions of reinforcement, participation, and independence of clones.
Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.
In economics, dichotomous preferences (DP) are preference relations that divide the set of alternatives to two subsets: "Good" versus "Bad".
Fair random assignment is a kind of a fair division problem.
Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.
A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).
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:
Fractional 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: A B or C, then in standard social choice, exactly one of these candidates is chosen, while in fractional social choice, it is possible to choose "2/3 of A and 1/3 of B". A common interpretation of the weighted sum is as a lottery, in which candidate A is chosen with probability 2/3 and candidate B is chosen with probability 1/3. Due to this interpretation, fractional social choice is also called random social choice, probabilistic social choice, or stochastic social choice. But it can also be interpreted as a recipe for sharing, for example:
Fractional approval voting is an electoral system 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:
A school-choice mechanism is an algorithm that aims to match pupils to schools in a way that respects both the pupils' preferences and the schools' priorities. It is used to automate the process of school choice. The most common school-choice mechanisms are variants of the deferred-acceptance algorithm and random serial dictatorship.
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 is a rule for group decision-making along a one-dimesional spectrum. An example is members of a city-council who have to decide on the total amount of annual city budget. Another example is several people working in the same office who have to decide on the air-conditioning temperature. Each member has in mind an ideal amount, and prefers the actual amount to be as close as possible to his peak.
