The Learning Point‎ > ‎Mathematics‎ > ‎

Bayesian Games - Games with Incomplete Information : A tutorial with examples, problems and solutions

                










   Our Game Theory Tutorials- at a glance


Game Theory


 An Introduction to Game Theory

Extensive Games

Bayesian Games : Games with Incomplete Information

Repeated Games



Recommended books for Game Theory enthusiasts

 

Strategy An Introduction To Game Theory

Joel Watson (Paperback)


Buy New INR 411.00

Privacy

 

Game Theory: An Introduction

E.N. Barron (Paperback - Sep …


Buy New INR 366.00

 

Game Theory - An Introduction

Steven Tadelis (Hardcover - Feb …


Buy New INR 2,725.00

 

Game Theory: A Nontechnical Introduction

Morton D. Davis (Paperback - Nov …


Buy New INR 643.00

 

Political Game Theory: An Introduction (Analytical Method…

Cambridge University Press


Buy New

 
Strategy
List Price: Rs.495
Our Price: Rs.356
Buy from FlipKart
 
Game Theory
List Price: Rs.489
Our Price: Rs.367
Buy from FlipKart
 
Game Theory
Our Price: Rs.6372
Buy from FlipKart
 
Game Theory
Our Price: Rs.1595
Buy from FlipKart
 
Game Theory for Political Sci...
Our Price: Rs.4244
Buy from FlipKart
 

Strategy

Joel Watson

Best Price $25.00 
or Buy New $115.00


 

Game Theory

E. N. Barron

Best Price $19.87 
or Buy New $121.60


 

Game Theory

Steven Tadelis

Best Price $33.80 
or Buy New $33.80


 

Game Theory

Morton D. Davis

Best Price $4.39 
or Buy New $8.29

Privacy Information

 

Political Game Theory

Nolan McCarty, Ada...

Best Price $53.58 
or Buy New $59.59






-----------------------------------------------------xxxxxx-------------------------------------------------------


A Tutorial on Bayesian Games: Games with Incomplete Information

Bayesian Games

In case you're interested, here are the Game Theory tutorials we have :

Games with Incomplete Information

In our daily life, there exist the settings where a player may not have complete information regarding nature, style etc. about his adversary.Some of these settings are given below:
  • Bidding in auctions
  • Political campaign of a candidate
  • Prices charged by a firm on a particular product
  • Regulating an industry

Example: Consider the following conflict game. In this game player 1 can be in two forms :Strong and weak; and payoffs differ in each of the case
StrongFightNot
Fight1,-22,-1
Not-1,20,0



WeakFightNot
Fight-2,12,-1
Not-1,20,0

Suppose both the players fight then the outcome depends whether the player 1 is “strong” or “weak”. Consequently Nash Equilibrium will also differ.
Suppose both the players know whether player 1 is going to be strong or weak.If player 1 is strong then he has a dominant strategy of fighting. Thus player will not fight and Nash Equilibrium is {Fight, Not}. If the player 1 is weak then nash equilibrium is {Not, Fight}
Suppose player does not know what player 1 going to be. So he assigns a probability “p” player is strong and probability “1-p” player 1 is weak.
Player 2 expected payoffs when he fights: p(-2)+(1-p)(1)
             expected payoff when not fighting : -1
Therefore, player 2 should fight if  p(-2)+(1-p)(1) > -1, i.e. if p<2/3



Bayesian Games

They can be formally defined as follows:

  • Players N={1,...,n}
  • Action sets: Ai             A = A1 x A2 x … An
  • Type sets: ϴi            ϴ = ϴ1 x ϴ2 x … ϴn
  • Payoff/Utility functions:   ui: A  x  ϴ→ R
  • Beliefs: pi-i| θi) conditional probability that i gives to others’ types being θ-i given θi
  • Strategies: si:  ϴi→ Ai (pure or si:  ϴi→ Δ(Ai) mixed)
  • sii) is the action type θi of player i takes
  • Expected Utility: For each i and θigiven the strategies s, the expected payoff is
           Σθ-ipi-i| θi) ui(sii), s-i-i); θi-i)

Bayesian Nash Equilibrium

  • Strategies, s= (s1, …, sn), such that for each i and θi: sii) maximizes player i’s expected utility, given the strategies of other players
  • For each i and θigiven the strategies s:
          Σθ-ipi (θ-i| θi) ui(si(θi), s-i(θ-i); θi,θ-i) ≥ Σθ-ipi (θ-i| θi) ui(ai, s-i(θ-i); θi,θ-i) for all a in Ai
Given finite number of pure strategies, finite set of types: Equilibrium exists (corollary to Nash’s Theorem)


Applications


