Egalitarian rule

In social choice and operations research, the egalitarian rule (also called the max-min rule or the Rawlsian rule) is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the minimum utility of all individuals in society. It is a formal mathematical representation of the egalitarian philosophy. It also corresponds to John Rawls' principle of maximizing the welfare of the worst-off individual.^[1]

Definition

Let $X$ be a set of possible `states of the world' or `alternatives'. Society wishes to choose a single state from $X$ . For example, in a single-winner election, $X$ may represent the set of candidates; in a resource allocation setting, $X$ may represent all possible allocations.

Let $I$ be a finite set, representing a collection of individuals. For each $i\in I$ , let $u_{i}:X\longrightarrow \mathbb {R}$ be a utility function, describing the amount of happiness an individual i derives from each possible state.

A social choice rule is a mechanism which uses the data $(u_{i})_{i\in I}$ to select some element(s) from $X$ which are `best' for society. The question of what 'best' means is the basic question of social choice theory. The egalitarian rule selects an element $x\in X$ which maximizes the minimum utility, that is, it solves the following optimization problem:

\max _{x\in X}\min _{i\in I}u_{i}(x).

Leximin rule

Often, there are many different states with the same minimum utility. For example, a state with utility profile (0,100,100) has the same minimum value as a state with utility profile (0,0,0). In this case, the egalitarian rule often uses the leximin order, that is: subject to maximizing the smallest utility, it aims to maximize the next-smallest utility; subject to that, maximize the next-smallest utility, and so on.

For example, suppose there are two individuals - Alice and George, and three possible states: state x gives a utility of 2 to Alice and 4 to George; state y gives a utility of 9 to Alice and 1 to George; and state z gives a utility of 1 to Alice and 8 to George. Then state x is leximin-optimal, since its utility profile is (2,4) which is leximin-larger than that of y (9,1) and z (1,8).

The egalitarian rule strengthened with the leximin order is often called the leximin rule, to distinguish it from the simpler max-min rule.

The leximin rule for social choice was introduced by Amartya Sen in 1970,^[1] and discussed in depth in many later books.^[2]^[3]^[4]^[5]^: sub.2.5 ^[6]

Properties

Pareto inefficiency

The leximin rule is Pareto-efficient if the outcomes of every decision are known with perfect certainty. However, by Harsanyi's utilitarian theorem, any leximin function is Pareto-inefficient for a society that must make tradeoffs under uncertainty: There exist situations in which every person in a society would be better-off (ex ante) if they were to take a particular bet, but the leximin rule will reject it (because some person might be made worse off ex post).

Pigou-Dalton property

The leximin rule satisfies the Pigou–Dalton principle, that is: if utility is "moved" from an agent with more utility to an agent with less utility, and as a result, the utility-difference between them becomes smaller, then resulting alternative is preferred.

Moreover, the leximin rule is the only social-welfare ordering rule which simultaneously satisfies the following three properties:^[5]^: 266

Pareto efficiency;
Pigou-Dalton principle;
Independence of common utility pace - if all utilities are transformed by a common monotonically-increasing function, then the ordering of the alternatives remains the same.

Egalitarian resource allocation

The egalitarian rule is particularly useful as a rule for fair division. In this setting, the set $X$ represents all possible allocations, and the goal is to find an allocation which maximizes the minimum utility, or the leximin vector. This rule has been studied in several contexts:

Division of a single homogeneous resource;
Fair subset sum problem;^[7]
Egalitarian cake-cutting;
Egalitarian item allocation.
Egalitarian (leximin) bargaining.^[8]

References

^ ^a ^b Sen, Amartya (2017-02-20). Collective Choice and Social Welfare. Harvard University Press. doi:10.4159/9780674974616. ISBN 978-0-674-97461-6.
^ D'Aspremont, Claude; Gevers, Louis (1977). "Equity and the Informational Basis of Collective Choice". The Review of Economic Studies. 44 (2): 199–209. doi:10.2307/2297061. ISSN 0034-6527. JSTOR 2297061.
^ Kolm, Serge-Christophe (2002). Justice and Equity. MIT Press. ISBN 978-0-262-61179-4.
^ Moulin, Herve (1991-07-26). Axioms of Cooperative Decision Making. Cambridge University Press. ISBN 978-0-521-42458-5.
^ ^a ^b Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
^ Bouveret, Sylvain; Lemaître, Michel (2009-02-01). "Computing leximin-optimal solutions in constraint networks". Artificial Intelligence. 173 (2): 343–364. doi:10.1016/j.artint.2008.10.010. ISSN 0004-3702.
^ Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2017-03-16). "Price of Fairness for allocating a bounded resource". European Journal of Operational Research. 257 (3): 933–943. arXiv:1508.05253. doi:10.1016/j.ejor.2016.08.013. ISSN 0377-2217. S2CID 14229329.
^ Imai, Haruo (1983). "Individual Monotonicity and Lexicographic Maxmin Solution". Econometrica. 51 (2): 389–401. doi:10.2307/1911997. ISSN 0012-9682. JSTOR 1911997.

[:0-1] Sen, Amartya (2017-02-20). Collective Choice and Social Welfare. Harvard University Press. doi:10.4159/9780674974616. ISBN 978-0-674-97461-6.

[2] D'Aspremont, Claude; Gevers, Louis (1977). "Equity and the Informational Basis of Collective Choice". The Review of Economic Studies. 44 (2): 199–209. doi:10.2307/2297061. ISSN 0034-6527. JSTOR 2297061.

[3] Kolm, Serge-Christophe (2002). Justice and Equity. MIT Press. ISBN 978-0-262-61179-4.

[4] Moulin, Herve (1991-07-26). Axioms of Cooperative Decision Making. Cambridge University Press. ISBN 978-0-521-42458-5.

[moulin-5] Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.

[6] Bouveret, Sylvain; Lemaître, Michel (2009-02-01). "Computing leximin-optimal solutions in constraint networks". Artificial Intelligence. 173 (2): 343–364. doi:10.1016/j.artint.2008.10.010. ISSN 0004-3702.

[:2-7] Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2017-03-16). "Price of Fairness for allocating a bounded resource". European Journal of Operational Research. 257 (3): 933–943. arXiv:1508.05253. doi:10.1016/j.ejor.2016.08.013. ISSN 0377-2217. S2CID 14229329.

[8] Imai, Haruo (1983). "Individual Monotonicity and Lexicographic Maxmin Solution". Econometrica. 51 (2): 389–401. doi:10.2307/1911997. ISSN 0012-9682. JSTOR 1911997.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]