Minimax regret criterion (Savage criterion)

Savage's criterion (also known as the minimax regret criterion) is a method for decision-making under uncertainty. It is applied in situations where the probabilities of different outcomes are unknown, and the goal is to minimize potential losses resulting from making a non-optimal decision.

General Characteristics

Under conditions of uncertainty, the consequences of choosing each strategy are not precisely defined. A number of criteria are used to evaluate possible alternatives, such as the criteria of Wald, Hurwicz, Laplace, and Savage. Savage's criterion is not focused on achieving maximum profit, but on minimizing the maximum regret (losses compared to the best possible outcome).

Regret is a value that reflects the opportunity loss incurred because a non-optimal strategy was chosen for a specific outcome.

Algorithm for Applying Savage's Criterion

• Constructing the payoff matrix: A table is created where rows correspond to possible strategies and columns correspond to possible outcomes (states of nature). The intersection records the expected result for a specific strategy and outcome.
• Constructing the regret matrix (risk matrix): For each outcome (column), the maximum payoff value is determined. Then, for each cell, the amount of regret is calculated.
• Determining the maximum regret for each strategy: In each row of the regret matrix, the maximum value is selected (the worst-case scenario for that strategy).
• Choosing the optimal strategy: The strategy with the minimum maximum regret is chosen.

Thus, Savage's criterion implements the principle of minimizing the potential loss from an incorrect decision.

Mathematical Formulation

Let the following be given:

• $S=\{s_1,s_2,\dots ,s_m\}$ — the set of available strategies (alternatives).
• $\mathrm{\Theta }=\{{\theta }_1,{\theta }_2,\dots ,{\theta }_n\}$ — the set of possible states of nature.
• $u(s_i,{\theta }_j)$ — the payoff (utility) function for choosing strategy $s_i$ when state ${\theta }_j$ occurs. This is often represented by a payoff matrix $A=[a_{ij}]$, where $a_{ij}=u(s_i,{\theta }_j)$.

Savage's criterion is based on the concept of regret or opportunity loss. The regret $r(s_i,{\theta }_j)$ for strategy $s_i$ under state of nature ${\theta }_j$ is defined as the difference between the maximum possible payoff that could have been obtained for that state of nature ${\theta }_j$ (if the best strategy for that state had been chosen) and the actual payoff from strategy $s_i$.

The algorithm for applying Savage's criterion:

1. Calculate the regret (risk) matrix:

   a) Find the maximum payoff for each state of nature (each column of the payoff matrix):

   $u_j^{*}=\underset{k=1,\dots ,m}{\max }u(s_k,{\theta }_j)=\underset{k=1,\dots ,m}{\max }{a}_{kj}$

   This is the best possible result if state ${\theta }_j$ occurs.

   b) Calculate the elements of the regret matrix $R=[r_{ij}]$:**

   $r_{ij}=r(s_i,{\theta }_j)=u_j^{*}-u(s_i,{\theta }_j)=(\underset{k=1,\dots ,m}{\max }{a}_{kj})-a_{ij}$

   The element $r_{ij}$ shows how much the payoff from strategy $s_i$ is less than the maximum possible payoff under state ${\theta }_j$. All elements $r_{ij}\ge 0$.

1. Find the maximum regret for each strategy: For each strategy $s_i$ (each row of the regret matrix $R$), its worst possible outcome in terms of regret is determined:

   $r_i^{\max }=\underset{j=1,\dots ,n}{\max }{r}_{ij}=\underset{j=1,\dots ,n}{\max }((\underset{k=1,\dots ,m}{\max }{a}_{kj})-a_{ij})$

1. Choose the strategy with the minimum maximum regret (the minimax regret principle): The strategy $s_{\text{Savage}}^{*}$ that minimizes the found maximum regret is chosen:

   $s_{\text{Savage}}^{*}=\arg \underset{i=1,\dots ,m}{\min }(r_i^{\max })=\arg \underset{s_i\in S}{\min }(\underset{{\theta }_j\in \mathrm{\Theta }}{\max }r(s_i,{\theta }_j))$

   Or, substituting the expression for $r_{ij}$:

   $s_{\text{Savage}}^{*}=\arg \underset{i=1,\dots ,m}{\min }\left(\underset{j=1,\dots ,n}{\max }[(\underset{k=1,\dots ,m}{\max }{a}_{kj})-a_{ij}]\right)$

The minimum value of the maximum regret achieved using Savage's criterion is: $V_{\text{Savage}}=\underset{i=1,\dots ,m}{\min }(r_i^{\max })=\underset{i=1,\dots ,m}{\min }\left(\underset{j=1,\dots ,n}{\max }{r}_{ij}\right)$

Thus, Savage's criterion aims to select the strategy that guarantees the smallest losses relative to the best possible action for each state of nature.

Key points in the mathematical formulation:

• Definition of regret $r_{ij}$: This is the central concept. It is important to show that it is calculated as the difference between the best outcome in column j and the current outcome a_{ij}.
• Regret matrix $R$: It is explicitly stated how it is constructed.
• Finding $r_i^{\max }$: The search for the maximum in each row of the regret matrix is shown.
• Minimax principle: The choice of strategy is clearly formulated using $\arg \min$ of the $\max$ of regrets.
• Notation used: Standard for game theory and decision theory (S, Θ, u, a_ij, r_ij, max, min, arg min).

Advantages and Disadvantages

Advantages:

• Focuses on minimizing risks.
• Particularly effective under conditions of high uncertainty.

Disadvantages:

• Ignores expected profit, focusing only on potential losses.
• Can lead to overly conservative decisions.

Decision Criteria

• Hurwicz's Criterion
• Laplace's Criterion
• Wald's Criterion