Department of AI&DS, BIT, Mangalore

Module 2

Subject Name and Code: Algorithmic Game Theory (BAI405D)

Faculty: Prof. Masooda

Department: Artificial Intelligence and Data Science

Department of AI&DS, BIT, Mangalore

• A Nash equilibrium is when every player in a game makes the best possible choice based on what others are doing, and no one wants to change their strategy.
• In a steady state, players behave the same way every time they play, and they don’t want to change their actions because they understand how others play.
• There are two types of steady states:
• Fixed actions – Every player always picks the same action.
• Probabilistic actions – Players choose actions based on a fixed probability.
• Both types are equivalent because, in the end, the probability of an action being chosen remains the same. This probabilistic steady state is called a stochastic steady state and is modeled by a mixed strategy Nash equilibrium, meaning players make choices randomly but in a predictable way.

Introduction

Stochastic steady states

Department of AI&DS, BIT, Mangalore

• Matching Pennies is a two-player zero-sum game, where:
• Each player (Player 1 and Player 2) can choose between Head (H) or Tail (T).
• If the players choose the same action (H, H) or (T, T), Player 1 loses $1, and Player 2 gains $1.
• If the players choose different actions (H, T) or (T, H), Player 1 gains $1, and Player 2 loses $1.

Example: Matching Pennies

Department of AI&DS, BIT, Mangalore

A Nash equilibrium is a strategy profile where no player has an incentive to unilaterally deviate. However, in pure strategies, this game has no equilibrium because:

• If Player 1 always picks Head, then Player 2 will always pick Tail to maximize their winnings.
• If Player 2 always picks Tail, then Player 1 will switch to Tail to maximize their winnings.
• This cycle continues, meaning there is no stable pair of pure strategies.

Thus, we must consider mixed strategies, where players randomize their actions.

Department of AI&DS, BIT, Mangalore

A stochastic steady state is a probability distribution over strategies where no player has an incentive to deviate.

Let’s assume:

• Player 2 chooses Head with probability ​ and Tail with probability
• Player 1 chooses Head with probability p and Tail with probability 1−p.

(Refer Notes)

• Since the probabilities balance out, Player 1 is indifferent to choosing any value of p, meaning they should randomize equally.

(Refer Notes)

• A similar analysis for Player 2 shows that their optimal choice is also to randomize equally.

Thus, the only stable mixed strategy equilibrium is:

​where each player chooses Head and Tail with equal probability.

Department of AI&DS, BIT, Mangalore

To confirm that this is the only stochastic steady state, assume Player 2 chooses Head with probability q, so they choose Tail with probability 1−q.

(Refer Notes)

Department of AI&DS, BIT, Mangalore

Case:

Department of AI&DS, BIT, Mangalore

Generalizing the analysis: expected payoffs

• In simple games like Matching Pennies, players either win $1 or lose $1. It’s easy to decide which is better.
• But in games with more than two possible outcomes (A, B, C, etc.), preferences become more complicated.
• A player who prefers A > B > C may face a choice:
• A lottery where A and C each happen 50% of the time
• A guaranteed outcome B
• We can’t predict what they’ll choose just from knowing they prefer A > B > C.

Department of AI&DS, BIT, Mangalore

• To compare uncertain choices, we assign payoff values to outcomes.
• A player chooses based on expected value.
• Example: If
• u(A) = 10, u(B) = 5, u(C) = 0
• The expected payoff of a lottery with 50% A and 50% C is: (0.5×10)+(0.5×0)=5
• If B has a payoff of 5, the player doesn’t care whether they pick B or the lottery.

This method is based on the von Neumann-Morgenstern (vNM) utility, which helps predict choices under uncertainty.

Department of AI&DS, BIT, Mangalore

People don’t always act the same way toward risk:

• Risk-Averse Players prefer a guaranteed small reward over a riskier big one.
• Example: Buying insurance to avoid a big loss.
• Risk-Seeking Players prefer a gamble with a chance of a big win.
• Example: Buying lottery tickets, even if the odds are low.
• Risk-Neutral Players only care about expected value.
• Example: Indifferent between $50 guaranteed and a 50% chance of winning $100.

• A payoff function that represents preferences over lotteries is called a Bernoulli payoff function (named after Daniel Bernoulli).
• It assigns numerical values to deterministic outcomes in a way that allows us to calculate expected payoffs.

Department of AI&DS, BIT, Mangalore

