leximin order

A vector x = (x₁, ..., x_n) is leximin-larger than a vector y = (y₁, ..., y_n) if one of the following holds:

• The smallest element of x is larger than the smallest element of y;
• The smallest elements of both vectors are equal, and the second-smallest element of x is larger than the second-smallest element of y;
• ...
• The k smallest elements of both vectors are equal, and the (k+1)-smallest element of x is larger than the (k+1)-smallest element of y.

The vector (3,5,3) is leximin-larger than (4,2,4), since the smallest element in the former is 3 and in the latter is 2. The vector (4,2,4) is leximin-larger than (5,3,2), since the smallest elements in both are 2, but the second-smallest element in the former is 4 and in the latter is 3.

Vectors with the same multiset of elements are equivalent w.r.t. the leximin preorder, since they have the same smallest element, the same second-smallest element, etc. For example, the vectors (4,2,4) and (2,4,4) are leximin-equivalent (but both are leximin-larger than (2,4,2)).

In the lexicographic order, the first comparison is between x₁ and y₁, regardless of whether they are smallest in their vectors. The second comparison is between x₂ and y₂, and so on.

For example, the vector (3,5,3) is lexicographically smaller than (4,2,4), since the first element in the former is 3 and in the latter it is 4. Similarly, (4,2,4) is lexicographically larger than (2,4,4).

The following algorithm can be used to compute whether x is leximin-larger than y:

• Let x' be a vector containing the same elements of x but in ascending order;
• Let y' be a vector containing the same elements of y but in ascending order;
• Return "true" iff x' is lexicographically-larger than y'.

The leximax order is similar to the leximin order except that the first comparison is between the largest elements; the second comparison is between the second-largest elements; and so on.

