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. Algorithms for lexmaxmin optimization (not using this name) were developed for computing the nucleolus of a cooperative game. An early application of lexmaxmin 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: lex max min f 1 ( x ) , f 2 ( x ) , … , f n ( x ) subject to x ∈ X {\displaystyle {\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 , … , f n {\displaystyle f_{1},\ldots ,f_{n}} are the functions to maximize; x {\displaystyle x} is the vector of decision variables; and X {\displaystyle X} is the feasible set - the set of possible values of x {\displaystyle 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 {\displaystyle f_{1}} is the most important, f 2 {\displaystyle 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 ) , … , f n ( x ) ) = {\displaystyle f_{[1]}(x):=\min(f_{1}(x),\ldots ,f_{n}(x))=} the smallest objective value in x. Similarly, denote by f [ 2 ] ( x ) := {\displaystyle f_{[2]}(x):=} the second-smallest objective value in x, and so on, so that f [ 1 ] ( x ) ≤ f [ 2 ] ( x ) ≤ ⋯ ≤ f [ n ] ( x ) {\displaystyle 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: lex max f [ 1 ] ( x ) , … , f [ n ] ( x ) subject to x ∈ X {\displaystyle {\begin{aligned}\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}
… excerpt ends here. Continue reading the full article.
