In
decision theory
Decision theory (or the theory of choice; not to be confused with choice theory) is a branch of applied probability theory concerned with the theory of making decisions based on assigning probabilities to various factors and assigning numerical ...
and
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
,
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 worst outcome. It is one of the most important models in
robust decision making
Robust decision-making (RDM) is an iterative decision analytics framework that aims to help identify potential robust strategies, characterize the vulnerabilities of such strategies, and evaluate the tradeoffs among them. RDM focuses on informing ...
in general and
robust optimization Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the ...
in particular.
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
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...
' is used instead of 'maximin'.
Definition
This model represents a 2-person game in which the
player plays first. In response, the second player selects the worst state in
, namely a state in
that minimizes the payoff
over
in
. In many applications the second player represents uncertainty. However, there are maximin models that are completely deterministic.
The above model is the ''classic'' format of Wald's maximin model. There is an equivalent
mathematical programming
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
(MP) format:
where
denotes the real line.
As in
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, the worst payoff associated with decision
, namely
:
is called ''the security level'' of decision
.
The minimax version of the model is obtained by exchanging the positions of the
and
operations in the classic format:
:
The equivalent MP format is as follows:
:
History
Inspired by game theory,
Abraham Wald
Abraham Wald (; hu, Wald Ábrahám, yi, אברהם וואַלד; – ) was a Jewish Hungarian mathematician who contributed to decision theory, geometry, and econometrics and founded the field of statistical sequential analysis. One of ...
developed this model
[Wald, A. (1939). Contributions to the theory of statistical estimation and testing hypotheses. ''The Annals of Mathematics,'' 10(4), 299-326.][Wald, A. (1945). Statistical decision functions which minimize the maximum risk. ''The Annals of Mathematics,'' 46(2), 265-280.][Wald, A. (1950). ''Statistical Decision Functions,'' John Wiley, NY.] as an approach to scenarios in which there is only one player (the decision maker). Player 2 showcases a gloomy approach to uncertainty. In Wald's maximin model, player 1 (the
player) plays first and player 2 (the
player) knows player 1's decision when he selects his decision. 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. The game of Wald's maximin model is also a 2-person
zero-sum game
Zero-sum game is a mathematical representation in game theory and economic theory of a situation which involves two sides, where the result is an advantage for one side and an equivalent loss for the other. In other words, player one's gain is e ...
, but the players choose sequentially.
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.
[Resnik, M.D. (1987). ''Choices: an Introduction to Decision Theory,'' University of Minnesota Press, Minneapolis.][French, S. (1986). ''Decision Theory: An Introduction to the Mathematics of Rationality,'' Ellis Horwood, Chichester.] It is widely used in diverse fields such as
decision theory
Decision theory (or the theory of choice; not to be confused with choice theory) is a branch of applied probability theory concerned with the theory of making decisions based on assigning probabilities to various factors and assigning numerical ...
,
control theory
Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a ...
,
economics
Economics () is the social science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services.
Economics focuses on the behaviour and intera ...
,
statistics
Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
,
robust optimization Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the ...
,
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
,
philosophy
Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such questions are often posed as problems to be studied or resolved. Some ...
, etc.
[Sniedovich, M. (2007). The art and science of modeling decision-making under severe uncertainty. ''Decision Making in Manufacturing and Services,'' 1(1-2), 111-136.][Sniedovich, M. (2008). Wald's maximin model: a treasure in disguise! ''Journal of Risk Finance,'' 9(3), 287-91.]
Example
One of the most famous examples of a Maximin/Minimax model is
:
where
denotes the real line. Formally we can set
and
. The picture is this
The optimal solution is the (red)
saddle point
In mathematics, a saddle point or minimax point is a point on the surface of the graph of a function where the slopes (derivatives) in orthogonal directions are all zero (a critical point), but which is not a local extremum of the function ...
.
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
In game theory, normal form is a description of a ''game''. Unlike extensive form, normal-form representations are not graphical ''per se'', but rather represent the game by way of a matrix. While this approach can be of greater use in identifying ...
", 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.
[Kouvelis P, and Yu G. (1997). ''Robust Discrete Optimization and Its Applications,'' Kluwer, Boston.][Ben-Tal, A, El Gaoui, L, Nemirovski, A. (2009). ''Robust Optimization.'' Princeton University Press, Princeton.][Bertsimas D, and Sim, M. (2004). The price of robustness. ''Operations Research,'' 52(1), 35-53.] For example,
Savage's minimax regret
Savage's minimax regret model[Savage, L. (1951). The theory of statistical decision. ''Journal of the American Statistical Association,'' 46, 55–67.] is associated with the payoff regrets.
Deterministic models
The sets of states
need not represent uncertainty. They can represent (deterministic) variations in the value of a parameter.
Example
Let
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. The maximin formulation of the problem is as follows:
:
where
denotes the distance of
from
. Note that in this problem
does not vary with
.
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 Facility location is a name given to several different problems in computer science and in game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: A ...
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 and a real valued function on , find the largest subset of such that for every in this subset.
The maximin formulation of this problem, in the MP format, is as follows:
:
Generic problems of this type appear in robustness analysis.
[L. Joe Moffitt, John K. Stranlund, and Craig D. Osteen (2008). Robust detection protocols for uncertain introductions of invasive species. ''Journal of Environmental Management,'' 89(4), 293–299.][Jonathan Rosenhead, Martin Elton, Shiv K. Gupta. (1972). Robustness and Optimality as Criteria for Strategic Decisions. ''Operational Research Quarterly,'' 23(4), 413-431.]
It has been shown that the
radius of stability model and
info-gap's robustness model are simple instances of Wald's maximin model.
[Sniedovich, M. (2010). A bird's view of info-gap decision theory. ''Journal of Risk Finance,'' 11(3), 268-283.]
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 Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the ...
.
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
Suppose there are two options, and , and where