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 = (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.

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

Applications

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:

• ${\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.

See also

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

References