Auctions


Example:
  • Suppose 2 bidders each bidding for a painting.
  • Each player has a value θi for the painting in Θi= {2,3} equally likely.
  • First price auction: highest bidder wins, pays bid.
  • One can only bid whole integers Ai= {0,1,2,3}
We can try various combinations. If bid is equal to value, then payoff is zero no matter whether win or not. If
s(3)<3, s(2)<2 e.g. s(3)=2, s(2)=1
If θi= 3, and other uses this strategy, then expected utility from
  • bidding 3 = 0
  • bidding 2 = (3-2) ( 1/2 + 1/4) = 3/4
  • bidding 1 = (3-1) (1/4) = 1/2
  • bidding 0 = 0
If θi= 2, and other uses this strategy, then expected utility from
  • bidding 3 = (2-3) ( 1) = -1
  • bidding 2 = 0
  • bidding 1 = (2-1) (1/4) = 1/4
  • bidding 0 = 0
So, s(3)=2, s(2)=1 is a best response to the same strategy by the other player. It is a (symmetric) pure strategy Bayesian equilibrium

Continuous First Price Auction

  • First price auction: highest bidder wins, pays bid
  • n bidders each bidding for a painting
  • Each player has a value θi in Θi= [0,100] from a uniform distribution for obtaining the painting, independently distributed
  • Ai = [0,100] possible bids
  • Private values: ui(ai, a-i ; θi,θ-i) does not depend on θ-i
  • ui(ai, a-i ; θi) = θi-ai if ai> aj for all j≠ i
                                = 0 if ai< aj some j≠ i
                                = (θi–ai)/y if tied with y-1 other bidders for highest bid
Equilibrium

  • Let bid be  si(θi) = f(θi) ;  same function f for all bidders.
  • f(θi) maximizes the  expected utility for each θi given that others use the same strategy
  • Expected utility for bid b: (θi–b) Prob(f(θj)<b all j≠i)
  • Let f(θj) = cθi  for some c.
  • Expected utility for bid b: (θi–b) Prob(cθj<b all j≠i)
  • Prob( cθj<b all j≠i) = Prob( max j≠iθj<b/c)
  • Prob(maxj≠iθj< b/c ) = [b/(c100)]n-1 (Probability that for one j θj< b/c is b/(c100))
  • Expected utility for bid b: (θi–b) [ b /(c100)]n-1
           Maximize with respect to b, taking derivative
           0= (n-1) (θi–b) [ b /(c100)]n-2 -[ b /(c100)]n-1
  • Solving for b we get; b= θi(n-1)/n
Thus equilibrium is si( θi) = f( θi) = θi(n-1)/n

Second Price Auction

  • n bidders, a single good
  • Sealed bids: Each bidder offers a price
  • Second price rule: Highest bidder wins, pays second highest bid
  • Each agent i has a type θi, say in [0,100];
  • Private values: Agent's Payoff Depends on the auction outcome (a function of the bids) and his type θi but not the other types θ-i
  • Actions: Each agent bids aiin [0,100]
  • Define a(2) = second highest bid of (a1, ... , an)
  • Payoffs: ui(ai, a-i; θi)= θi–a(2)if ai> a(2)
                                           = 0 if ai< a(2)
                                           = (θi–a(2))/y if tied with y-1 other bidders for highest bid
  • Agents have a dominant strategy: ui(ai, a-i; θi) >= ui(a’i, a-i; θi) for all a’i, a-i
  • The dominant strategy: Bid your true value, or ai= θi
  • Such auctions are called truthful.

Reasons for Second Price Auction being truthful

  • ui(ai, a-i ; θi) = θi–a(2)if ai> a(2)
                                = 0 if ai< a(2)
                                = (θi–a(2))/yif tied
  • θi–a(2) is positive if and only if θi> a(2).
  • So, we want to have ai> a(2) if and only if θi> a(2)
  • ai= θiguarantees win if and only if we get positive payoff from winning





Revelation Principle

  • a direct auction means bidders simply declare a value
  • A direct auction is truthful if it’s an equilibrium for all to declare truthfully

Any auction can be converted to an equivalent truthful auction.

Example:  Consider a first-price auction with n bidders with IPVs drawn i.i.d(independently and identically distributed). from [0,100]. We know it is a Bayesian Nash Equilibrium  when an agent with value x bids x(n-1)/n.Define a modified auction in which, when you bid x, the auctioneers considers it as x(n-1)/n and runs a first-price auction.It is now an equilibrium to bid truthfully.

The Revenue Equivalence Theorem

In IPV setting with IID values, all single-item auctions in which

  • Item goes to bidder with highest (true) value
  • Bidder with value 0 pays 0 have the same expected revenue


