Leximin order

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]

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,^[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 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]

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]

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:

• ${\displaystyle f(\mathbf {x} )=-\sum _{i=1}^{n}n^{-x_{i}}}$; ^[13]
• ${\displaystyle f(\mathbf {x} )=-\sum _{i=1}^{n}x_{i}^{-q}}$, where q is a sufficiently large constant;^[14]
• ${\displaystyle f(\mathbf {x} )=\sum _{i=1}^{n}w_{i}\cdot (x^{\uparrow })_{i}}$, where ${\displaystyle \mathbf {x^{\uparrow }} }$ is vector x sorted in ascending order, and ${\displaystyle w_{1}\gg w_{2}\gg \cdots \gg w_{n}}$.^[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.

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