![]() | ||
In decision theory and game theory, Wald's maximin model is a non-probabilistic decision-making model according to which decisions are ranked on the basis of their worst-case outcomes – the optimal decision is one with the least worst outcome. It is one of the most important models in robust decision making in general and robust optimization in particular.
Contents
- Definition
- History
- Example
- Decision tables
- Variations on a theme
- Savages minimax regret
- Deterministic models
- Maximin models in disguise
- Constrained maximin models
- The price of robustness
- Algorithms
- References
It is also known by a variety of other titles, such as Wald's maximin rule, Wald's maximin principle, Wald's maximin paradigm, and Wald's maximin criterion. Often 'minimax' is used instead of 'maximin'.
Definition
Wald's generic maximin model is as follows:
where
This model represents a 2-person game in which the
The above model is the classic format of Wald's maximin model. There is an equivalent mathematical programming (MP) format:
where
As in game theory, the worst payoff associated with decision
is called the security level of decision
The minimax version of the model is obtained by exchanging the positions of the
The equivalent MP format is as follows:
History
Inspired by maximin models of game theory, Abraham Wald developed this model in the early 1940s as an approach to situations in which there is only one player (the decision maker). The second player represents a pessimistic (worst case) approach to uncertainty. In Wald's maximin model, player 1 (the
With the establishment of modern decision theory in the 1950s, the model became a key ingredient in the formulation of non-probabilistic decision-making models in the face of severe uncertainty. It is widely used in diverse fields such as decision theory, control theory, economics, statistics, robust optimization, operations research, philosophy, etc.
Example
One of the most famous examples of a Maximin/Minimax model is
where
The optimal solution is the (red) saddle point
Decision tables
There are many cases where it is convenient to 'organize' the Maximin/Minimax model as a 'table'. The convention is that the rows of the table represent the decisions, and the columns represent the states.
Example
Henri is going for a walk. The sun may shine, or it may rain. Should Henri carry an umbrella? Henri does not like carrying an umbrella, but he dislikes getting wet even more. His "payoff matrix", viewing this as a Maximin game pitting Henri against Nature, is as follows.
Appending a Worst Payoff column and a Best Worst Payoff column to the payoff table, we obtain
The worst case, if Henri goes out without umbrella, is definitely worse than the (best) worst case when carrying an umbrella. Therefore Henri takes his umbrella with him.
Variations on a theme
Over the years a variety of related models have been developed primarily to moderate the pessimistic approach dictated by the worst-case orientation of the model. For example,
Savage's minimax regret
Savage's minimax regret model is an application of Wald's minimax model to the 'regrets' associated with the payoffs. It can be formulated as follows:
where
is the regret of payoff
Deterministic models
The sets of states
Example
Let
It might be desirable to build the facility so that its shortest distance from an existing dwelling is as large as possible. The maximin formulation of the problem is as follows:
where
In cases where is it desirable to live close to the facility, the objective could be to minimize the maximum distance from the facility. This yields the following minimax problem:
These are generic facility location problems.
Maximin models in disguise
Experience has shown that the formulation of maximin models can be subtle in the sense that problems that 'do not look like' maximin problems can be formulated as such.
Example
Consider the following problem:
Given a finite set
The maximin formulation of this problem, in the MP format, is as follows:
Generic problems of this type appear in robustness analysis.
It has been shown that the radius of stability model and info-gap's robustness model are simple instances of Wald's maximin model.
Constrained maximin models
Constraints can be incorporated explicitly in the maximin models. For instance, the following is a constrained maximin problem stated in the classic format
Its equivalent MP format is as follows:
Such models are very useful in robust optimization.
The price of robustness
One of the 'weaknesses' of the Maximin model is that the robustness that it provides comes with a price. By playing it safe, the Maximin model tends to generate conservative decisions, whose price can be high. The following example illustrates this important feature of the model.
Example
Consider the simple case where there are two decisions, d' and d", and where S(d')=S(d")=[a,b]. The Maximin model is then as follows:
Now consider the instance shown by
Note that although the payoff associated with decision d' is larger than the payoff associated with decision d" over most of the state space S=[a,b], the best worst case according to Wald's model is provided by decision d". Hence, according to Wald's model decision d" is better than decision d'.
Algorithms
There are no general-purpose algorithms for the solution of maximin problems. Some problems are very simple to solve, others are very difficult.
Example
Consider the case where the state variable is an "index", for instance let
where
If