Example: Suppose you want to sell an object through auction. Obviously you will try to maximise your earnings. So you may ask should you hold a first price auction or second price auction or some other auction.
  • n bidders each bidding for a painting
  • Each player has a value θidrawn from the uniform distribution over [0,100] for the painting
  • Equilibrium in first price auction: bid θi(n-1)/n
  • Equilibrium in second price auction: bid θi
  • Winning payment First price: maxi θi(n-1)/n = E[maxiθi] = 100 n/(n+1)
                                                                                  E[revenue] = 100 (n-1)/(n+1)
  • Winning payment Second price: second highest θi
                                                              E[second highest θi] = 100 (n-1)/(n+1)
                                                              E[revenue] = 100 (n-1)/(n+1)


Private values:


  • Agents know their own payoff functions
  • Uncertainty is about other players and their actions
  • Both ``Payoff Uncertainty’’ and ``Strategic Uncertainty’’




Common Values: Example

  • Two companies are bidding for an item worth either(with probabilities): 10 (p=1/4), 20 (p=1/2) or 30 (p=1/4)
Information:
  • If item worth 10: both bidders see ``Low’’
  • If item worth 20: one bidder sees ``Low’’, other sees ``High’’ (equal chance on either)
  • If item worth 30: both bidders see ``High’’.
The Bayesian Game
  • Ai = [0,30] possible bids
  • Θi={L,H}
  • ui(ai, a-i ; ti,t-i)            = 0 if lose; otherwise:
                                             = 30 –ajθi=H=θj
            Common Values      = 20 –ajθi≠θj
                                              = 10 –ajθi=L=θj
Consider a second-price auction .Try to mimic the equilibrium from the private values case: bid your expected value
See ``Low’’ two possibilities:
  • Item worth 10 (probability ¼)
  • Item worth 20, and then i happened to be the one seeing the Low signal (probability ½ times ½ = probability ¼)
  • So if see Low, expected value is 15. If other player sees Low, then actually worth 10.Other also bids 15, expected payoff = (10-15)/2= -2.5. If other sees High, then lose the auction.Expected payoff when Low is -2.5/2= -1.25. Better off not bidding.
  • Similarly, if see High then expected value is 25
Equilibrium in this case
  • If see Low: bid 10. If other sees ``Low’’ then it is worth 10, and are bidding/paying 10, no benefit from deviating
  • If other sees ``High’’ then it is worth 20, and other is bidding 30. In order to win would have to bid at least 30, and pay 30, not worth it
  • If see High: bid 30 .If other sees ``Low,’’ then it is worth 20, and other is bidding 10, so you are winning paying 10, wonderful, no benefit from deviating
  • If other sees ``High,’’ then it is worth 30, and are tied at bidding 30, no gain from increasing or decreasing

  • Strategy should take into account what you learn from winning
  • Equilibrium can differ substantially from bidding expected value
  • Results for IPV case no longer valid
  • English auction no longer equivalent to second-price auction
  • Revenue Equivalence no longer holds


Exercises: Problems with solutions


1.

StrongFightNot
Fight2,-22,-1
Not-1,20,0



WeakFightNot
Fight-2,22,-1
Not-1,20,0


Let p* be the threshold such that if player 1 fights when both weak and strong then:
–if p>p*, player 2 prefers `Not’
–if p<p*, player 2 prefers `Fight’
What is p*?
Solution:Conditional on 1 always choosing Fight, the payoff of 2 when choosing Not is -1 and the payoff of 2 when choosing Fight is (-2)p + 2(1-p).Comparing these two payoffs, 2 is just indifferent when -1 = (-2)p + 2(1-p), thus p* = 3/4, above which 2 prefers Not and below which 2 prefers to Fight.


2. Player 1 is a company choosing whether to enter a market or stay out; If 1 stays out, the payoff to both players is (0, 3).
Player 2 is already in the market and chooses (simultaneously) whether to fight player 1 if there is entry The payoffs to player 2 depend whether 2 is a normal player (with prob 1-p) or an aggressive player (with prob p).
AggressiveFightNot
Enter-1,22,-1
Out0,30,3


NormalFightNot
Enter-1,01,2
Out0,30,3

Player 2 knows if he/she is normal or aggressive, and player 1 doesn’t know.
If player 2 uses a strategy of fight when aggressive and not when normal, what is true about player 1’s expected utility?
a)It is -1 when 1 chooses to enter;
b)It is 1-2p when 1 chooses to enter;
c)It is 1-2p when 1 chooses to be out;
d)It is -1 when 1 chooses to be out
Solution:
  • If 1 chooses to stay out, 1 always earns 0 and so (c) and (d) are false.
  • If 1 chooses to enter, with prob=p player 2 is aggressive and flights and then 1 earns -1, and with prob=(1-p) player 2 is normal and doesn’t fight and then 1 earns 1.Thus, the expected payoff is (-1)p + 1(1-p) = 1-2p
