Principle of the largest sure result

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)