• There are many ways to assign payoff numbers, as long as the order of preferences stays the same.
• Many different payoff functions can represent the same preferences.
• Suppose a player prefers a > b > c and is indifferent between b and a 50-50 lottery between a and c.
• Possible utility assignments:
• u(a)=3, u(b)=2, u (c)=1
• u(a)=10, u(b)=5, u(c)=0
• As long as the highest payoff exceeds the lowest, different scales can represent the same preferences.
• Different numbers, but same preferences.

Department of AI&DS, BIT, Mangalore

Strategic games in which players may randomize

Bernoulli Payoffs vs Ordinal Preferences

• In earlier game representations, numbers in payoff tables reflected ordinal preferences (just ranking of outcomes).
• Now, they represent expected values of lotteries—this gives more detail, including how much players prefer one outcome over another.

DEFINITION: A strategic game (with vNM preferences) consists of

• a set of players
• for each player, a set of actions
• for each player, preferences regarding lotteries over action profiles that may be represented by the expected value of a (“Bernoulli”) payoff function over action profiles.

Department of AI&DS, BIT, Mangalore

• The interpretation of payoffs matters: two tables that look the same may represent different strategic situations.
• With vNM preferences, comparing strategic games becomes more complex.
• The same-looking game can lead to different conclusions depending on how players value risky outcomes.

Department of AI&DS, BIT, Mangalore

Mixed strategy Nash equilibrium

• A mixed strategy is a probability distribution over a player’s possible actions.
• It generalizes the idea of a player choosing a single action to randomly selecting actions with certain probabilities.
• For example, in Matching Pennies, a mixed strategy might be ½ for Head and ½ for Tail.
• Mixed strategies can be written as lists of probabilities (e.g., (⅓, ⅔) means ⅓ probability for the first action and ⅔ for the second).
• A pure strategy is a special case where one action is chosen with probability 1.

Department of AI&DS, BIT, Mangalore

• It is an extension of the Nash equilibrium concept to include randomized (mixed) strategies.
• Each player chooses a probability distribution over their available actions.
• The equilibrium occurs when no player can improve their expected payoff by changing their own strategy while others keep theirs fixed.
• In other words, each player’s strategy is the best response to the strategies of the other players.
• Players compare lotteries over outcomes (random results) and choose strategies based on expected payoff values.

Equilibrium

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

• Best response functions help identify mixed strategy Nash equilibria, just like in games with pure strategies.
• Player i's best response function, denoted Bi, gives the set of best mixed strategies for player i in response to the other players’ mixed strategies (α−i).

Best response functions

Department of AI&DS, BIT, Mangalore

Best response functions in two-player two-action games

• In two-player games where each player has two actions (like Matching Pennies), the best response to the opponent’s mixed strategy is either:
• A single pure strategy, or
• Any mixed strategy (i.e., all mixed strategies are equally good).
• Example from Matching Pennies:
• If Player 2 chooses Head with a probability less than ½, Player 1’s best response is Tail.
• If Player 2 chooses Head with more than ½, Player 1’s best response is Head.
• If Player 2 chooses Head with exactly ½, any mix of Head and Tail is equally good for Player 1.
• This pattern holds for any 2-player, 2-action game because the expected payoffs are linear functions of the mixed strategies.

Department of AI&DS, BIT, Mangalore

Consider a two-player game in which each player has two actions, T and B for player 1 and L and R for player 2.

Denote by ui, for i = 1, 2, a Bernoulli payoff function for player i. (That is, ui is a payoff function over action pairs whose expected value represents player i’s preferences regarding lotteries over action pairs.)

Player 1’s mixed strategy α1 assigns probability α1(T) to her action T and probability α1(B) to her action B (with α1(T) + α1(B) = 1).

For convenience, let p = α1(T), so that α1(B) = 1 − p. Similarly, denote the probability α2(L) that player 2’s mixed strategy assigns to L by q, so that α2(R) = 1 − q.

​

• There are two players in the game.
• Player 1 has actions: T (Top) and B (Bottom).
• Player 2 has actions: L (Left) and R (Right).

Department of AI&DS, BIT, Mangalore

• Each player has a payoff function, denoted by u₁ for Player 1 and u₂ for Player 2.
• These are Bernoulli payoff functions, meaning the expected payoff represents the player's preferences over possible outcomes (lotteries over action pairs).
• A mixed strategy is a probability distribution over a player's actions.
• Player 1's mixed strategy α₁ assigns:
• Probability p to action T
• Probability 1 − p to action B
• Player 2's mixed strategy α₂ assigns:
• Probability q to action L
• Probability 1 − q to action R
• The players choose their actions independently (no coordination or signaling).
• So, the joint probability of any outcome is the product of the individual probabilities.

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