Hence b is true.





3. Consider the game in previous question:
Player 2 knows if he/she is normal or aggressive, and player 1 doesn’t know.
Which is true:
a)When p>1/2, it is a Bayesian equilibrium for 1 to stay out, 2 to fight when aggressive and not when normal;
b)When p<1/2, it is a Bayesian equilibrium for 1 to stay out, 2 to fight when aggressive and not when normal;
c)For all p, it is a Bayesian equilibrium for 1 to stay out, 2 to fight when aggressive and not when normal;
d)When p>1/2, it is a Bayesian equilibrium for 1 to enter, 2 to fight when aggressive and not when normal
Solution:When 1 enters, it is optimal for the aggressive type to fight and for the normal type not to fight.
Conditional on 2’s strategy,we know it is optimal for 1 to enter when p<1/2, and it is optimal for 1 to stay out when p>1/2.
Hence a is true.



4. 2 bidders each bidding for a painting
  • Each bidder has a value θi in Θi= {2,3} equally likely and independent of the other bidder’s value
  • They bid in a first price auction: the highest bidder wins, and pays his or her bid
  • They have to bid whole integers in Ai= {0,1,2,3}
  • If there is a tie, the winner is determined by the flip of a fair coin.
Suppose bidder 2 always bids 1 (whatever his or her value). Which statement is wrong regarding player 1 when her value is 3:
a)Her expected utility from bidding 3 is (3-3)(1)=0;
b)Her expected utility from bidding 2 is (3-2)(1)=1;
c)Her expected utility from bidding 1 is (3-1)(1/2)=1;
d)Her expected utility from bidding 0 is (3-0)(1/2)=3/2;
Solution:  check that (a) (b) and (c) are true by looking at value minus bid times probability of winning. Given the other player bids 1 regardless of the type, bidding 0 has a 0 probability of winning thus the payoff is 0.
Hence d is false.



5.
p
StrongFightNot
Fight1,-32,-1
Not-1,20,0

1-p
WeakFightNot
Fight-3,12,-1
Not-1,20,0

Let p* be the threshold such that if player 1 fights when both weak and strong then:
  • if p>p*, player 2 prefers `Not’
  • if p<p*, player 2 prefers `Fight’
Find p*
Solution: Expected payoff when player 2 fights: -3p+(1-p)
                Expected payoff when player 2 “not fight” : -1
He is indifferent for p=1/2
Hence p*=1/2



6.
p
AggressiveFightNot
Enter-1,21,-2
Out0,30,3

1-p
NormalFightNot
Enter-1,01,2
Out0,30,3

  • Player 1 is a company choosing whether to enter a market or stay out;

If 1 stays out, the payoff to both players is (0, 3).


  • Player 2 is already in the market and chooses (simultaneously) whether to fight player 1 if there is entry

The payoffs to player 2 depend on whether 2 is a normal player (with prob 1-p) or an aggressive player (with prob p).

Player 2 knows if he/she is normal or aggressive, and player 1 doesn’t know.
If player 2 uses a strategy of fight when aggressive and not when normal, what is the p* such that when p<p* player 1 prefers to enter, and when p>p* player 1 prefers to stay out?
Solution:  Player 1 expected payoff when it enters: -p+1-p
                 Player 1 expected payoff when it stays out: 0
Solving for p we get p=1/2
hence p*=1/2



7. Which of the following is true . (Consider the previous question)
  1. When p=1/2, it is a Bayesian equilibrium for 1 to stay out, 2 to fight when aggressive and not when normal
  2. When p>1/2, it is a Bayesian equilibrium for 1 to stay out, 2 to fight when aggressive and not when normal
  3. When p=1/2, it is a Bayesian equilibrium for 1 to enter, 2 to fight when aggressive and not when normal
  4. When p<1/2, it is a Bayesian equilibrium for 1 to enter, 2 to fight when aggressive and not when normal
Solution:
All are true.
  • When 1 enters, it is optimal for the aggressive type to fight and for the normal type not to fight; and those actions don’t matter when 1 stays out.
  • Conditional on 2’s strategy, we know it is optimal for 1 to enter when p<1/2, it is optimal for 1 to stay out when p>1/2 and it is indifferent for 1 to enter or to stay out when p=1/2.



