Algorithmic Game theory
Module-4:Bayesian games
Dr. K. A. VIDYA
Department of Mathematics
Dayananda Sagar Academy of Technology and Management
Bangalore -560 082
July 12, 2024
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games
A strategic game with imperfect information is called
Bayesian Game
The model of an Bayesian game allows us to analyze any
situation where player is imperfectly informed about some
aspect of her environment relevant to her choice of an
action.
A bayesian Game consists of
A set of players
A set of states
A set of actions
A set of signals
Belief
Payoffs
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian games-EX-1
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games:Example 1
Here player 1 doesn’t know about player2. If she thinks that
the type who wishes to meet her will choose B and type who
wishes to avoid will choose S, then her payoff for choosing
B is 2*(1/2) + 0 * (1/2)=1
S is 0*(1/2) + 1 * (1/2)=1
Similar calculations for other combinations???
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games:Example 1
(B,B) (B,S) (S,B) (S,S)
Expected Payoffs are B 2,1/2 1,3/2 1,0 0 ,1
S 0 ,1/2 1/2,0 1/2,3/2 1,1
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Model:Ex1
Players: The pair of people
States: Meet, Avoid
Actions: B,S
Signals: Player 1 receives a single signal,z
Her signal function τ1 satisfies τ1 (meet)=z and τ1 (avoid)=z
Player 2 recieves two signals say m and n.
Her signal function τ2 satisfies τ2 (meet)=m and τ2 (avoid)=n
Belief: Player1 assigns probability (1/2) to each state and
Player 2 assigns probability 1 to each state
Payoffs: As given in the table
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games:Nash Equilibrium
Nash Equilibrium is a triple of actions, one for player 1 and
one for each type of player2, with the property that
1. The action of player 1 is optimal, given the actions of the
two types of player 2
2. The action of each type of player 2 is optimal given the
action of player 1
In example 1, (B, (B,S)) is a Nash Equilibrium
(B,B) (B,S) (S,B) (S,S)
∗ ∗
B 2 ,1/2 1 , 3/2 ∗ ∗
1 ,0 0,1
S 0 ,1/2 1/2,0 1/2,3/2∗ 1∗ , 1
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian games-EX-2
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games:Example 2
Here both players doesn’t know about the other player.
Player 1 will think that player 2 wants to meet her with prob-
ability (1/2) and wants to avoid her with probability(1/2).
Player 2 will think that player 1 wants to meet her with prob-
ability (2/3) and wants to avoid her with probability(1/3).
Model this situation by introducing 4 states- yy(both wants
to meet the other), yn(P1 wants to meet, P2 wants to avoid),
ny(P1 wants to avoid, P2 wants to meet), nn(both wants to
avoid)
P1 receives the signal y1 for the states yy and yn
P1 receives the signal n1 for the states ny and nn
P2 receives the signal y2 for the states ny and yy
P2 receives the signal n2 for the states yn and nn
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games:Example 2
Expected payoffs of player 1 of type y1 are
(B,B) (B,S) (S,B) (S,S)
B 2,1/2 1,3/2 1,0 0 ,1
S 0 ,1/2 1/2,0 1/2,3/2 1,1
Expected payoffs for other types???
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games:Example 2
Expected payoffs of player 1 of type n1 are
(B,B) (B,S) (S,B) (S,S)
B 0,1/2 1,3/2 1,0 2,1
S 1,1/2 1/2,0 1/2,3/2 0,1
Expected payoffs of player 2 of type y2 are
(B,B) (B,S) (S,B) (S,S)
B 4/3, 1 5/3,2/3 0, 1/3 1/3, 0
S 2/3, 0 0, 2/3 4/3, 4/3 2/3, 2
Expected payoffs of player 2 of type n2 are
(B,B) (B,S) (S,B) (S,S)
B 4/3,0 5/3, 1/3 0,2/3 1/3 1
S 2/3,2 0,4/3 4/3, 2/3 2/3, 0
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Model:Ex2
Players: The pair of people
States: {yy,yn,ny,nn}
Actions: B,S
Signals:
Player 1 receives two signals, y1 and n1 .
Her signal function τ1 satisfies
τ1 (yy)=τ1 (yn)= y1 and τ1 (ny)=τ1 (nn)= n1
Player 2 receives two signals, y2 and n2 .
Her signal function τ2 satisfies
τ2 (yy)=τ2 (ny)= y2 and τ2 (yn)=τ2 (nn)= n2
Belief: Player1 assigns probability (1/2) to each state and
Player 2 assigns probability 1 to each state
Payoffs: As given in the table
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games:Nash Equilibrium
In this example ((B,B),(B,S)) and ((S,B),(S,S)) are Nash
Equilibrium.(Prove by marking best response for each of the
above tables)
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian games-EX-3
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games with more information:Example 3
Here there are two states w1 and w2. Neither of the players
knows the state.
Let 0 < e < 1/2. Let p be the probability player 1 assigns
to T.
Player 2’s expected payoff for L is
(1/2)2e+(1/2)2e=2e if P1 chooses T
(1/2)2+(1/2)2=2 if P1 chooses B
Player 2’s expected payoff for M is
(1/2)0+(1/2)3e=3e/2 if P1 chooses T
(1/2)0+(1/2)3=3/2 if P1 chooses B
Player 2’s expected payoff for R is
(1/2)3e+(1/2)0=3e/2 if P1 chooses T
(1/2)3+(1/2)0=3/2 if P1 chooses B
Thus Player 2’s unique best response to every strategy of
player 1 is L
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games with more information:Example 3
Player 2’s Expected payoff is (1/2)2ep+(1/2)2(1-
p)+(1/2)2ep+(1/2)2(1-p)= 2-2(1-e)p if he choose L
and (3/2)-(3/2)(1-e)p if he chooses M or R
Player 1,s unique best response to L is B
Thus (B,L) is the unique Nash Equilibrium which gives a
payoff 2 to player 2 and player 1.
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games with more information:Example 3
Consider a variant of this game where player 2 is informed
of the state.
Then in state w1 player 2 chooses R and in state w2 player
2 chooses M(Strict Dominance)
In both the cases, player 1’s best response is T
Thus (T,(R,M) is the unique Nash Equilibrium, which gives
a payoff 3e to player 2.
Thus eventhough with more information, his payoff is less
here.
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian games-EX-4
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games with more information:Example 4
Bayesian game models not only situations in which players
are uncertain about each other’s preferences, but also un-
certain about others knowledge
Here there are three states w1, w2 and w3.
Player 2’s preferences are same in all states. Player 1’s
preferences are different in w1 and w2 and player 2 doesn’t
know that.
In w3 each player knows the preferences and player 2
knows that player 1 knows that. But player 1 doesn’t know
that player 2 knows this.
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian Games with more information:Example 4
In W1, player1 chooses R(strict dominance)
In W1,W2- player1 chooses (R,L) or (R,R)(Player 1
chooses only R in W1). The payoff’s for player 2 is
(R,L) (R,R)
L 1/2 0 Thus Player 2 chooses R
R 3/4 1
In W2,W3- player2 chooses (R,L) or (R,R)(In W2, Player 2
chooses only R). Then Payoff’s for player 1 are
(R,L) (R,R)
L 1/2 0 Thus Player 1 chooses R
R 3/4 1
In W3, since Player 1 chooses R, Player 2’s best response
is R
Thus in all cases both players chooses R
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Cournot’s duopoly game with imperfect Information
In Counout’s model, assume that firm 1 doesn’t know firm 2’s
cost function. He believes firm 2’s cost function is cL with proba-
bility p and cH with probability 1-p, where cL < cH .
Players: The two firms
States: {L,H}
Actions: Set of its possible outcomes
Signals:
Firm 1 receives only one signal, τ1 (H)= τ2 (L)
Firm 2 receives two signals, τ1 (H) and τ2 (L)
Beliefs: Player1 assigns probability p to each state L and
probability 1-p to H
Player 2 assigns probability 1 to each state
Payoffs: Firm 1’s profit is π=q1 P(q1 + q2 )-c(q1 ) and Firm
2’s profit is π=q2 P(q1 + q2 )-cL (q2 ) or Firm 2’s profit is
π=q2 P(q1 + q2 )-cH (q2 ).
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Bayesian games-EX-3
A Nash Equilibrium of this game is a triplet(q1∗ , qL∗ , qH∗ ), such that
q1∗ maximises firm 1’s profit given the outputs qL∗ of type L
and qH∗ of type H.
qL∗ maximises firm 2’s profit of type L given the outputs q1∗
of firm 1
qH∗ maximises firm 2’s profit of type H given the outputs q1∗
of firm 1
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Cournot’s duopoly game with imperfect Information
To find an equilibrium , we first find the firm’s best responses
The best response of firm 1 b1 solves
max[pq1 P(q1 + qL )-c(q1 ) + (1-p)q1 P(q1 + qH )-c(q1 )]
The best response of firm 2 bL solves
max[qL P(q1 + qL )-cL (qL )
The best response of firm 2 bH solves
max[qH P(q1 + qH )-cH (qH )
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Cournot’s duopoly game with two imperfect Information
In next version of Counout’s model, assume that Firm 2 doesn’t
know whether Firm 1 know its cost or not
Players: The two firms
States: {L0,L1,H0,H1}
Actions: Set of its possible outcomes
Signals:Firm 1 receives three signals, 0,L,H τ1 (L0)=
τ1 (H0)=0, τ1 (L1)=L and τ1 (H1)=H
Firm 2 receives two signals, τ1 (H) and τ2 (L)
Beliefs: Player1 assigns probability p to each state L0 and
probability 1-p to H0. Type L assigns probability 1 to state
L1 and type H assigns probability 1 to state H1
Type L assigns probability q to state L1 and 1-q to L0. Type
H assigns probability q to state H1 and 1-q to H0. 1-
Payoffs: Firm 1’s profit is π=q1 P(q1 + q2 )-c(q1 ) and Firm 1’s
profit is π=q2 P(q1 + q2 )-cL (q2 ) in L0 and L1 or Firm 1’s profit
is π=q2 P(q1 + q2 )-cH (q2 ) in H0 and H1.
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Providing a public good
Suppose that a public good is provided to a group of people
if atleast one person is willing to pay the cost of the goods.
Denote the number of individuals by n, the cost of the good
by c and each individual’s valuation by vi .
Assume that people differ in their valuations of the good and
each individual knows his own valuation, but knows that val-
uations are between va and vb , where a ≤ c ≤ b. Probabil-
ity of each individual valuation is atmost v is F (v ).
All individuals simultaneously submit envelops, the envelop
may contain c or nothing. If all individuals submit 0, good
is not provided. if atleast one submits c, good is provided.
Those who submitted c, will get payoff vi − c and others will
get payoff vi
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Providing a public good
The set of n individuals
States: { v1 , v2 , v3 , .....}
Actions:{0,c}
Signals: Set of possible valuations
Beliefs: Each player assigns probability
F(v1 ),F(v2 ),F(v3 ),.....
Payoffs: Player i’s payoff is
0
if no one contributes
= vi if i doesnot contribute but some other player does
vi − c if i contributes
(1)
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Auctions
In an "auction", a good is sold to a party who submits the
higher bid
Let vi be the value the player i attaches to the object. If she
obtains the object at price p, her payoff is vi -p.If m is the
number of tied winning bids, then payoff is vi -p/m.
Assume that people differ in their valuations of the good and
each individual knows his own valuation, but knows that val-
uations are between va and vb , where a ≤ c ≤ b. Probabil-
ity of each individual valuation is atmost v is F (v ).
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
Auctions
The set of n bidders
States: The set of all profiles (v1 , v2 , v3 , .....)
Actions: Set of possible bids
Signals: Set of possible valuations
Beliefs: Each player assigns probability
F(v1 ),F(v2 ),F(v3 ),.....
Payoffs: Player i’s payoff is
(
0 if his bid is not highest
= (2)
(vi − p)/m if his bid is highest
Dr. K. A. VIDYA Algorithmic Game theoryModule-4:Bayesian games
