Namespaces
Variants
Actions

Difference between revisions of "Principle of the largest sure result"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
p0748101.png
 +
$#A+1 = 55 n = 0
 +
$#C+1 = 55 : ~/encyclopedia/old_files/data/P074/P.0704810 Principle of the largest sure result
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
One of the fundamental principles of decision-making, used in [[Operations research|operations research]] and game theory (cf. [[Games, theory of|Games, theory of]]). It is implicit in the attempt to choose a strategy such that the minimum of the pay-offs it yields will be a maximum (see [[Maximin|Maximin]]). In many cases the principle can be derived as a corollary from a certain system of axioms which represents properties that are natural to demand of any  "reasonable"  principle of optimal behaviour (see [[#References|[5]]]). Realization of the principle of the largest sure result in different situations implies the formulation of a great variety of maximin problems.
 
One of the fundamental principles of decision-making, used in [[Operations research|operations research]] and game theory (cf. [[Games, theory of|Games, theory of]]). It is implicit in the attempt to choose a strategy such that the minimum of the pay-offs it yields will be a maximum (see [[Maximin|Maximin]]). In many cases the principle can be derived as a corollary from a certain system of axioms which represents properties that are natural to demand of any  "reasonable"  principle of optimal behaviour (see [[#References|[5]]]). Realization of the principle of the largest sure result in different situations implies the formulation of a great variety of maximin problems.
  
Operations research, i.e. the study of activities that lead to the achievement of a pre-assigned objective, is carried out by the operations researcher in the interests of a consumer. The latter endeavours to achieve his objective, as mathematically expressed by the desire to increase an effectiveness criterion — a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748101.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748102.png" /> is the consumer's choice and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748103.png" /> a factor not controllable by the consumer. The choice of concrete values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748104.png" />, depending on the information at the disposal of the consumer and the operations researcher concerning the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748105.png" />, defines the consumer's strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748106.png" />.
+
Operations research, i.e. the study of activities that lead to the achievement of a pre-assigned objective, is carried out by the operations researcher in the interests of a consumer. The latter endeavours to achieve his objective, as mathematically expressed by the desire to increase an effectiveness criterion — a function $  f ( x, y) $,  
 +
where $  x $
 +
is the consumer's choice and $  y $
 +
a factor not controllable by the consumer. The choice of concrete values $  x \in X $,  
 +
depending on the information at the disposal of the consumer and the operations researcher concerning the values of $  y $,  
 +
defines the consumer's strategy $  \widetilde{x}  = x ( y) $.
  
Based on the information at the disposal of the researcher about the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748107.png" />, the uncontrollable factors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748108.png" /> are divided into three groups: fixed factors, whose values are known; random factors, i.e. random processes with known distributions; and indeterminate factors, of which nothing is known other than the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p0748109.png" /> to which they belong or the domain to which their distribution laws belong.
+
Based on the information at the disposal of the researcher about the values of $  y $,  
 +
the uncontrollable factors $  y $
 +
are divided into three groups: fixed factors, whose values are known; random factors, i.e. random processes with known distributions; and indeterminate factors, of which nothing is known other than the domain $  Y $
 +
to which they belong or the domain to which their distribution laws belong.
  
The researcher evaluates the effectiveness of strategies and makes his choice of strategies insofar as they maximize the guaranteed value of the effectiveness criterion, given the amount of information at the consumer's disposal concerning the uncontrollable factors. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481010.png" /> is the strategy of the consumer, then its value to the consumer, when it is known only that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481011.png" />, is defined as
+
The researcher evaluates the effectiveness of strategies and makes his choice of strategies insofar as they maximize the guaranteed value of the effectiveness criterion, given the amount of information at the consumer's disposal concerning the uncontrollable factors. If $  \widetilde{x}  $
 +
is the strategy of the consumer, then its value to the consumer, when it is known only that $  y \in Y $,  
 +
is defined as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481012.png" /></td> </tr></table>
+
$$
 +
\inf _ {y \in Y }  f ( \widetilde{x}  , y).
 +
$$
  
 
The largest sure result is defined as
 
The largest sure result is defined as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$ \tag{* }
 +
\sup _ {\widetilde{x}  }  \inf _ {y \in Y }  f( \widetilde{x}  , y);
 +
$$
  
a strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481014.png" /> for which
+
a strategy $  \widetilde{x}  {}  ^ {*} $
 +
for which
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481015.png" /></td> </tr></table>
+
$$
 +
\inf _ {y \in Y }  f ( \widetilde{x}  {}  ^ {*} , y)  = \
 +
\sup _ {\widetilde{x}  }  \inf _ {y \in Y }  f( \widetilde{x}  , y)
 +
$$
  
 
is an optimum strategy in the situation under consideration.
 
is an optimum strategy in the situation under consideration.
  
If the consumer does not expect any information about the concrete values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481016.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481017.png" />, the largest sure result is defined as
+
If the consumer does not expect any information about the concrete values $  y \in Y $,  
 +
i.e. $  x ( y) = x $,  
 +
the largest sure result is defined as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481018.png" /></td> </tr></table>
+
$$
 +
\sup _ {x \in X }  \inf _ {y \in Y }  f ( x, y)
 +
$$
  
 
(see [[Minimax principle|Minimax principle]]).
 
(see [[Minimax principle|Minimax principle]]).
  
If the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481019.png" /> is known exactly, there is the following equality for (*):
+
If the value of $  y $
 +
is known exactly, there is the following equality for (*):
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481020.png" /></td> </tr></table>
+
$$
 +
\sup _ {x ( y) }  \inf _ {y \in Y }  f( x( y), y)  = \
 +
\inf _ {y \in Y }  \sup _ {x \in X }  f ( x, y).
 +
$$
  
If the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481021.png" /> are produced by an active opponent, and the operations researcher and the consumer are informed of the opponent's effectiveness criterion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481023.png" />, on the assumption that the opponent selects <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481024.png" /> to fulfill the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481025.png" />, then the largest sure result is defined as
+
If the values of $  y $
 +
are produced by an active opponent, and the operations researcher and the consumer are informed of the opponent's effectiveness criterion $  \phi ( \widetilde{x}  , y) $,  
 +
$  y \in Y $,
 +
on the assumption that the opponent selects $  y $
 +
to fulfill the condition $  \max _ {y \in Y }  \phi ( \widetilde{x}  ( y), y) $,  
 +
then the largest sure result is defined as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481026.png" /></td> </tr></table>
+
$$
 +
\sup _ {\widetilde{x}  } \
 +
\inf _ {y \in Y _ {1} ( \widetilde{x}  ) }  f ( \widetilde{x}  , y),
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481027.png" /></td> </tr></table>
+
$$
 +
Y _ {1} ( \widetilde{x}  )  = \left \{ {y \in Y } : {\phi ( x ( y), y) =
 +
\max _ {y \in Y }  \phi ( x ( y), y) } \right \}
 +
.
 +
$$
  
 
Realization of the principle of the largest sure result in games with a fixed sequence of player moves and in operations for which the information about the indeterminate factors becomes more precise with the passage of time leads to the solution of extremely complex minimax problems (e.g. [[Differential games|differential games]]).
 
Realization of the principle of the largest sure result in games with a fixed sequence of player moves and in operations for which the information about the indeterminate factors becomes more precise with the passage of time leads to the solution of extremely complex minimax problems (e.g. [[Differential games|differential games]]).
  
Now suppose that the operation involves, besides the indeterminate factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481029.png" />, a random factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481031.png" />, with known distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481032.png" />, and that the consumer is capable of averaging over random events. In this case the effectiveness criterion is the expectation
+
Now suppose that the operation involves, besides the indeterminate factor $  y $,  
 +
$  y \in Y $,  
 +
a random factor $  z $,  
 +
$  z \in Z $,  
 +
with known distribution $  P $,  
 +
and that the consumer is capable of averaging over random events. In this case the effectiveness criterion is the expectation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481033.png" /></td> </tr></table>
+
$$
 +
\overline{f}\; ( \widetilde{x}  , y)  = \int\limits _ { Z } f ( \widetilde{x}  , y, z)  dP ( z),
 +
$$
  
which means that the consumer must agree to a definite risk. As a rule, the introduction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481034.png" /> is applied in frequently repeated operations.
+
which means that the consumer must agree to a definite risk. As a rule, the introduction of $  \overline{f}\; $
 +
is applied in frequently repeated operations.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481035.png" /> stays constant in successive trials and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481036.png" />, then the largest sure result is
+
If $  y $
 +
stays constant in successive trials and $  \widetilde{x}  = x ( y) $,  
 +
then the largest sure result is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481037.png" /></td> </tr></table>
+
$$
 +
\sup _ {\widetilde{x}  }  \inf _ {y \in Y } \
 +
\overline{f}\; ( \widetilde{x}  , y).
 +
$$
  
But if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481038.png" /> varies in different trials in an arbitrary manner, then the largest sure result will be
+
But if $  y $
 +
varies in different trials in an arbitrary manner, then the largest sure result will be
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481039.png" /></td> </tr></table>
+
$$
 +
\sup _ {\widetilde{x}  }  \int\limits _ { Z } \
 +
\inf _ {y \in Y } \
 +
f ( \widetilde{x}  , y, z)  dP ( z).
 +
$$
  
In other cases (and also in other classes of strategies, e.g. of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481040.png" />), the largest sure result is represented by other combinations of extremum-evaluation and integration (see [[#References|[1]]], [[#References|[3]]]).
+
In other cases (and also in other classes of strategies, e.g. of the type $  \widetilde{x}  = x ( y, z) $),  
 +
the largest sure result is represented by other combinations of extremum-evaluation and integration (see [[#References|[1]]], [[#References|[3]]]).
  
A mixed strategy is defined as a [[Probability measure|probability measure]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481041.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481042.png" />. If, as before, the consumer agrees to averaging the effectiveness criterion,
+
A mixed strategy is defined as a [[Probability measure|probability measure]] $  \Psi $
 +
on $  X $.  
 +
If, as before, the consumer agrees to averaging the effectiveness criterion,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481043.png" /></td> </tr></table>
+
$$
 +
f ( \Psi , y)  = \
 +
\int\limits _ { X } f ( x, y)  d \Psi ( x),
 +
$$
  
 
then the largest sure result is
 
then the largest sure result is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481044.png" /></td> </tr></table>
+
$$
 +
\sup _  \Psi  \inf _ {y \in Y }  f ( \Psi , y).
 +
$$
  
 
Much importance is attached to the evaluation of optimal mixed strategies (see [[Two-person zero-sum game|Two-person zero-sum game]]).
 
Much importance is attached to the evaluation of optimal mixed strategies (see [[Two-person zero-sum game|Two-person zero-sum game]]).
  
In multi-step operations with a finite number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481045.png" /> of steps, the effectiveness criterion has the form
+
In multi-step operations with a finite number $  n $
 +
of steps, the effectiveness criterion has the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481046.png" /></td> </tr></table>
+
$$
 +
f ( x _ {1} , y _ {1} \dots x _ {n} , y _ {n} ),
 +
$$
  
where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481047.png" /> constitute the choices of the consumer, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481048.png" /> is the value of the uncontrollable factor at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481049.png" />-th step. The largest sure result in multi-step operations is generally written as a multiple (successive) maximin. Thus, in a two-person zero-sum game with complete information it is
+
where the $  x _ {i} \in X _ {i} $
 +
constitute the choices of the consumer, while $  y _ {i} \in Y _ {i} $
 +
is the value of the uncontrollable factor at the $  i $-
 +
th step. The largest sure result in multi-step operations is generally written as a multiple (successive) maximin. Thus, in a two-person zero-sum game with complete information it is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481050.png" /></td> </tr></table>
+
$$
 +
\sup _ {x _ {1} \in X _ {1} } \
 +
\inf _ {y _ {1} \in Y _ {1} } \dots
 +
\sup _ {x _ {n} \in X _ {n} } \
 +
\inf _ {y _ {n} \in Y _ {n} } \
 +
f ( x _ {1} , y _ {1} \dots x _ {n} , y _ {n} ).
 +
$$
  
 
Similar expressions are also encountered in some problems of the theory of differential games.
 
Similar expressions are also encountered in some problems of the theory of differential games.
  
If the consumer's objective is not clearly formulated, e.g. there is a set of effectiveness criteria <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481051.png" /> and the index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481052.png" /> is an indeterminate factor for the operations researcher, the principle of the largest sure result implies convolution of the criteria, and the largest sure result is
+
If the consumer's objective is not clearly formulated, e.g. there is a set of effectiveness criteria $  f _ {1} ( x) \dots f _ {n} ( x) $
 +
and the index $  i $
 +
is an indeterminate factor for the operations researcher, the principle of the largest sure result implies convolution of the criteria, and the largest sure result is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481053.png" /></td> </tr></table>
+
$$
 +
\max _ { x }  \min _ { i }  ( f _ {i} ( x) - f _ {i} ^ { 0 } ),
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481054.png" /> is the level that is desired in relation to the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074810/p07481055.png" />-th component. If the largest sure result turns out to be non-negative, these desirable levels are attainable.
+
where $  f _ {i} ^ { 0 } $
 +
is the level that is desired in relation to the $  i $-
 +
th component. If the largest sure result turns out to be non-negative, these desirable levels are attainable.
  
 
Consistent application of the principle of the largest sure result, in different situations concerning the amount and type of information at the consumer's disposal, yields a unified approach to evaluating the effectiveness of strategies and to devising a complete theory of decision-making under uncertainty.
 
Consistent application of the principle of the largest sure result, in different situations concerning the amount and type of information at the consumer's disposal, yields a unified approach to evaluating the effectiveness of strategies and to devising a complete theory of decision-making under uncertainty.
Line 85: Line 179:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  Yu.B. Germeier,  "Introduction to the theory of operations research" , Moscow  (1971)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.N. Vorob'ev,  "The present state of the theory of differential games"  ''Russian Math. Surveys'' , '''25''' :  2  (1970)  pp. 77–136  ''Uspekhi Mat. Nauk'' , '''25''' :  2  (1970)  pp. 81–140</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  Yu.B. Germeier,  "Non-antagonistic games" , Reidel  (1986)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.S. Venttsel',  "Operations research" , Moscow  (1972)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E. Vilkas,  "Axiomatic definition of the value of a matrix game"  ''Theory Probab. Appl.'' , '''8''' :  3  (1963)  pp. 304–307  ''Teor. Veroyatnost. i Primenen.'' , '''8''' :  3  (1963)  pp. 324–327</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  Yu.B. Germeier,  "Introduction to the theory of operations research" , Moscow  (1971)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.N. Vorob'ev,  "The present state of the theory of differential games"  ''Russian Math. Surveys'' , '''25''' :  2  (1970)  pp. 77–136  ''Uspekhi Mat. Nauk'' , '''25''' :  2  (1970)  pp. 81–140</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  Yu.B. Germeier,  "Non-antagonistic games" , Reidel  (1986)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.S. Venttsel',  "Operations research" , Moscow  (1972)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E. Vilkas,  "Axiomatic definition of the value of a matrix game"  ''Theory Probab. Appl.'' , '''8''' :  3  (1963)  pp. 304–307  ''Teor. Veroyatnost. i Primenen.'' , '''8''' :  3  (1963)  pp. 324–327</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Latest revision as of 08:07, 6 June 2020


One of the fundamental principles of decision-making, used in operations research and game theory (cf. Games, theory of). It is implicit in the attempt to choose a strategy such that the minimum of the pay-offs it yields will be a maximum (see Maximin). In many cases the principle can be derived as a corollary from a certain system of axioms which represents properties that are natural to demand of any "reasonable" principle of optimal behaviour (see [5]). Realization of the principle of the largest sure result in different situations implies the formulation of a great variety of maximin problems.

Operations research, i.e. the study of activities that lead to the achievement of a pre-assigned objective, is carried out by the operations researcher in the interests of a consumer. The latter endeavours to achieve his objective, as mathematically expressed by the desire to increase an effectiveness criterion — a function $ f ( x, y) $, where $ x $ is the consumer's choice and $ y $ a factor not controllable by the consumer. The choice of concrete values $ x \in X $, depending on the information at the disposal of the consumer and the operations researcher concerning the values of $ y $, defines the consumer's strategy $ \widetilde{x} = x ( y) $.

Based on the information at the disposal of the researcher about the values of $ y $, the uncontrollable factors $ y $ are divided into three groups: fixed factors, whose values are known; random factors, i.e. random processes with known distributions; and indeterminate factors, of which nothing is known other than the domain $ Y $ to which they belong or the domain to which their distribution laws belong.

The researcher evaluates the effectiveness of strategies and makes his choice of strategies insofar as they maximize the guaranteed value of the effectiveness criterion, given the amount of information at the consumer's disposal concerning the uncontrollable factors. If $ \widetilde{x} $ is the strategy of the consumer, then its value to the consumer, when it is known only that $ y \in Y $, is defined as

$$ \inf _ {y \in Y } f ( \widetilde{x} , y). $$

The largest sure result is defined as

$$ \tag{* } \sup _ {\widetilde{x} } \inf _ {y \in Y } f( \widetilde{x} , y); $$

a strategy $ \widetilde{x} {} ^ {*} $ for which

$$ \inf _ {y \in Y } f ( \widetilde{x} {} ^ {*} , y) = \ \sup _ {\widetilde{x} } \inf _ {y \in Y } f( \widetilde{x} , y) $$

is an optimum strategy in the situation under consideration.

If the consumer does not expect any information about the concrete values $ y \in Y $, i.e. $ x ( y) = x $, the largest sure result is defined as

$$ \sup _ {x \in X } \inf _ {y \in Y } f ( x, y) $$

(see Minimax principle).

If the value of $ y $ is known exactly, there is the following equality for (*):

$$ \sup _ {x ( y) } \inf _ {y \in Y } f( x( y), y) = \ \inf _ {y \in Y } \sup _ {x \in X } f ( x, y). $$

If the values of $ y $ are produced by an active opponent, and the operations researcher and the consumer are informed of the opponent's effectiveness criterion $ \phi ( \widetilde{x} , y) $, $ y \in Y $, on the assumption that the opponent selects $ y $ to fulfill the condition $ \max _ {y \in Y } \phi ( \widetilde{x} ( y), y) $, then the largest sure result is defined as

$$ \sup _ {\widetilde{x} } \ \inf _ {y \in Y _ {1} ( \widetilde{x} ) } f ( \widetilde{x} , y), $$

where

$$ Y _ {1} ( \widetilde{x} ) = \left \{ {y \in Y } : {\phi ( x ( y), y) = \max _ {y \in Y } \phi ( x ( y), y) } \right \} . $$

Realization of the principle of the largest sure result in games with a fixed sequence of player moves and in operations for which the information about the indeterminate factors becomes more precise with the passage of time leads to the solution of extremely complex minimax problems (e.g. differential games).

Now suppose that the operation involves, besides the indeterminate factor $ y $, $ y \in Y $, a random factor $ z $, $ z \in Z $, with known distribution $ P $, and that the consumer is capable of averaging over random events. In this case the effectiveness criterion is the expectation

$$ \overline{f}\; ( \widetilde{x} , y) = \int\limits _ { Z } f ( \widetilde{x} , y, z) dP ( z), $$

which means that the consumer must agree to a definite risk. As a rule, the introduction of $ \overline{f}\; $ is applied in frequently repeated operations.

If $ y $ stays constant in successive trials and $ \widetilde{x} = x ( y) $, then the largest sure result is

$$ \sup _ {\widetilde{x} } \inf _ {y \in Y } \ \overline{f}\; ( \widetilde{x} , y). $$

But if $ y $ varies in different trials in an arbitrary manner, then the largest sure result will be

$$ \sup _ {\widetilde{x} } \int\limits _ { Z } \ \inf _ {y \in Y } \ f ( \widetilde{x} , y, z) dP ( z). $$

In other cases (and also in other classes of strategies, e.g. of the type $ \widetilde{x} = x ( y, z) $), the largest sure result is represented by other combinations of extremum-evaluation and integration (see [1], [3]).

A mixed strategy is defined as a probability measure $ \Psi $ on $ X $. If, as before, the consumer agrees to averaging the effectiveness criterion,

$$ f ( \Psi , y) = \ \int\limits _ { X } f ( x, y) d \Psi ( x), $$

then the largest sure result is

$$ \sup _ \Psi \inf _ {y \in Y } f ( \Psi , y). $$

Much importance is attached to the evaluation of optimal mixed strategies (see Two-person zero-sum game).

In multi-step operations with a finite number $ n $ of steps, the effectiveness criterion has the form

$$ f ( x _ {1} , y _ {1} \dots x _ {n} , y _ {n} ), $$

where the $ x _ {i} \in X _ {i} $ constitute the choices of the consumer, while $ y _ {i} \in Y _ {i} $ is the value of the uncontrollable factor at the $ i $- th step. The largest sure result in multi-step operations is generally written as a multiple (successive) maximin. Thus, in a two-person zero-sum game with complete information it is

$$ \sup _ {x _ {1} \in X _ {1} } \ \inf _ {y _ {1} \in Y _ {1} } \dots \sup _ {x _ {n} \in X _ {n} } \ \inf _ {y _ {n} \in Y _ {n} } \ f ( x _ {1} , y _ {1} \dots x _ {n} , y _ {n} ). $$

Similar expressions are also encountered in some problems of the theory of differential games.

If the consumer's objective is not clearly formulated, e.g. there is a set of effectiveness criteria $ f _ {1} ( x) \dots f _ {n} ( x) $ and the index $ i $ is an indeterminate factor for the operations researcher, the principle of the largest sure result implies convolution of the criteria, and the largest sure result is

$$ \max _ { x } \min _ { i } ( f _ {i} ( x) - f _ {i} ^ { 0 } ), $$

where $ f _ {i} ^ { 0 } $ is the level that is desired in relation to the $ i $- th component. If the largest sure result turns out to be non-negative, these desirable levels are attainable.

Consistent application of the principle of the largest sure result, in different situations concerning the amount and type of information at the consumer's disposal, yields a unified approach to evaluating the effectiveness of strategies and to devising a complete theory of decision-making under uncertainty.

References

[1] Yu.B. Germeier, "Introduction to the theory of operations research" , Moscow (1971) (In Russian)
[2] N.N. Vorob'ev, "The present state of the theory of differential games" Russian Math. Surveys , 25 : 2 (1970) pp. 77–136 Uspekhi Mat. Nauk , 25 : 2 (1970) pp. 81–140
[3] Yu.B. Germeier, "Non-antagonistic games" , Reidel (1986) (Translated from Russian)
[4] E.S. Venttsel', "Operations research" , Moscow (1972) (In Russian)
[5] E. Vilkas, "Axiomatic definition of the value of a matrix game" Theory Probab. Appl. , 8 : 3 (1963) pp. 304–307 Teor. Veroyatnost. i Primenen. , 8 : 3 (1963) pp. 324–327

Comments

The principle holds "naturally" only for a conservative, risk-averse decision-maker or in a zero-sum game. In other instances, different criteria might be intuitively appealing.

The largest sure result is also referred to as the gain-floor for the consumer. Related terms are loss ceiling, security level and security strategy.

References

[a1] T. Basar, G.J. Olsder, "Dynamic noncooperative game theory" , Acad. Press (1982)
[a2] N.N. Vorob'ev, "Game theory. Lectures for economists and system scientists" , Springer (1977) (Translated from Russian)
How to Cite This Entry:
Principle of the largest sure result. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Principle_of_the_largest_sure_result&oldid=12652
This article was adapted from an original article by F.I. EreshkoV.V. Fedorov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article