8.      
  • 2 bidders each bidding for a painting

  • Each bidder has a value θi in Θi = {2,3} equally likely and independent of the other bidder’s value
  • They bid in a first price auction: the highest bidder wins, and pays his or her bid
  • They have to bid whole integers in Ai = {0,1,2,3}
  • If there is a tie, the winner is determined by the flip of a fair coin.
Suppose that bidder 2 bids according to the strategy: s2(3)=1 & s2(2)=1. Which of the following is wrong?
  1. If θ1 = 2, bidder 1’s expected utility from bidding 1 is (2-1)(1/2)=1/2;
  2. If θ1 = 2, bidder 1’s expected utility from bidding 2 is (2-2)(1)=0;
  3. If θ1 = 2, bidder 1’s expected utility from bidding 0 is (2-0)(0)=0;
  4. Each player always bidding 1 does not form a symmetric Bayesian equilibrium.
Solution: Each player always bidding 1 does not form a symmetric Bayesian equilibrium" is wrong.
We can check the other options by considering the value minus bid times probability of winning.
Given this and the previous question on this auction (implying that 1 is also a best reply when a player’s value is 3) then when the other player always bids 1, it is optimal to use the same strategy. Thus always bidding 1 is a symmetric pure strategy Bayesian equilibrium of this game.



9. Modify the BoS to have incomplete information:
  • There are two possible types of player 2 (column):

"Meet:" player 2 wishes to be at the same movie as player 1, just as in the usual game. (This type has probability p)

"Avoid" 2 wishes to avoid player 1 and go to the other movie. (This type has probability 1-p)


  • 2 knows her type, and 1 does not.
  • They simultaneously choose P or L.
p:
MeetLP
L2,10,0
P0,01,2


1-p:
AvoidLP
L2,00,2
P0,11,0

When p=1/2, what is the pure strategy Bayesian equilibrium: (1’s strategy; 2’s type - 2’s strategy)
Solution:
  • (L; Meet – L, Avoid - P): If 1 chooses L, indeed the Meet type prefers L and Avoid type prefers P. Thus with prob=1/2, 2 is a Meet type who chooses L and with prob=1/2, 2 is a Avoid types who chooses P. Thus, 1 prefers L with a payoff of 1/2*2, while P gives a lower payoff of 1/2*1.
  • (P; Meet – P, Avoid - L) is not a Bayesian equilibrium because when L and P are chosen by 2 (depending on the type) with 1/2 probability, 1 prefers L instead of P.
  • (L; Meet – P, Avoid - P). is not a Bayesian equilibrium because when 1 chooses L, the Meet type prefers L instead of P.
Hence (L; Meet – L, Avoid - P) is the answer


10. An engineer has a talent t in {1,2} with equal probability (prob=1/2), and the value of t is private information to the engineer. The engineer’s pure strategies are applying for a job or being an entrepreneur and doing a startup. The company’s pure strategies are either hiring or not hiring the engineer. If the engineer applies for the job and the company does not hire, then the engineer becomes an entrepreneur and does a startup. The utility of the engineer is t (talent) from being an entrepreneur, and w (wage) from being hired. The utility of the company is (t-w) from hiring the engineer and 0 otherwise
t=2HireNot
Startup2,02,0
Workw,2-w2,0

t=1HireNot
Startup1,01,0
Workw,1-w1,0

Suppose w=2, list all pure strategy Bayesian equilibria. (the engineer is the row player and the company is the column player.)
Solution: (t=2 Startup, t=1 Work, Not) and (t=2 Work, t=1 Work, Not) are pure strategy Bayesian equilibria. Other alternatives are not true.
  • Because w=2, type t=1 prefers to work if the company hires and type t=2 is indifferent between work and startup.
  • Given that type t=1 prefers to work, the company prefers not to hire since it loses money from type t=1 and only breaks even from t=2.
Thus (t=2 Startup, t=1 Work, Not) and (t=2 Work, t=1 Work, Not) are true.


11. Discrete First-Price Auction
  • 2 bidders each bidding for a painting.
  • Each player has a value θi in Θi = {3,5} with probabilities .4 and .6, respectiThuely
  • Values are independently chosen by nature.
  • They compete in a first-price sealed bid auction, so submit bids simultaneously with the highest bidder winning and paying his or her bid (and ties broken by a fair coin flip).
  • They bid in whole numbers Ai = {0,1,2,3,4,5}
Which of these is a symmetric pure strategy Bayesian equilibrium:
  1. s(3)=1, s(5)=2
  2. s(3)=2, s(5)=2
  3. s(3)=2, s(5)=3
  4. s(3)=1, s(5)=1
