Maximal lotteries

Last updated

Maximal lotteries refers to a probabilistic voting rule. The method uses preferential ballots and returns a probability distribution (or linear combination) of candidates that a majority of voters would weakly prefer to any other. [1]

Contents

Maximal lotteries satisfy a wide range of desirable properties: they elect the Condorcet winner with probability 1 if it exists [1] and never elect candidates outside the Smith set. [1] Moreover, they satisfy reinforcement, [2] participation, [3] , and independence of clones [2] . The probabilistic voting rule that returns all maximal lotteries is the only rule satisfying reinforcement, Condorcet-consistency, and independence of clones. [2] The social welfare function that top-ranks maximal lotteries has been uniquely characterized using Arrow's independence of irrelevant alternatives and Pareto efficiency. [4]

Maximal lotteries do not satisfy the standard notion of strategyproofness, as Allan Gibbard has shown that only random dictatorships can satisfy strategyproofness and ex post efficiency. [5] Maximal lotteries are also nonmonotonic in probabilities, i.e. it is possible that the probability of an alternative decreases when a voter ranks this alternative up. [1] However, they satisfy relative monotonicity, i.e., the probability of relative to that of does not decrease when is improved over . [6]

The support of maximal lotteries, which is known as the essential set or the bipartisan set, has been studied in detail. [7] [8] [9] [10]

History

Maximal lotteries were first proposed by the French mathematician and social scientist Germain Kreweras in 1965 [11] and popularized by Peter Fishburn. [1] Since then, they have been rediscovered multiple times by economists, [8] mathematicians, [1] [12] political scientists, philosophers, [13] and computer scientists. [14]

Several natural dynamics that converge to maximal lotteries have been observed in biology, physics, chemistry, and machine learning. [15] [16] [17]

Collective preferences over lotteries

The input to this voting system consists of the agents' ordinal preferences over outcomes (not lotteries over alternatives), but a relation on the set of lotteries can be constructed in the following way: if and are lotteries over alternatives, if the expected value of the margin of victory of an outcome selected with distribution in a head-to-head vote against an outcome selected with distribution is positive. In other words, if it is more likely that a randomly selected voter will prefer the alternatives sampled from to the alternative sampled from than vice versa. [4] While this relation is not necessarily transitive, it does always admit at least one maximal element.

It is possible that several such maximal lotteries exist, as a result of ties. However, the maximal lottery is unique whenever there the number of voters is odd. [18] By the same argument, the bipartisan set is uniquely-defined by taking the support of the unique maximal lottery that solves a tournament game. [8]

Strategic interpretation

Maximal lotteries are equivalent to mixed maximin strategies (or Nash equilibria) of the symmetric zero-sum game given by the pairwise majority margins. As such, they have a natural interpretation in terms of electoral competition between two political parties [19] and be computer in polynomial-time via [linear programming].

Example

Suppose there are five voters who have the following preferences over three alternatives:

The pairwise preferences of the voters can be represented in the following skew-symmetric matrix, where the entry for row and column denotes the number of voters who prefer to minus the number of voters who prefer to .

This matrix can be interpreted as a zero-sum game and admits a unique Nash equilibrium (or minimax strategy) where , , . By definition, this is also the unique maximal lottery of the preference profile above. The example was carefully chosen not to have a Condorcet winner. Many preference profiles admit a Condorcet winner, in which case the unique maximal lottery will assign probability 1 to the Condorcet winner. If the last voter in the example above swaps alternatives and in his preference relation, becomes the Condorcet winner and will be selected with probability 1.

Related Research Articles

<span class="mw-page-title-main">Approval voting</span> Single-winner electoral system

Approval voting is a single-winner electoral system in which voters mark all the candidates they support, instead of just choosing one. The candidate with the highest approval rating is elected.

In social choice theory, a Condorcet paradox is a situation where majority rule behaves in a way that is self-contradictory. In such a situation, every possible choice is rejected by the electorate in favor of another, because there is always some other outcome that a majority of voters consider to be better.

<span class="mw-page-title-main">Condorcet method</span> Pairwise-comparison electoral system

A Condorcet method is an election method that elects the candidate who wins a majority of the vote in every head-to-head election against each of the other candidates, whenever there is such a candidate. A candidate with this property, the pairwise champion or beats-all winner, is formally called the Condorcet winner. The head-to-head elections need not be done separately; a voter's choice within any given pair can be determined from the ranking.

In economics, utility is a measure of the satisfaction that a certain person has from a certain state of the world. Over time, the term has been used in at least two different meanings.

Arrow's impossibility theorem is a key result in social choice showing that no rank-order method for collective decision-making can behave rationally or coherently. Specifically, any such rule violates independence of irrelevant alternatives, the principle that a choice between and should not depend on the quality of a third, unrelated option .

Independence of irrelevant alternatives (IIA), also known as binary independence, the independence axiom, is an axiom of decision theory and economics describing a necessary condition for rational behavior. The axiom says that a choice between and should not depend on the quality of a third, unrelated outcome .

In an election, a candidate is called a majority winner or majority-preferred candidate if more than half of all voters would support them in a one-on-one race against any one of their opponents. Voting systems where a majority winner will always win are said to satisfy the majority-rule principle, because they extend the principle of majority rule to elections with multiple candidates.

<span class="mw-page-title-main">Tournament (graph theory)</span> Directed graph where each vertex pair has one arc

In graph theory, a tournament is a directed graph with exactly one edge between each two vertices, in one of the two possible directions. Equivalently, a tournament is an orientation of an undirected complete graph. The name tournament comes from interpreting the graph as the outcome of a round-robin tournament, a game where each player is paired against every other exactly once. In a tournament, the vertices represent the players, and the edges between players point from the winner to the loser.

