Syllabus
II Games with Imperfect Information
Ch 09: Bayesian Games
● Motivational Examples
● General Definitions
● Information aspects
● Illustrations
Ch 10: Extensive Games with Imperfect Information
● Strategies
● Nash Equilibrium
● Beliefs and sequential equilibrium
● Illustrations
III Variants and Extension
Ch 14: Repeated Games……………………………………………………………………
● The Prisoner’s Dilemma………………………………………
Ch 16: Bargaining……………………………………………………………………
References Mapped Lingo
1. GT Scanned Book => Game Theory 2009
2. Draft Book => Introduction to Game Theory
1
Bayesian Games
A “Bayesian game” generalizes the notion of a strategic game to allow us to
analyze any situation in which each player is imperfectly informed about some
aspect of her environment relevant to her choice of an action.
Prerequisite for this example : chapter 2 - Mixed strategy equilibrium
Example of a game with imperfect information
1. EXAMPLE 271.1 (Variant of BoS with imperfect information)
Consider a variant of the situation modeled by BoS (Figure 16.1) in which
player 1 is unsure whether player 2 prefers to go out with her or prefers to
avoid her, whereas player 2, as before, knows player 1’s preferences.
Specifically, suppose player 1 thinks that with probability “1/2" player 2 wants
to go out with her, and with probability “1/2" player 2 wants to avoid her.
That is, player 1 thinks that with probability 1/2 she is playing the game on the
left of Figure 272.1 and with probability 1/2 she is playing the game on the
right. Because probabilities are involved, an analysis of the situation requires us
to know the players’ preferences over lotteries, even if we are interested only in
pure strategy equilibria; thus the numbers in the tables are Bernoulli payoffs.
We can think of there being two states, one in which the players’ Bernoulli
payoffs are given in the left table and one in which these payoffs are given in
2
the right table. Player 2 knows the state—she knows whether she wishes to
meet or avoid player 2—whereas player 1 does not; player 1 assigns probability
“1/2" to each state.
The notion of Nash equilibrium for a strategic game models a steady state in
which each player’s beliefs about the other players’ actions are correct, and
each player acts optimally, given her beliefs. We wish to generalize this notion
to the current situation.
From player 1’s point of view, player 2 has two possible types, one whose
preferences are given in the left table of Figure 272.1, and one whose
preferences are given in the right table. Player 1 does not know player 2’s type,
so to choose an action rationally she needs to form a belief about the action of
each type. Given these beliefs and her belief about the likelihood of each type,
she can calculate her expected payoff to each of her actions. For example, if she
thinks that the type who wishes to meet her will choose B and the type who
wishes to avoid her will choose S, then she thinks that B will yield her a payoff
of 2 with probability 1/2 and a payoff of 0 with probability 1/2 , so that her
expected payoff is 1/2 · 2 + 1/2 · 0 = 1, and S will yield her an expected payoff
of 1/2 · 0 + 1/2 · 1 = 1/2 . Similar calculations for the other combinations of
actions for the two types of player 2 yield the expected payoffs in Figure 273.1.
Each column of the table is a pair of actions for the two types of player 2, the
first member of each pair being the action of the type who wishes to meet
player 1 and the second member being the action of the type who wishes to
avoid player 1.
That is, we treat the two types of player 2 as separate players, and analyze the
situation as a three-player strategic game in which player 1’s payoffs as a
function of the actions of the two other players (i.e. the two types of player 2)
are given in Figure 273.1, and the payoff of each type of player 2 is
independent of the actions of the other type and depends on the action of
player 1 as given in the tables in Figure 272.1 (the left table for the type who
wishes to meet player 1, and the right table for the type who wishes to avoid
player 1).
3
In a Nash equilibrium, player 1’s action is a best response in Figure 273.1 to the
pair of actions of the two types of player 2, the action of the type of player 2
who wishes to meet player 1 is a best response in the left table of Figure 272.1
to the action of player 1, and the action of the type of player 2 who wishes to
avoid player 1 is a best response in the right table of Figure 272.1 to the action
of player 1.
I claim that (B, (B, S)), where the first component is the action of player 1 and
the other component is the pair of actions of the two types of player 2, is a
Nash equilibrium. Given that the actions of the two types of player 2 are (B, S),
player 1’s action B is optimal, from Figure 273.1; given that player 1 chooses B,
B is optimal for the type who wishes to meet player 2 and S is optimal for the
type who wishes to avoid player 2, from Figure 272.1. Suppose that in fact
player 2 wishes to meet player 1. Then we interpret the equilibrium as follows.
Both player 1 and player 2 choose B; player 1, who does not know if player 2
wants to meet her or avoid her, believes that if player 2 wishes to meet her she
will choose B, and if she wishes to avoid her she will choose S.
4
Ch10: Extensive Games with Imperfect Information
Quick Overview:
● Extensive Games with Imperfect Information (Section 10.1)
These games model scenarios where players make decisions at
different stages, but not all players have complete information about
earlier moves.
● Strategies (Section 10.2)
The set of strategies defines the possible actions a player can take,
considering all contingencies they might face in a game.
● Nash Equilibrium (Section 10.3)
A Nash equilibrium occurs when no player can improve their
outcome by changing their strategy alone, assuming all other players'
strategies remain unchanged.
● Beliefs and Sequential Equilibrium (Section 10.4)
In a sequential equilibrium, players form beliefs about where they
are in the game, and this concept improves upon Nash equilibrium by
accounting for these beliefs in extensive-form games with sequential
moves.
● Signaling Games (Section 10.5)
These are games where one party (the "sender") sends a signal to
convey information to another party (the "receiver"), which impacts their
decisions.
5
Establishing Understanding
A partition of a set A is a collection {A1,...,Ak} of subsets of A such that every
member of A is in exactly one of the sets Aj. The set {Paris,Venice,Havana},for
example has five partitions: {{Paris}, {Venice}, {Havana}}, {{Paris,Venice},
{Havana}}, {{Paris,Havana}, {Venice}}, {{Paris}, {Venice,Havana},
and{{Paris,Venice,Havana}}
6
Definition 314.1 (Extensive game) An extensive game (with imperfect
information and chance moves) consists of:
● a set of players
● a set of sequences (terminal histories) having the property that no
sequence is a proper subhistory of any other sequence
● a function (the player function) that assigns either a player or "chance"
to every sequence that is a proper subhistory of some terminal history
● a function that assigns to each history that the player function assigns to
chance a probability distribution over the actions available after that
history, with the property that each such probability distribution is
independent of every other distribution
● for each player, a partition (the player's information partition) of the
set of histories assigned to that player by the player function
● for each player, preferences over the set of lotteries over terminal
histories.
The simplest extensive games, in which each player moves once and no
player, when moving, is informed of any other player's action, model situations
that may alternatively be modeled as strategic games, as illustrated by the next
example.
7
shows her card to player 2. (Player 2 does not have any card for player 1 to
see, but you can imagine her holding a fixed card with value between High and
Low. In Exercise 316.1 you are asked to consider a situation in which player 2,
like player 1, is dealt a card.) If player 1's card is High she takes the money in
the pot, and if it is Low player 2 takes the money in the pot; in both cases the
game ends. If player 1 raises, she adds a dollar to the pot and player 2
chooses whether to pass or meet. If player 2 passes, player 1 takes the
money in the pot. If player 2 meets, she adds a dollar to the pot, and player 1
shows her card. If the card is High, player 1 takes the money in the pot, while
if it is Low player 2 does so.
An extensive game that models this situation is shown in Figure 316.1. Player 1
has two information sets, one containing the single history High and one
containing the single history Low. Player 2 has one information set, consisting
of the two histories (High, Raise) and (Low, Raise). This information set
reflects the fact that player 2 cannot observe player 1's card. Note that again
the requirement that the set of actions at every history within an information
set be the same is satisfied at player 2's information set.
Strategies in extensive game
8
9
Nash equilibrium of extensive game
10
Example
11
In summary, the game in which player 1 moves first and her action is perfectly
observable has a unique subgame perfect equilibrium, the outcome of which is
that both players choose X, whereas the game in which player 1’s action is
observable with error has a pure strategy Nash equilibrium in which the
outcome is that both players choose Y, regardless of how small the error.
Thus the advantage gained by the commitment entailed in being the
first-mover, as reflected in the subgame perfect equilibrium of the game with
perfect information, is completely lost in the pure strategy Nash equilibrium of
the game in which the second player’s observation of the first-mover’s action is
even slightly imperfect. Why? Suppose both player 1 and player 2 choose Y,
and consider the implications of player 1’s switching to X. In the game with
perfect information, player 2’s observation of X is inconsistent with the
equilibrium; she interprets it as a deviation, to which she optimally responds by
12
choosing X, making the deviation worthwhile for player 1. In the game with
imperfect information, player 2’s observation of X is consistent with the
equilibrium; she interprets it as an inaccurate signal (regardless of how unlikely
such a signal is) and continues to choose Y, making player 1's deviation
undesirable for her.
Beliefs and Sequential Equilibrium
A Nash equilibrium of a strategic game may be characterized by two
requirements: that each player choose her best action given her belief about
the other players, and that each player's belief be correct (see page 21). The
notion of equilibrium I now define for extensive games embodies the same two
requirements, and, like the notion of subgame perfect equilibrium for extensive
games with perfect information, insists that they hold at each point at which a
player has to choose an action. When defining a Nash equilibrium of a strategic
game precisely, we do not need to consider the players' beliefs separately from
their strategies because the requirement that the beliefs be correct completely
determines them: each player's belief about every other player's strategy is
simply equal to that strategy. For an extensive game, the players' strategies
may not completely determine their beliefs, as we have just seen in the game in
Figure 323.1. Thus we are led to define a notion of equilibrium for pairs
consisting of a strategy profile and a collection of beliefs.
Beliefs
We assume that at an information set that contains more than one history, the
player whose turn it is to move forms a belief about the history that has
occurred. We model this belief as a probability distribution over the histories in
the information set. (At an information set containing a single history, the only
possible belief assigns probability 1 to that history.) We call a collection of
beliefs, one for each information set of every player, a belief system.
Example
13
Imagine a game of rock-paper-scissors. If you believe your opponent is more likely to play rock, you
might choose paper. However, if your belief is wrong, and they actually choose paper, you will lose.
Remember: The key is to understand that beliefs are crucial in decision-making, especially in games
where players have limited information about each other's actions.
DEFINITION 324.2 (Behavioral strategy in extensive game) A behavioral strategy of player i in an
extensive game is a function that assigns to each of i's information sets I; a probability distribution
over the actions in A(I;), with the property that each probability distribution is independent of every
other distribution.
A behavioral strategy assigns probability 1 to a single action, making it equivalent to a pure
strategy.
In all games discussed, mixed strategies and behavioral strategies are functionally equivalent,
though behavioral strategies are easier to work with.
Example 314.2 (BoS as an extensive game):
● Each player has a single information set.
● A behavioral strategy for each player is a single probability distribution over their actions.
● Therefore, each player's set of behavioral strategies is identical to their set of mixed
strategies.
Example 315.1 (card game):
● Player 1 has two information sets, so her behavioral strategy is defined by a pair of
probability distributions over the set {Raise, See}.
● A mixed strategy for Player 1 is a single probability distribution over her four pure strategies:
{(Raise, Raise), (Raise, See), (See, Raise), (See, See)}.
A behavioral strategy is specified by two numbers (probabilities of actions for different scenarios),
while a mixed strategy is defined by three numbers (because the probabilities must sum to 1).
Behavioral strategies are conceptually simpler but do not limit a player's options, as every mixed
strategy can be matched by an equivalent behavioral strategy.
10.4.3 Equilibrium
DEFINITION 325.1 (Assessment) An assessment in an extensive game is a
pair consisting of a profile of behavioral strategies and a belief system.
An assessment is an equilibrium if it satisfies the following two requirements
Sequential rationality : Each player's strategy is optimal whenever she has to
move, given her belief and the other players' strategies.
Consistency of beliefs with strategies : Each player's belief is consistent with the
strategy profile.
14
The diagram illustrates a game with two players, where player 1 moves first,
followed by player 2. The branches represent the possible actions, and the
numbers in brackets at the end of histories represent player 2's beliefs about
the history that has occurred.
Key Points:
1. Sequential Rationality: This concept requires that each player's
strategy is optimal, given their belief and the other player's strategy. In
other words, each player should make the best decision at every point in
the game, considering their current situation and expectations.
2. Beliefs: The numbers in brackets represent player 2's beliefs about which
history (C or D) has occurred. These beliefs are crucial for determining
her optimal action.
3. Expected Payoffs: Player 2 calculates her expected payoff for each
action (F and G) based on her beliefs and the subsequent actions of
player 1. She chooses the action with the highest expected payoff.
4. Optimal Action: In this case, given player 1's strategy and player 2's
beliefs, player 2's optimal action is G. This is because her expected payoff
from G is higher than her expected payoff from F.
Explanation of the Diagram:
● Player 1's Strategy: Player 1 chooses action E at the beginning, and
then chooses action J if history C,F occurs.
● Player 2's Beliefs: Player 2 believes that history C has occurred with
probability 1/3 and history D with probability 2/3.
15
● Expected Payoffs: Player 2 calculates her expected payoffs for actions F
and G:
○ F: (1/3 1) + (2/3 1) = 1
○ G: (1/3 0) + (2/3 2) = 4/3
● Optimal Action: Since the expected payoff for G is higher, player 2's
optimal action is G.
In essence, the diagram shows that player 2's decision is rational based
on her beliefs and the expected outcomes of her actions.
Bayesian probability calculation. It represents the probability of a specific
history, h , occurring, given a strategy profile, β, and conditional on the
information set, I, being reached.
● Pr(h according to β): This represents the probability of history h
occurring if the players follow the strategy profile β.
● Σh∈I Pr(h according to β): This is the summation of the probabilities
of all possible histories, h, that could occur within the information set I,
given the strategy profile β.
The equation essentially calculates the probability of h occurring relative to the
overall probability of reaching the information set I. In other words, it measures
the likelihood of h happening within the context of the given information set
and strategy profile.
This formula is often used in game theory to analyze decision-making under
uncertainty, where players need to assess the probability of different outcomes
based on their available information and strategies.
16
Bargaining:
Introduction
Bargaining in game theory involves two or more players negotiating to reach a
mutually beneficial agreement while balancing their own interests. The
principles of bargaining revolve around strategic decision-making, cooperation,
and conflict resolution.
Basic Principles of Bargaining
1. Mutual Benefit: The objective is to find an agreement that benefits all
parties compared to the outcome of no agreement (disagreement point).
2. Disagreement Point: This is the outcome if no agreement is reached.
Players aim to negotiate a deal better than this baseline.
3. Pareto Efficiency: An agreement is Pareto efficient if no player can be
made better off without making another player worse off.
4. Fairness: While fairness isn't always a strict requirement, many
bargaining scenarios consider equitable outcomes based on players’
contributions or needs.
5. Strategic Moves: Players use offers, counteroffers, and strategies to
maximize their share of the agreement's value.
Reaching an Agreement
1. Credible Offers:
○ Players propose offers that they can commit to and expect the other
party to consider.
2. Patience and Time Preference:
○ The party with a higher discount factor (more patience) can
negotiate a better deal.
3. Information Asymmetry:
○ Sharing or withholding information strategically affects the
bargaining process.
4. Threats and Promises:
○ Players may use threats (credible commitment to disagreement) or
promises to influence outcomes.
5. External Factors:
○ Social norms, external enforcement, or regulations can guide or
constrain bargaining.
17
18
Bargaining as an extensive game:
19
20
Infinite Horizon Game with Alternating Offers and Impatient Players
Definition: A version of the bargaining model where players can make
counteroffers indefinitely after rejecting an offer. This game has no deadline and
can continue infinitely.
Terminal Histories:
● Infinite rejection: Every offer is rejected, resulting in an infinite
sequence (x¹, N, x², N, ...).
● Finite acceptance: Offers are rejected until a proposal is accepted in
period t, resulting in a finite sequence (x¹, N, x², N, ..., x^t, Y).
21
22
23
24
25
26