Solution: {s(3)=1, s(5)=2} (ep=expected payoff): when θ1=3
  • If 1 bids 1, 1 wins with prob=0.4/2=0.2 thus ep=(3-1)*0.2=0.4.
  • If 1 bids 2, 1 wins with prob=0.4+0.6/2=0.7 thus ep=(3-2)*0.7=0.7 > 0.4. Thus 1 wants to deviates
{s(3)=2, s(5)=2}when θ1=5
  • If 1 bids 2, 1 wins with prob=0.5 thus ep=(5-2)*0.5=1.5.
  • If 1 bids 3, 1 wins with prob=1 thus ep=(5-3)*1 = 2 > 1.5. Thus 1 wants to deviates.
  • The same deviation happens in {s(3)=1, s(5)=1} such that type 5 wants to bid 2.
Thus 3 is true.



12.
2 bidders are each bidding for a painting
Each bidder has a value θi in Θi= [0,100] drawn from a uniform distribution for obtaining the painting, and their values are independently distributed. Consider a first price auction: the highest bidder wins, and pays his or her bid. If there is a tie, the winner is determined by a flip of a fair coin.Suppose bidder 2 bids half of her value: s22)=θ2/2, which if any of the following statements is wrong?
  1. By bidding a bid b1≤50, bidder 1’s probability of winning is b1/50;
  2. When winning with a bid of b1, bidder 1’s utility is (θ1-b1);
  3. To find a best response, bidder 1 chooses a bid as a function of his value θ1,s1(θ1), that maximizes (θ1-s1) s1/50.
  4. A best reply strategy of player 1 is also to bid half of his value: s1( θ1) = θ1/2.
  5. None is wrong
Solution: None of the statement is wrong.



13.
Two identical paintings are for sale
n bidders each have a private value θiin Θi= [0,100] drawn from a uniform distribution for obtaining one painting, and values are independent .Bidders bid in a Third price auction: the highest and second highest bidders win, and pay the third highest bid If there is a tie at some bid, then those bidders are randomly ordered (with equal probability).
Which is true:
  1. It is a dominant strategy for bidders to bid their values;
  2. There is a Bayesian equilibrium in which all bidders bid higher than the their values;
  3. There is a Bayesian equilibrium in which all bidders bid lower than the their values.
  4. None of the above
Solution: Follow the same logic as in the second-price auction  a bidder’s bid determines whether they win or not, but not the price they pay conditional on winning
A bidder wishes to win whenever the value is higher than the second highest bid among the other bidders and not otherwise .This is exactly guaranteed by bidding one’s value.
hence 1. is true



14. 4 bidders are each bidding for a painting
  • Each bidder has a value θi in Θi = [0,100] drawn from a uniform distribution for obtaining the painting, and their values are independently distributed
  • Consider a first price auction: the highest bidder wins, and pays his or her bid.
  • If there is a tie, each tied bidder gets an equal chance of being the winner.
Suppose bidders 2&3&4 bid according to si(θi)=3θi/4, which of the following statements is wrong?
  1. When winning with a bid b1, bidder 1’s utility is 1−b1);
  2. By bidding s1≤75, bidder 1’s probability of winning is s1/75;
  3. To find a best response, bidder 1 chooses a bid as a function of his value θ1, s11), that maximizes 1−s1)(s1/75)3.
  4. The best reply for player 1 is s11)=3θ1/4.
Solution: By bidding s1≤75, bidder 1’s probability of winning is s1/75" is wrong.
When bidder 1 bids s1≤75, another bidder i has a lower bid than 1 when 3θi/4<s1 or when θi<4s1/3. Given the uniform distribution, this happens with probability s1/75 .Thus, by bidding s1≤75, bidder 1’s probability of winning is (s1/75)3 because s1 is the winning bid only if all three other bidders submit lower bids.




15. k identical paintings are for sale
  • n>k bidders each have a private value θi in Θi = [0,100] drawn from a uniform distribution for obtaining one painting, and values are independent
  • Bidders bid in a k+1-th price auction: the k highest bidders win, and pay the k+1-th highest bid
  • If there is a tie at some bid, then those bidders are randomly ordered (with equal probability)
Which is true:
  1. There is a Bayesian equilibrium in which all bidders bid higher than the their values;
  2. It is a dominant strategy for bidders to bid their values;
  3. There is a Bayesian equilibrium in which all bidders bid lower than the their values.
  4. None of the other options
Solution: solving on the lines of previous question we get
It is a dominant strategy for bidders to bid their values.



16.
2 bidders bid for a painting.
Each player has a private value θifor a painting in Θi= [0,30] drawn from a uniform distribution, independently. Consider two auctions (with ties broken by the flip of a fair coin):
  • First price auction (FPA): highest bidder wins, pays his or her bid.
  • Second price auction (SPA): highest bidder wins, pays the the second highest bid.
