Leximin order

From HandWiki
Short description: Concept in mathematics


In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division.[1][2][3]

Definition

A vector x = (x1, ..., xn) is leximin-larger than a vector y = (y1, ..., yn) 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.

Examples

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

Related order relations

In the lexicographic order, the first comparison is between x1 and y1, regardless of whether they are smallest in their vectors. The second comparison is between x2 and y2, 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.

Applications

In social choice

In social choice theory,[4] particularly in fair division,[1] 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 multicriteria decision

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.[5]

The leximin-order is also used for Multi-objective optimization,[6] for example, in optimal resource allocation,[7] location problems,[8] and matrix games.[9]

It is also studied in the context of fuzzy constraint solving problems.[10][11]

In flow networks

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]

In game theory

Main page: Software: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.

Representation

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:

  • [math]\displaystyle{ f(\mathbf{x}) = - \sum_{i=1}^n n^{-x_i} }[/math]; [13]
  • [math]\displaystyle{ f(\mathbf{x}) = - \sum_{i=1}^n x_i^{-q} }[/math], where q is a sufficiently large constant;[14]
  • [math]\displaystyle{ f(\mathbf{x}) = \sum_{i=1}^n w_i \cdot (x^{\uparrow})_i }[/math], where [math]\displaystyle{ \mathbf{x^{\uparrow}} }[/math] is vector x sorted in ascending order, and [math]\displaystyle{ w_1\gg w_2 \gg \cdots \gg w_n }[/math].[15][16]

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

See also

References

  1. 1.0 1.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" (in en). Journal of Economic Theory 46 (1): 34–44. doi:10.1016/0022-0531(88)90148-2. ISSN 0022-0531. https://dx.doi.org/10.1016%2F0022-0531%2888%2990148-2. 
  3. Yager, Ronald R. (1997-10-01). "On the analytic representation of the Leximin ordering and its application to flexible constraint propagation" (in en). European Journal of Operational Research 102 (1): 176–192. doi:10.1016/S0377-2217(96)00217-2. ISSN 0377-2217. http://www.sciencedirect.com/science/article/pii/S0377221796002172. 
  4. Sen, Amartya (2017-02-20) (in en). Collective Choice and Social Welfare. Harvard University Press. doi:10.4159/9780674974616. ISBN 978-0-674-97461-6. https://www.degruyter.com/document/doi/10.4159/9780674974616/html. 
  5. Dubois, Didier; Fargier, Hélène; Prade, Henri (1997), Yager, Ronald R.; Kacprzyk, Janusz, eds., "Beyond Min Aggregation in Multicriteria Decision: (Ordered) Weighted Min, Discri-Min, Leximin" (in en), The Ordered Weighted Averaging Operators: Theory and Applications (Boston, MA: Springer US): pp. 181–192, doi:10.1007/978-1-4615-6123-1_15, ISBN 978-1-4615-6123-1, https://doi.org/10.1007/978-1-4615-6123-1_15, retrieved 2021-06-11 
  6. Ehrgott, Matthias (2005-05-18) (in en). Multicriteria Optimization. Springer Science & Business Media. ISBN 978-3-540-21398-7. https://books.google.com/books?id=8wGyB5Sa2CUC&dq=Multicriteria+Optimization%2C+Lecture+Notes+in+Economics+and+Mathematical+Systems%2C+v&pg=PA1. 
  7. Luss, Hanan (1999-06-01). "On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach". Operations Research 47 (3): 361–378. doi:10.1287/opre.47.3.361. ISSN 0030-364X. 
  8. Ogryczak, Włodzimierz (1997-08-01). "On the lexicographic minimax approach to location problems" (in en). European Journal of Operational Research 100 (3): 566–585. doi:10.1016/S0377-2217(96)00154-3. ISSN 0377-2217. https://www.sciencedirect.com/science/article/abs/pii/S0377221796001543. 
  9. Potters, Jos A. M.; Tijs, Stef H. (1992-02-01). "The Nucleolus of a Matrix Game and Other Nucleoli". Mathematics of Operations Research 17 (1): 164–174. doi:10.1287/moor.17.1.164. ISSN 0364-765X. https://pubsonline.informs.org/doi/abs/10.1287/moor.17.1.164. 
  10. Dubois, Didier; Fortemps, Philippe (1999-10-01). "Computing improved optimal solutions to max–min flexible constraint satisfaction problems" (in en). European Journal of Operational Research 118 (1): 95–126. doi:10.1016/S0377-2217(98)00307-5. ISSN 0377-2217. https://www.sciencedirect.com/science/article/abs/pii/S0377221798003075. 
  11. Pires, J.M.; Prade, H. (1998-05-01). "Logical analysis of fuzzy constraint satisfaction problems". 1998 IEEE International Conference on Fuzzy Systems Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98CH36228). 1. pp. 857–862 vol.1. doi:10.1109/FUZZY.1998.687603. ISBN 0-7803-4863-X. https://ieeexplore.ieee.org/document/687603. 
  12. "Fair integral network flows". Mathematics of Operations Research 48 (3): 1393–1422. 2020-09-18. doi:10.1287/moor.2022.1303. 
  13. Frisch, Alan M.; Hnich, Brahim; Kiziltan, Zeynep; Miguel, Ian; Walsh, Toby (2009-02-01). "Filtering algorithms for the multiset ordering constraint" (in en). Artificial Intelligence 173 (2): 299–328. doi:10.1016/j.artint.2008.11.001. ISSN 0004-3702. https://www.sciencedirect.com/science/article/pii/S0004370208001471. 
  14. 14.0 14.1 Moulin, Herve (1991-07-26) (in en). Axioms of Cooperative Decision Making. Cambridge University Press. ISBN 978-0-521-42458-5. https://books.google.com/books?id=mK6nEvHnqQIC&dq=H.+Moulin%2C+Axioms+of+Cooperative+Decision+Making%2C+Cambridge+University+Press%2C+1988.&pg=PR11. 
  15. Yager, R.R. (1988-01-01). "On ordered weighted averaging aggregation operators in multicriteria decisionmaking". IEEE Transactions on Systems, Man, and Cybernetics 18 (1): 183–190. doi:10.1109/21.87068. ISSN 2168-2909. https://ieeexplore.ieee.org/document/87068. 
  16. Yager, Ronald R. (1997-10-01). "On the analytic representation of the Leximin ordering and its application to flexible constraint propagation" (in en). European Journal of Operational Research 102 (1): 176–192. doi:10.1016/S0377-2217(96)00217-2. ISSN 0377-2217. https://www.sciencedirect.com/science/article/abs/pii/S0377221796002172.