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.

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.

Computation

A leximin optimization problem is an optimization problem for a set X of variables over a given domain D, with a set C of constraints on the variables. It can be formalized as follows:

Find a vector x in Dⁿ that is leximin-optimal subject to satisfying the constraints C.

Continuous variables

When the set of vectors is continuous (e.g. D is the set of real numbers, or a real interval) and the set of constraints is linear or at least convex, then the leximin optimization problem can be solved efficiently by linear programming or convex programming. The following algorithm, for the case of linear constraints, was presented by Stephen J. Willson, and later by other authors:

1. Find the maximum minimum value; this can be done by solving a single linear program. Denote this value by V.
2. For each variable x_i, find the maximum value of x_i subject to the additional constraint that the value of all other variables is at least V. Denote this value by V_i. Note that it must be at least V.
3. If V_i=V, then we say that x_i is "saturated"; its value in the leximin-optimal solution must be exactly V. Otherwise, V_i > V, then we say that x_i is "free"; its value in the leximin-optimal solution must be more than V (this follows from the convexity of the solution space).
4. Fix the value of all saturated variables to V; go back to step 1 with only the free variables.

At each step, at least one free variable must become saturated in step 3 (this follows, again, from the convexity of the solution space). Therefore, after at most n iterations, all variables are saturated and a leximin-optimal solution is found.

Discrete variables

If the set of vectors is discrete, and the domain is sufficiently small, then it is possible to use one of the functions representing the leximin order, and maximize it subject to the constraints, using a solver for constraint-satisfaction problems.

But if the domain is large, the above approach becomes unfeasible due to the large number of possible values that this function can have: ${m+n-1 \choose n}$, where m is the number of different values in the domain, and n is the number of variables.

Bouveret and Lemaître present five different algorithms for finding leximin-optimal solutions to discrete constraint-satisfaction problems:

1. Branch and bound based on the LEXIMIN constraint - a constraint on two vectors x and y, saying that y is leximin-larger than x.
2. Branching on saturated subsets - finding subsets of variables that must be fixed at the minimum value, and finding the maximum-minimum value for the other variables.
3. Using the SORT constraint - a constraint on two vectors x and y, saying that y contains the same elements as x sorted in ascending order. This constraint can be computed efficiently by several algorithms.
4. Using the ATLEAST constraint.
5. Using max-min transformations.

In their experiments, the best-performing approach was 4 (ATLEAST), followed by 3 (SORT) followed by 1 (LEXIMIN).

Dall'aglio presents an algorithm for computing a leximin-optimal resource allocation.