Leximin order
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 = (x1, ..., x'n) is leximin-larger than a vector y = (y1, ..., 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 x1 and y1, regardless of whether they are smallest in their vectors. The second comparison is between x2 and y2, 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 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:
<math>f(\mathbf{x}) = - \sum_{i=1}^n n^{-x_i}</math>; <math>f(\mathbf{x}) = - \sum_{i=1}^n x_i^{-q}</math>, where q is a sufficiently large constant; <math>f(\mathbf{x}) = \sum_{i=1}^n w_i \cdot (x^{\uparrow})_i</math>, where <math>\mathbf{x^{\uparrow}}</math> is vector x' sorted in ascending order, and <math>w_1\gg w_2 \gg \cdots \gg w_n</math>. 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.