♟️ Game theory elements

Antagonistic zero-sum games

Zero-sum antagonistic games are a class of game theory problems in which one player’s gain is exactly equal to the loss of another player (or several others). Simply put: whatever one player wins, another player loses. The sum of all players' winnings is always zero.

Game theory studies optimal strategies in situations where the outcome depends on the decisions of two or more participants, whose interests may coincide, conflict or be a mix of both.

A classic example: "Rock, Paper, Scissors"

This is a symmetric zero-sum antagonistic game:

+1 (win), 0 (draw), –1 (loss).

Symmetry means that the rules are the same for all players.

Nash equilibrium and mixed strategies

In "Rock, Paper, Scissors" there is no equilibrium in pure strategies (where a player always chooses the same action) because any fixed choice can be exploited. However, there is a Nash equilibrium in mixed strategies: each player chooses rock, paper or scissors with a probability of \( \frac{1}{3} \). With this approach, an opponent's expected payoff is independent of their own action and equals 0. Any deviation from this strategy (for example, increasing the frequency of choosing "rock") would allow a rational opponent to increase their average payoff.

Formally, if player A chooses rock with probability \(p_1\), scissors with \(p_2\) and paper with \(p_3\) (where \(p_1+p_2+p_3=1\)), and player B chooses the pure strategy "rock", then player A’s expected payoff is \(0\cdot p_1 + 1\cdot p_2 + (-1)\cdot p_3 = p_2 - p_3\). For player B to be indifferent as to which strategy to use in response, it is necessary that \(p_1=p_2=p_3=1/3\). This constitutes the equilibrium.

Expected value of the payoff in zero-sum games

For a game with a payoff matrix \(A\) (of size \(m \times n\)) and mixed strategies \(x\) (probabilities for player 1) and \(y\) (probabilities for player 2), the expected payoff for player 1 is \(x^T A y\). Player 1 seeks to maximize this value, while player 2 seeks to minimize it. Von Neumann’s minimax theorem states that in any finite zero-sum game, there exists a value of the game \(v\) and optimal mixed strategies such that: \[ \max_x \min_y x^T A y = \min_y \max_x x^T A y = v. \] This is a fundamental result that underlies many algorithms and applications.

In practice, this means that players can guarantee themselves an average payoff of at least \(v\) (for player 1) or at most \(v\) (for player 2) by using their optimal strategies, regardless of the opponent's actions.

Why is it important in practice?

"If one's opponent is predictable, one wins"

Imagine that a player's opponent in "Rock, Paper, Scissors" almost always starts with "rock". In that case, the player simply plays "paper" every time and wins. Any pattern or skew in probabilities creates an opportunity to be exploited.

“But a rational opponent adapts.”. As soon as the player begins to exploit its predictability, it will change its behavior. In response, the player changes the strategy once again. This process of adaptation ideally leads everyone to a Nash equilibrium: a state in which no one has an incentive to deviate unilaterally.

Where does this happen in the real world?

Sport. In a penalty kick, the goalkeeper chooses which way to dive, while the kicker decides where to aim the shot. The optimal strategy is to dive or shoot to the left or right with a 50% probability (sometimes accounting for the asymmetry between right-footed and left-footed players). If a goalkeeper notices that a kicker always aims for the left corner, they will start diving in that direction — and vice versa.

War games and cybersecurity. The attacker chooses the target, while the defender decides what to protect. Resources are limited. Randomizing the allocation of defense (a mixed strategy) prevents the opponent from achieving guaranteed success.

Business and bidding. Two companies are competing for a contract. If both follow a predictable pricing strategy, one will always be able to slightly undercut the other. It is optimal to occasionally make "illogical" bids.

Poker. Bluffing is a classic example of a mixed strategy: a player bets with a weak hand with a certain probability, ensuring that their opponent cannot always read them.

Key takeaway

If the opponent is adaptive, the best strategy is randomness (with precisely calculated probabilities).

If an opponent is predictable, exploit their patterns.

Expected value and Decision-making criteria

In antagonistic games, players often evaluate strategies based on their expected payoff. In practice, however, it is important to consider not only the mean but also the variance (risk). For instance, in a high-stakes poker tournament, a player might prefer a strategy with a lower EV but a smaller probability of going bust. While the mathematical expectation remains a fundamental benchmark, a comprehensive analysis may employ other criteria, such as the maximin principle (maximizing the minimum payoff) or the Savage criterion (minimizing regret).

In the game of "Rock, Paper, Scissors," the maximin strategy (choosing each option with equal probability) guarantees an EV of at least 0 (assuming the opponent plays optimally). If, for instance, the opponent always chooses "rock", the maximin strategy (1/3 probability for each move) yields an EV of 0, whereas a pure strategy of always choosing "paper" would yield an EV of +1. In this context, the maximin strategy does not exploit the opponent's weakness, but it does provide a safeguard against the worst-case scenario (i.e., if the opponent happens to play optimally).

Thus, the choice between exploitation and safety is a key dilemma in game theory, and its resolution depends on information about the opponent and the context of the game.