When comparing the expected price paid, which statement is wrong:
a)In the FPA, a symmetric equilibrium bidding strategy is b(θi)=θi/2;
b)The expected price paid in a symmetric equilibrium in the FPA is E(θi/2)=(15)/2=7.5;
c)In the SPA, a symmetric equilibrium bidding strategy is b(θi)=θi;
d)The expected price paid in a symmetric equilibrium in the SPA is E(θi|θj>θi)=10;
Solution: (b) is wrong.
Revenue from FPA is E(θi/2| θi>θj)=(20)/2=10. Note that the revenue is not the direct expectation of a player’s bid, instead it should be the expectation of the higher type’s bid among these two bidders.
So we do have revenue equivalence.



17.Two bidders are bidding in a second-price auction;
  • If they tie, the winner is picked by the flip of a fair coin.
  • Each bidder observes a signal (θ1and θ2), taking value either 0 or 2 with equal probability; independently
  • The common value is the sum of both signals, such that v = θ1+ θ2
  • The expected value of the other signal is 1. In a second-price auction, a naïvebid is bidding the expected value: b(θi) = E(v|θi) = θi+1.
What is a bidder’s expected profit when observing θi=0 if both use the naïvebidding strategy?
Solution:
When bidding 1, the player only wins if the other player also observes 0 and also bids 1, which happens with probability 1/2 .
  • Then with a tie, the player is the winner with prob1/2, and the winner pays a price 1(the second highest bid).
  • When both observe 0, the common value is 0.
  • Thus the expected payoff is 1/2*1/2*(0-1) = -1/4



18.Two bidders are bidding in a second-price auction;
  • If they tie, the winner is picked by the flip of a fair coin.
  • Each bidder observes a signal (θ1 and θ2), taking value either 0 or 2 with equal probability; independently
  • The common value is the sum of both signals, such that v=θ12
  • The expected value of the other signal is 1. In a second-price auction, a naïve bid is bidding the expected value: b(θi)=E⁡(v|θi)=θi+1.
Which is a bidding strategy in a symmetric pure strategy Bayesian equilibrium:
  1. b(0)=0, b(2)=2;
  2. b(0)=1, b(2)=4;
  3. b(0)=1, b(2)=2;
  4. b(0)=0, b(2)=4.
Solution: b(0)=0, b(2)=4;
  • Suppose bidder 2 uses b(0)=0, b(2)=4, let us check if 1 wants to use the same strategy:
  • When 1 observes 0 (cv=common value):

If 1 bids 0, 1 wins with (prob=0.25, price=0, cv=0), and the expected payoff is 0.

If 1 bids 1 (or 2, 3), 1 wins with (prob=0.5, price=0, cv=0), and the expected payoff is 0.

If 1 bids 4, 1 wins with (prob=0.5, price=0, cv=0) as well as with (prob=0.25, price=4, cv=2), such that expected payoff is -0.5.

If 1 bids 5 (or higher), 1 wins with (prob=0.5, price=0, cv=0) as well as with (prob=0.5, price=4, cv=2), expected payoff is -1;


  • When 1 observes 2:

If 1 bids 0, 1 wins with (prob=0.25, price=0, cv=2), so the expected payoff is 0.5;

If 1 bids 1 (or 2, 3), 1 wins with (prob=0.5, price=0, cv=2) so the expected payoff is 1;

If 1 bids 4, 1 wins with (prob=0.5, price=0, cv=2) as well as with (prob=0.25, price=4, cv=4) so the expected payoff is 1;

If 1 bids 5 (or higher), 1 wins with (prob=0.5, price=0, cv=2) as well as with (prob=0.5, price=4, cv=4) so the expected payoff is 1;

Thus, it is optimal for bidder 1 to use b(0)=0 and b(2)=4


19.Common-Value Auction
  • Two bidders compete in a in a second-price auction.
  • Each observes one signal (s1 and s2), taking value from {1, 3} with equal probability;
  • The common value is the max of the signals, so that v=max(s1,s2)
  • So, the expected common value is 2 when observing si =1 , and 3 when observing si =3.
  • In a second-price auction, a naïve bid is bidding the expected common value: b(1) =2 and b(3)=3.
What is the player’s expected profit when observing si =1 and bidding b(1)=2 if the other player uses the naïve bidding strategy?
Solution: When bidding 2, the player could win only if the other player observes 1 (with prob 1/2) and bids 2. Then with a tie, the player is the winner with prob 1/2, and the winner pays a price 2 (the second highest bid).when both observe 1, the common value is 1.
Thus the expected payoff is 1/2*1/2*(1-2) = -1/4