In social choice theory,{{Cite book|last=Sen|first=Amartya|url=https://www.degruyter.com/document/doi/10.4159/9780674974616/html|title=Collective Choice and Social Welfare|date=2017-02-20|publisher=Harvard University Press|isbn=978-0-674-97461-6|language=en|doi=10.4159/9780674974616}} particularly in fair division, the leximin order is one of the orders used to choose between alternatives. In a typical social choice problem, society has to choose among several alternatives (for example: several ways to allocate a set of resources). Each alternative induces a utility profile - a vector in which element i is the utility of agent i in the allocation. An alternative is called leximin-optimal if its utility-profile is (weakly) leximin-larger than the utility profile of all other alternatives.

For example, suppose there are three alternatives: x gives a utility of 2 to Alice and 4 to George; y gives a utility of 9 to Alice and 1 to George; and z gives a utility of 1 to Alice and 8 to George. Then alternative 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-optimal solution is always Pareto-efficient.

The leximin rule selects, from among all possible allocations, the leximin-optimal ones. It is often called the egalitarian rule; see that page for more information on its computation and applications. For particular applications of the leximin rule in fair division, see:

• Leximin cake-cutting
• Leximin item allocation

In Multiple-criteria decision analysis a decision has to be made, and there are several criteria on which the decision should be based (for example: cost, quality, speed, etc.). One way to decide is to assign, to each alternative, a vector of numbers representing its value in each of the criteria, and chooses the alternative whose vector is leximin-optimal.{{Citation|last1=Dubois|first1=Didier|title=Beyond Min Aggregation in Multicriteria Decision: (Ordered) Weighted Min, Discri-Min, Leximin|date=1997|url=https://doi.org/10.1007/978-1-4615-6123-1_15|work=The Ordered Weighted Averaging Operators: Theory and Applications|pages=181–192|editor-last=Yager|editor-first=Ronald R.|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-1-4615-6123-1_15|isbn=978-1-4615-6123-1|access-date=2021-06-11|last2=Fargier|first2=Hélène|author2-link= Hélène Fargier |last3=Prade|first3=Henri|editor2-last=Kacprzyk|editor2-first=Janusz}}

The leximin-order is also used for Multi-objective optimization,{{Cite book|last=Ehrgott|first=Matthias|url=https://books.google.com/books?id=8wGyB5Sa2CUC&dq=Multicriteria+Optimization%2C+Lecture+Notes+in+Economics+and+Mathematical+Systems%2C+v&pg=PA1|title=Multicriteria Optimization|date=2005-05-18|publisher=Springer Science & Business Media|isbn=978-3-540-21398-7|language=en}} for example, in optimal resource allocation,{{Cite journal|last=Luss|first=Hanan|date=1999-06-01|title=On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach|journal=Operations Research|volume=47|issue=3|pages=361–378|doi=10.1287/opre.47.3.361|issn=0030-364X|doi-access=free}} location problems,{{Cite journal|date=1997-08-01|title=On the lexicographic minimax approach to location problems|url=https://www.sciencedirect.com/science/article/abs/pii/S0377221796001543|journal=European Journal of Operational Research|language=en|volume=100|issue=3|pages=566–585|doi=10.1016/S0377-2217(96)00154-3|issn=0377-2217|last1=Ogryczak|first1=Włodzimierz}} and matrix games.{{Cite journal

| last1=Potters | first1=Jos A. M.

| last2=Tijs | first2=Stef H. |author2-link=Stef Tijs

| date=1992-02-01

| title=The Nucleolus of a Matrix Game and Other Nucleoli

| url=https://pubsonline.informs.org/doi/abs/10.1287/moor.17.1.164

| journal=Mathematics of Operations Research

| volume=17

| issue=1

| pages=164–174

| doi=10.1287/moor.17.1.164

| issn=0364-765X

| hdl=2066/223732 | hdl-access=free

| s2cid=40275405}}

It is also studied in the context of fuzzy constraint solving problems.{{Cite journal|date=1999-10-01|title=Computing improved optimal solutions to max–min flexible constraint satisfaction problems|url=https://www.sciencedirect.com/science/article/abs/pii/S0377221798003075|journal=European Journal of Operational Research|language=en|volume=118|issue=1|pages=95–126|doi=10.1016/S0377-2217(98)00307-5|issn=0377-2217|last1=Dubois|first1=Didier|last2=Fortemps|first2=Philippe}}{{Cite book|last1=Pires|first1=J.M.|last2=Prade|first2=H.|title=1998 IEEE International Conference on Fuzzy Systems Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98CH36228) |chapter=Logical analysis of fuzzy constraint satisfaction problems |date=1998-05-01|chapter-url=https://ieeexplore.ieee.org/document/687603|volume=1|pages=857–862 vol.1|doi=10.1109/FUZZY.1998.687603|isbn=0-7803-4863-X|s2cid=123126673|url=https://hal.science/hal-04026179/file/Logical%20Analysis%20of%20Fuzzy%20Constraint%20Satisfaction%20Problems.pdf }}

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.{{cite journal

| last1=Frank | first1=András | authorlink1=András Frank

| last2=Murota | first2=Kazuo

| date=2020-09-18

| title=Fair integral network flows

| arxiv=1907.02673

| journal=Mathematics of Operations Research

| volume=48

| issue=3

| pages=1393–1422

| doi=10.1287/moor.2022.1303| s2cid=246411731 }}

{{Main|Nucleolus (game theory)}}

One kind of a solution to a cooperative game is the payoff-vector that minimizes the leximin vector of excess-values of coalitions, among all payoff-vectors that are efficient and individually-rational. This solution is called the nucleolus.

A representation of an ordering on a set of vectors is a function f that assigns a single number to each vector, such that the ordering between the numbers is identical to the ordering between the vectors. That is, f(x) ≥ f(y) iff x is larger than y by that ordering. When the number of possible vectors is countable (e.g. when all vectors are integral and bounded), the leximin order can be represented by various functions, for example:

• $f(\backslash mathbf\{x\})\; =\; -\; \backslash sum\_\{i=1\}^n\; n^\{-x\_i\}$; {{Cite journal|date=2009-02-01|title=Filtering algorithms for the multiset ordering constraint|url=https://www.sciencedirect.com/science/article/pii/S0004370208001471|journal=Artificial Intelligence|language=en|volume=173|issue=2|pages=299–328|doi=10.1016/j.artint.2008.11.001|issn=0004-3702|arxiv=0903.0460|last1=Frisch|first1=Alan M.|last2=Hnich|first2=Brahim|last3=Kiziltan|first3=Zeynep|last4=Miguel|first4=Ian|last5=Walsh|first5=Toby|s2cid=7869870}}
• $f(\backslash mathbf\{x\})\; =\; -\; \backslash sum\_\{i=1\}^n\; x\_i^\{-q\}$, where q is a sufficiently large constant;{{Cite book|last=Moulin|first=Herve|url=https://books.google.com/books?id=mK6nEvHnqQIC&dq=H.+Moulin%2C+Axioms+of+Cooperative+Decision+Making%2C+Cambridge+University+Press%2C+1988.&pg=PR11|title=Axioms of Cooperative Decision Making|date=1991-07-26|publisher=Cambridge University Press|isbn=978-0-521-42458-5|language=en}}
• $f(\backslash mathbf\{x\})\; =\; \backslash sum\_\{i=1\}^n\; w\_i\; \backslash cdot\; (x^\{\backslash uparrow\})\_i$, where $\backslash mathbf\{x^\{\backslash uparrow\}\}$ is vector x sorted in ascending order, and $w\_1\backslash gg\; w\_2\; \backslash gg\; \backslash cdots\; \backslash gg\; w\_n$.{{Cite journal|last=Yager|first=R.R.|date=1988-01-01|title=On ordered weighted averaging aggregation operators in multicriteria decisionmaking|url=https://ieeexplore.ieee.org/document/87068|journal=IEEE Transactions on Systems, Man, and Cybernetics|volume=18|issue=1|pages=183–190|doi=10.1109/21.87068|issn=2168-2909}}{{Cite journal|date=1997-10-01|title=On the analytic representation of the Leximin ordering and its application to flexible constraint propagation|url=https://www.sciencedirect.com/science/article/abs/pii/S0377221796002172|journal=European Journal of Operational Research|language=en|volume=102|issue=1|pages=176–192|doi=10.1016/S0377-2217(96)00217-2|issn=0377-2217|last1=Yager|first1=Ronald R.}}

However, when the set of possible vectors is uncountable (e.g. real vectors), no function (whether contiuous or not) can represent the leximin order.{{Rp|34}} The same is true for the lexicographic order.

• Lexicographic max-min optimization is the computational problem of finding a maximal element of the leximin order in a given set.

{{reflist}}

Category:Fairness criteria

Category:Vector calculus

Category:Egalitarianism