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

## Definition

A vector x = (x$_1$, ..., x$_n$) is leximin-larger than a vector y = (y$_1$, ..., 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$_1$ and y$_1$, regardless of whether they are smallest in their vectors. The second comparison is between x$_2$ and y$_2$, 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, 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 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.
The leximin-order is also used for Multi-objective optimization, for example, in optimal resource allocation, location problems, and matrix games.
It is also studied in the context of fuzzy constraint solving problems.

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

### In 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:
* $f(\mathbf {x} )=-\sum _{i=1}^{n}n^{-x_{i}}$;
* $f(\mathbf {x} )=-\sum _{i=1}^{n}x_{i}^{-q}$, where q is a sufficiently large constant;
* $f(\mathbf {x} )=\sum _{i=1}^{n}w_{i}\cdot (x^{\uparrow })_{i}$, where $\mathbf {x^{\uparrow }}$ is vector x sorted in ascending order, and $w_{1}\gg w_{2}\gg \cdots \gg w_{n}$.
However, when the set of possible vectors is uncountable (e.g. real vectors), no function (whether contiuous or not) can represent the leximin order.$^{:34}$ The same is true for the lexicographic order.