The expected payoff is constant regardless of p, and the graph is a horizontal line. Every mixed strategy—including pure strategies—is equally optimal.

​

A mixed strategy with 0<p< 1(i.e., a true mixture of T and B) is never a unique best response. It is either not optimal at all, or all mixed strategies are best responses in the case of equal expected payoffs from both pure strategies.

Department of AI&DS, BIT, Mangalore

Analyze the game of ‘Matching Pennies’ and apply the method of best responses to find mixed strategy Nash Equilibrium.

• Matching Pennies is a two-player, zero-sum game where both players simultaneously choose Head (H) or Tail (T).
• If their choices match (both choose Head or both choose Tail), Player 2 pays $1 to Player 1.
• If their choices differ (one chooses Head, the other chooses Tail), Player 1 pays $1 to Player 2.

Department of AI&DS, BIT, Mangalore

A pure strategy Nash equilibrium occurs when neither player wants to unilaterally change their strategy. However:

• If Player 1 always chooses Head, Player 2 will always choose Tail to win.
• If Player 1 always chooses Tail, Player 2 will always choose Head to win.
• Similarly, Player 2 has no fixed best choice since Player 1 would always counter it.
• This means there is no pure strategy Nash equilibrium.

​

To find the mixed strategy equilibrium, we assume that:

• Player 1 plays Head with probability p and Tail with probability 1 - p.
• Player 2 plays Head with probability q and Tail with probability 1 - q.

​

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

• Matching Pennies has no Nash equilibrium
• The mixed strategy equilibrium is:

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

• p be the probability that Player 1 (row player) plays T
• q be the probability that Player 2 (column player) plays L

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

In any finite game, a player’s expected payoff under a mixed strategy profile is a weighted average of her expected payoffs from her pure strategies, where the weights are the probabilities she assigns to each strategy.

Characterization of Mixed Strategy Nash Equilibrium

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

A useful characterization of the mixed strategy Nash equilibrium

• Every strategic game where each player has finitely many actions always has at least one mixed strategy Nash equilibrium.
• This is a guaranteed existence result—even if it's hard to find the equilibrium, we know it must exist.
• The result only requires that each player has a finite number of actions.
• It's not necessary—some games with infinitely many actions also have equilibria.
• A mixed strategy equilibrium might be a pure strategy (if a player puts probability 1 on one action).

Department of AI&DS, BIT, Mangalore

• This proposition provides a simple and practical way to check if a mixed strategy profile is a Nash equilibrium, by looking only at players' expected payoffs to pure strategies.

​

PROPOSITION (Characterization of mixed strategy Nash equilibrium of finite game)

Department of AI&DS, BIT, Mangalore

• Every pure strategy that is played (i.e., given positive probability) must give the same payoff.
• Any strategy not played must not give a higher payoff.
• This helps verify equilibria using only pure strategy payoffs, without computing complex best responses.

Department of AI&DS, BIT, Mangalore

Example – Battle of the Sexes (BoS):

Therefore, the pair is a mixed strategy Nash equilibrium (since all played actions give the same payoff, and no unplayed action gives more).

Department of AI&DS, BIT, Mangalore

Battle of the Sexes Game:

• Two players: Player 1 and Player 2
• Two choices: B (Ballet) or S (Soccer)
• Both prefer to be together, but have different favorite outcomes.

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Dominated actions

• In a strategic game with ordinal preferences, one action of a player strictly dominates another action if it is superior, no matter what the other players do.
• In a game with vNM preferences in which players may randomize, we extend this definition to allow an action to be dominated by a mixed strategy.

Department of AI&DS, BIT, Mangalore

Department of AI&DS, BIT, Mangalore

Strictly Dominated Actions:

• A strictly dominated action gives lower payoffs than some mixed strategy against every possible strategy of the other players.
• So, it is never a best response.
• A strictly dominated action is never used (not even with small probability) in any mixed strategy Nash equilibrium.

​

Weakly Dominated Actions:

• A weakly dominated action gives payoffs no better than some mixed strategy in all cases and strictly worse in at least one case.
• A weakly dominated action can still be used in a mixed strategy equilibrium.
• So, we cannot eliminate weakly dominated actions automatically.

Department of AI&DS, BIT, Mangalore

Figure 117.1 (in which only player 1’s payoffs are given) shows that an action that is not strictly dominated by any pure strategy may be strictly dominated by a mixed strategy.

The action T of player 1 is not strictly dominated by either M or B, but it is strictly dominated by the mixed strategy that assigns probability ½ to M and ½ to B.

Show that this is true.