In voting systems, the Minimax Condorcet method is a single-winner ranked-choice voting method that always elects the majority (Condorcet) winner. Minimax compares all candidates against each other in a round-robin tournament, then ranks candidates by their worst election result. The candidate with the largest (maximum) number of votes in their worst (minimum) matchup is declared the winner.

Pairwise comparison generally is any process of comparing entities in pairs to judge which of each entity is preferred, or has a greater amount of some quantitative property, or whether or not the two entities are identical. The method of pairwise comparison is used in the scientific study of preferences, attitudes, voting systems, social choice, public choice, requirements engineering and multiagent AI systems. In psychology literature, it is often referred to as paired comparison.

The Kemeny–Young method is an electoral system that uses ranked ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice.

In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single predetermined 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.

In decision theory, the von Neumann–Morgenstern (VNM) utility theorem shows that, under certain axioms of rational behavior, a decision-maker faced with risky (probabilistic) outcomes of different choices will behave as if they are maximizing the expected value of some function defined over the potential outcomes at some specified point in the future. This function is known as the von Neumann–Morgenstern utility function. The theorem is the basis for expected utility theory.

In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality of preference aggregation rules, such as voting rules. It is an indicator of the extent to which an aggregation rule can yield well-defined choices.

<span class="mw-page-title-main">Tournament solution</span>

A tournament solution is a function that maps an oriented complete graph to a nonempty subset of its vertices. It can informally be thought of as a way to find the "best" alternatives among all of the alternatives that are "competing" against each other in the tournament. Tournament solutions originate from social choice theory, but have also been considered in sports competition, game theory, multi-criteria decision analysis, biology, webpage ranking, and dueling bandit problems.

A major branch of social choice theory is devoted to the comparison of electoral systems, otherwise known as social choice functions. Viewed from the perspective of political science, electoral systems are rules for conducting elections and determining winners from the ballots cast. From the perspective of economics, mathematics, and philosophy, a social choice function is a mathematical function that determines how a society should make choices, given a collection of individual preferences.

A jury theorem is a mathematical theorem proving that, under certain assumptions, a decision attained using majority voting in a large group is more likely to be correct than a decision attained by a single expert. It serves as a formal argument for the idea of wisdom of the crowd, for decision of questions of fact by jury trial, and for democracy in general.

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".

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:

Lexicographic dominance is a total order between random variables. It is a form of stochastic ordering. It is defined as follows. Random variable A has lexicographic dominance over random variable B if one of the following holds:

References

  1. 1 2 3 4 5 6 P. C. Fishburn. Probabilistic social choice based on simple voting comparisons. Review of Economic Studies, 51(4):683–692, 1984.
  2. 1 2 3 F. Brandl, F. Brandt, and H. G. Seedig. Consistent probabilistic social choice. Econometrica. 84(5), pages 1839-1880, 2016.
  3. ↑ F. Brandl, F. Brandt, and J. Hofbauer. Welfare Maximization Entices Participation. Games and Economic Behavior. 14, pages 308-314, 2019.
  4. 1 2 F. Brandl and F. Brandt. Arrovian Aggregation of Convex Preferences. Econometrica. 88(2), pages 799-844, 2020.
  5. ↑ 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.
  6. ↑ Brandl, Florian; Brandt, Felix; Stricker, Christian (2022-01-01). "An analytical and experimental comparison of maximal lottery schemes". Social Choice and Welfare. 58 (1): 5–38. doi:10.1007/s00355-021-01326-x. hdl: 10419/286729 . ISSN   1432-217X.
  7. ↑ B. Dutta and J.-F. Laslier. Comparison functions and choice correspondences. Social Choice and Welfare, 16: 513–532, 1999.
  8. 1 2 3 G. Laffond, J.-F. Laslier, and M. Le Breton. The bipartisan set of a tournament game. Games and Economic Behavior, 5(1):182–201, 1993.
  9. ↑ Laslier, J.-F. Tournament solutions and majority voting Springer-Verlag, 1997.
  10. ↑ F. Brandt, M. Brill, H. G. Seedig, and W. Suksompong. On the structure of stable tournament solutions. Economic Theory, 65(2):483–507, 2018.
  11. ↑ G. Kreweras. Aggregation of preference orderings. In Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1–27 July 1960) and of Gösing, Austria (3–27 July 1962), pages 73–79, 1965.
  12. ↑ D. C. Fisher and J. Ryan. Tournament games and positive tournaments. Journal of Graph Theory, 19(2):217–236, 1995.
  13. ↑ D. S. Felsenthal and M. Machover. After two centuries should Condorcet’s voting procedure be implemented? Behavioral Science, 37(4):250–274, 1992.
  14. ↑ R. L. Rivest and E. Shen. An optimal single-winner preferential voting system based on game theory. In Proceedings of 3rd International Workshop on Computational Social Choice, pages 399–410, 2010.
  15. ↑ B. Laslier and J.-F. Laslier. Reinforcement learning from comparisons: Three alternatives are enough, two are not. Annals of Applied Probability 27(5): 2907–2925, 2017.
  16. ↑ Jacopo Grilli, György Barabás, Matthew J. Michalska-Smith and Stefano Allesina. Higher-order interactions stabilize dynamics in competitive network models. Nature 548: 210-214, 2017.
  17. ↑ F. Brandl and F. Brandt. A Natural Adaptive Process for Collective Decision-Making. Theoretical Economics 19(2): 667–703, 2024.
  18. ↑ Gilbert Laffond, Jean-François Laslier and Michel Le Breton A theorem on two–player symmetric zero–sum games. Journal of Economic Theory 72: 426–431, 1997.
  19. ↑ Laslier, J.-F. Interpretation of electoral mixed strategies. Social Choice and Welfare 17: pages 283–292, 2000.
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.