20. In the previous question What is the bidding strategy in a symmetric pure strategy Bayesian equilibrium?
Solution: b(1)=1, b(3)=3.
Suppose bidder 2 uses b(1)=1, b(3)=3, let check if 1 wants to use the same strategy:
When 1 observes 1 :
    • If 1 bids 1, 1 wins with (prob=0.25, price=1, v=1), so that the expected payoff is 0.
    • If 1 bids 2, 1 wins with (prob=0.5, price=1, v=1), so that the expected payoff is 0.
    • If 1 bids 3, 1 wins with (prob=0.5, price=1, v=1) as well as with (prob=0.25, price=3, v=3), so that expected payoff is 0.
    • If 1 bids 4 (or higher), 1 wins with (prob=0.5, price=1, v=1) as well as with (prob=0.5, price=3, v=3), the expected payoff is 0;



21. Each of two individuals receives a ticket on which there is an integer from 1 to m indicating the size of a prize she may receive..The individual’s tickets are assigned randomly and independently; the probability of an individual’s receiving each possible number is positive.Each individual is given the option of exchanging her prize to other individual’s prize;the individuals are given this option simultaneously . If both individuals wish to exchange, then the prizes are exchanged; otherwise not. Each individual’s objective is to maximise her expected monetary payoff.Model this situation as a bayesian game.
Solution: The following Bayesian game models the situation.
Players The two individuals.
States The set of all pairs (s1, s2), where si is the number on player i’s ticket (an integer from 1 to m).
Actions The set of actions of each player is {Exchange,Don’t exchange}.
Signals The signal function of each player i is defined by τi(s1, s2) = si (each player observes her own ticket, but not that of the other player)
Beliefs Type si of player i assigns the probability Prj(sj) to the state (s1, s2), where j is the other player and Prj(sj) is the probability with which player j receives a ticket with the prize sj on it.
Payoffs Player i’s Bernoulli payoff function is given by ui((X,Y),ω) = ωj if X = Y = Exchange and ui((X,Y),ω) = ωi otherwise.


22. Show that in previous question in any Nash Equilibrium the highest prize that either individual is willing to exchange is the smallest possible prize.
Solution: Let Mi be the highest type of player i that chooses Exchange. If Mi > 1 then type 1 of player j optimally chooses Exchange: by exchanging her ticket, she cannot obtain a smaller prize, and may receive a bigger one. Thus if Mi ≥ Mj and Mi > 1, type Mi of player i optimally chooses Don’t exchange, because the expected value of the prizes of the types of player j that choose Exchange is less than Mi. Thus in any possible Nash equilibrium Mi = Mj = 1: the only prizes that may be exchanged are the smallest.




23.Show that for each type vi  for each player i in a second-price sealed auction with imperfect information about valuations the bid vi weakly dominates all other bids.
Solution: Fix player i, and choose a bid for every type of every other player. Player i, who does not know the other players’ types, is uncertain of the highest bid of the other players. Denote by b this highest bid. Consider a bid bi of type vi of player i for which bi < vi. The dependence of the payoff of type vi of player i on b is shown in following table.
                                                    Highest of other players’ bids
b<bibi=bbi<b<vi b>=vi
bi<vivi-b(vi-b)/m00
vivi-bvi-bvi-b0

Player i’s expected payoffs to the bids bi and vi are weighted averages of the payoffs in the columns; each value of b gets the same weight when calculating the expected payoff to bi as it does when calculating the expected payoff to vi. The payoffs in the two rows are the same except when bib < vi, in which case vi yields a payoff higher than does bi. Thus the expected payoff to vi is at least as high as the expected payoff to bi, and is greater than the expected payoff to bi unless the other players’ bids lead this range of values of b to get probability 0. Now consider a bid bi of type vi of player i for which bi > vi. The dependence of the payoff of type vi of player i on b is shown below
                                                  Highest of other players’ bids
b=<vibi>b>vi bi=bb>=bi
bi<vivi-b000
vivi-bvi-b(vi-b)/m0


As before, player i’s expected payoffs to the bids bi and vi are weighted averages of the payoffs in the columns; each value of b gets the same weight when calculating the expected payoff to vi as it does when calculating the expected payoff to bi. The payoffs in the two rows are the same except when vi < b ≤ bi, in which case vi yields a payoff higher than does bi. (Note that vib < 0 for b in this range.) Thus the expected payoff to vi is at least as high as the expected payoff to bi , and is greater than the expected payoff to bi unless the other players’ bids lead this range of values of b to get probability 0.
We conclude that for type vi of player i, every bid bi =∦vi is weakly dominated
by the bid vi.