Leximin order

In mathematics, the leximin order is a total preorder on finite-dimensional vectors. It is particularly important in fair division.[1][2][3]

Not to be confused with Lexis minima.

Description

A vector x = (x1, ..., xn) is leximin-larger than a vector y = (y1, ..., yn) if the smallest element of x is larger than the smallest element of y, or the smallest elements of both vectors are equal and the second-smallest element of x is larger than the second-smallest element of y, etc.

The definition implies that vectors with the same element are equivalent w.r.t. the leximin order, since they have the same smallest element, the same second-smallest element, etc. For example, the vectors (2,4) and (4,2) are leximin-equivalent. Both these vectors are leximin-larger than (1,9) and (9,1), since the smallest element is 2 in the former vectors and 1 in the latter vectors. These latter vectors are leximin-larger than (1,8) and (8,1), since their smallest element is the same (1) but their second-smallest element is larger (9 vs. 8).

Leximin allocation rule

The leximin order can be used as a rule for fair division of resources. In a typical resource allocation problem, there are several resources and several agents with different valuations of the resources. Each allocation of the resources to the agents induces a utility profile - a vector in which element i is the utility of agent i in the allocation. An allocation is called leximin-optimal if its utility-profile is (weakly) leximin-larger than the utility profile of all other allocations. For example, suppose there are three possible allocations: allocation x gives a utility of 2 to Alice and 4 to George; allocation y gives a utility of 9 to Alice and 1 to George; and allocation z gives a utility of 1 to Alice and 8 to George. Then allocation 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 leximin allocation rule selects, from among all possible allocations, the leximin-optimal ones.[1]

The leximin allocation rule is often called the egalitarian rule, as it corresponds to the egalitarian philosophy: it aims to maximize the happiness of the worst-off agent; subject to that, to maximize the happiness of the second worst-off agent; and so on. It is often called the Rawlsian rule, since it resembles the John Rawls' theory of justice.

Existence

Leximin-optimal allocations exist whenever the set of allocation is a compact space. This is always the case when allocating discrete objects (see fair item allocation). When allocating a finite number of continuous homogeneous resources, it is easy to prove that the set of allocations is compact. Dubins and Spanier proved that, with a continuous heterogeneous resource ("cake"), the set of allocations is compact.[4] Therefore, leximin-optimal cake allocations always exist. For this reason, the leximin cake-allocation rule is sometimes called the Dubins–Spanier rule.[5]

Properties

A leximin-optimal allocation is always Pareto-optimal (PO). This is because if an allocation y Pareto-dominates an allocation x, then y is also leximin-better than x.

When the agents' valuations are not normalized (i.e., different agents may assign a different value to the entire cake), there is a difference between the absolute utility profile of an allocation (where element i is just the utility of agent i), and its relative utility profile (where element i is the utility of agent i divided by the total value for agent i). The absolute leximin rule chooses an allocation in which the absolute utility profile is leximin-maximal, and the relative leximin rule chooses an allocation in which the relative utility profile is leximin-maximal. While both rules are PO, they differ in other properties. In the context of cake-cutting, the absolute leximin rule is resource monotonic and population monotonic but not proportional, while the relative-leximin rule is proportional and population-monotonic but not resource-monotonic.[6]

In the context of indivisible allocation of goods:

  • When all agents have identical valuations with nonzero marginal utilities, any (relative) leximin-optimal allocation is PO and EFX. An improvement of leximin called leximin++ guarantees EFX (but not PO) with general identical valuations.[7]
  • When all agents have valuations that are matroid rank functions (i.e., submodular with binary marginals), the set of leximin-optimal allocations is equivalent to the set of max-product allocations; all such allocations are max-sum and EF1.[8]
  • In general, a leximin-optimal allocation might not be even EF1, even with additive valuations. For example, suppose there are four goods and two agents who value them at {0,1,1,1} and {3,3,3,3}. The unique (absolute) leximin-optimal allocation gives {1,1,1} to the first agent and {3} to the second agent, but then the second agent envies.[8]:28

In the context of indivisible allocation of chores (items with negative utilities):

  • With 3 or 4 agents with additive valuations, any leximin-optimal allocation is PROP1 and PO; with n agents with general identical valuations, any leximin-optimal allocation is EFX.[9]

Applications

The leximin rule has been used for fairly allocating unused classrooms in public schools to charter schools.[10]

Computation

There are several efficient algorithms for computing leximin-optimal solutions in constraint networks.[11]

Leximin flow

The leximin order can be used as a rule for solving network flow problems. Given a flow network, a source s, a sink t, and a specified subset E of edges, a flow is called leximin-optimal (or decreasingly minimal) on E if it minimizes the largest flow on an edge of E, subject to this minimizes the second-largest flow, and so on. There is a polynomial-time algorithm for computing a cheapest leximin-optimal integer-valued flow of a given flow amount. It is a possible way to define a fair flow.[12]

References
  1. Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
  2. Barbarà, Salvador; Jackson, Matthew (1988-10-01). "Maximin, leximin, and the protective criterion: Characterizations and comparisons". Journal of Economic Theory. 46 (1): 34–44. doi:10.1016/0022-0531(88)90148-2. ISSN 0022-0531.
  3. Yager, Ronald R. (1997-10-01). "On the analytic representation of the Leximin ordering and its application to flexible constraint propagation". European Journal of Operational Research. 102 (1): 176–192. doi:10.1016/S0377-2217(96)00217-2. ISSN 0377-2217.
  4. Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68 (1): 1–17. doi:10.2307/2311357. JSTOR 2311357.
  5. Dall'Aglio, Marco (2001-05-01). "The Dubins–Spanier optimization problem in fair division theory". Journal of Computational and Applied Mathematics. 130 (1–2): 17–40. Bibcode:2001JCoAM.130...17D. doi:10.1016/S0377-0427(99)00393-3. ISSN 0377-0427.
  6. Segal-Halevi, Erel; Sziklai, Balázs R. (2019-09-01). "Monotonicity and competitive equilibrium in cake-cutting". Economic Theory. 68 (2): 363–401. arXiv:1510.05229. doi:10.1007/s00199-018-1128-6. ISSN 1432-0479. S2CID 179618.
  7. Plaut, Benjamin; Roughgarden, Tim (2020-01-01). "Almost Envy-Freeness with General Valuations". SIAM Journal on Discrete Mathematics. 34 (2): 1039–1068. arXiv:1707.04769. doi:10.1137/19M124397X. ISSN 0895-4801.
  8. Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). Finding Fair and Efficient Allocations When Valuations Don't Add Up. Lecture Notes in Computer Science. 12283. pp. 32–46. arXiv:2003.07060. doi:10.1007/978-3-030-57980-7_3. ISBN 978-3-030-57979-1. S2CID 208328700.
  9. Chen, Xingyu; Liu, Zijie (2020-05-11). "The Fairness of Leximin in Allocation of Indivisible Chores". arXiv:2005.04864 [cs.GT].
  10. Kurokawa, David; Procaccia, Ariel D.; Shah, Nisarg (2015-06-15). "Leximin Allocations in the Real World". Proceedings of the Sixteenth ACM Conference on Economics and Computation. EC '15. Portland, Oregon, USA: Association for Computing Machinery: 345–362. doi:10.1145/2764468.2764490. ISBN 978-1-4503-3410-5. S2CID 1060279.
  11. 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.
  12. Frank, András; Murota, Kazuo (2020-09-18). "Fair Integral Flows". arXiv:1907.02673 [math.CO].
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.