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 bad outcome.
In response, the second player selects the worst state in
However, there are maximin models that are completely deterministic.
There is an equivalent mathematical programming (MP) format: where
As in game theory, the worst payoff associated with decision
The minimax version of the model is obtained by exchanging the positions of the
operations in the classic format: The equivalent MP format is as follows: Inspired by game theory, Abraham Wald developed this model [1][2][3] as an approach to scenarios in which there is only one player (the decision maker).
Player 2 showcases a gloomy approach to uncertainty.
This is a major simplification of the classic 2-person zero-sum game in which the two players choose their strategies without knowing the other player's choice.
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.
[4][5] It is widely used in diverse fields such as decision theory, control theory, economics, statistics, robust optimization, operations research, philosophy, etc.
The optimal solution is the (red) saddle point
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.
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.
They can represent (deterministic) variations in the value of a parameter.
be a finite set representing possible locations of an 'undesirable' public facility (e.g. garbage dump), and let
denote a finite set of locations in the neighborhood of the planned facility, representing existing dwellings.
It might be desirable to build the facility so that its shortest distance from an existing dwelling is as large as possible.
In cases where is it desirable to live close to the facility, the objective could be to minimize the maximum distance from the facility.
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.
The maximin formulation of this problem, in the MP format, is as follows: Generic problems of this type appear in robustness analysis.
[14] 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.
One of the 'weaknesses' of the Maximin model is that the robustness that it provides comes with a price.
[10] 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.
The model is then as follows: There are no general-purpose algorithms for the solution of maximin problems.
[9][10][15][16] Consider the case where the state variable is an "index", for instance let
, then this problem is a linear programming problem that can be solved by linear programming algorithms such as the simplex algorithm.