Lexicographic max-min optimization

Lexicographic max-min optimization (also called lexmaxmin or leximin or leximax or lexicographic max-ordering optimization) is a kind of multi-objective optimization. In general, multi-objective optimization deals with optimization problems with two or more objective functions to be optimized simultaneously. Lexmaxmin optimization presumes that the decision-maker would like the smallest objective value to be as high as possible; subject to this, the second-smallest objective should be as high as possible; and so on. In other words, the decision-maker ranks the possible solutions according to a leximin order of their objective function values.

As an example, consider egalitarian social planners, who want to decide on a policy such that the utility of the poorest person will be as high as possible; subject to this, they want to maximize the utility of the second-poorest person; and so on. This planner solves a lexmaxmin problem, where the objective function number i is the utility of agent number i.

An early application of lexmaxmin (not using this name) was presented by Melvin Dresher in his book on game theory, in the context of taking maximum advantage of the opponent's mistakes in a zero-sum game. Behringer cites many other examples in game theory as well as decision theory.

Notation

A lexmaxmin problem may be written as:

$${\begin{aligned}\operatorname {lex} \max \min &&f_{1}(x),f_{2}(x),\ldots ,f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$$

where $f_{1},\ldots ,f_{n}$ are the functions to maximize; $x$ is the vector of decision variables; and $X$ is the feasible set - the set of possible values of $x$.

Comparison with lexicographic optimization

Lexmaxmin optimization is closely related to lexicographic optimization. However, in lexicographic optimization, there is a fixed order on the functions, such that $f_{1}$ is the most important, $f_{2}$ is the next-most important, and so on. In contrast, in lexmaxmin, all the objectives are equally important. To present lexmaxmin as a special case of lexicographic optimization, denote by $f_{[1]}(x):=\min(f_{1}(x),\ldots ,f_{n}(x))=$ the smallest objective value in x. Similarly, denote by $f_{[2]}x:=$ the second-smallest objective value in x, and so on, so that $f_{[1]}(x)\leq f_{[2]}(x)\leq \cdots \leq f_{[n]}(x)$. Then, the lexmaxmin optimization problem can be written as the following lexicographic maximization problem:

$${\begin{aligned}\operatorname {lex} \max &&f_{[1]},\ldots ,f_{[n]}\\{\text{subject to}}&&x\in X\end{aligned}}$$

Properties

(1) Uniqueness. In general, a lexicographic optimization problem may have more than one optimal solution. However, If $x^{1}$ and $x^{2}$ are two optimal solutions, then their value must be the same, that is, $f_{i}(x^{1})=f_{i}(x^{2})$ for all $i\in [n]$. Moreover, if the feasible domain is a convex set, and the objective functions are strictly concave, then the problem has at most one optimal solution, since if there were two different optimal solutions, their mean would be another feasible solution in which the objective functions attain a higher value - contradicting the optimality of the original solutions.

Algorithms

Behringer's algorithm for quasiconcave functions

Behringer presented a sequential algorithm for lexmaxmin optimization when the objectives are quasiconvex functions, and the feasible set X is a convex set.

Reduction to lexicographic maximization

Ogryczak, Pioro and Tomaszewski

Many algorithms for lexicographic optimization can be adapted to leximin optimization.

Weighted average

Yager presented a way to represent the leximin ordering analytically using the Ordered weighted averaging aggregation operator.

See also

• In game theory, the nucleolus is defined as a lexicographically-minimal solution set.