Leximin order

Not to be confused with Lexis minima.

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

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

Main article: 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:

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