Transcript Slide 1

1
problem set 11
from Binmore’s
Fun and Games.
p. 563 Exs. 35, (36)
p. 564. Ex. 39
Auctions
first & second price auctions with
independent private valuations
• Set of bidders 1,2….n
• The states of nature: Profiles of valuations
(v1,v2,…..vn), v  vi  v Each is informed
about his own valuation only.
• Given a profile (v1,v2,…..vn), the probability
of having a profile (w1,w2,…..wn), s.t. vi ≥ wi
is F(v1)F(v2)…...F(vn). Where F() is a
cummulative distribution function.
3
Auctions
first & second price auctions with
independent private valuations
• Actions: Set of possible (non negative) bids
• Payoffs: In a state (v1,v2,…..vn), if player i’s bid is
the highest and there are m such bids he gets
[vi-P(b)]/m . If there are higher bids he gets 0.
• P(b) is what the winner pays when the profile of
bids is b. It is the highest bid in a first price
auction, and the second highest bid in a second
price auction.
4
Auctions, Nash Equilibria
first & second price auctions with
independent private valuations
• In a second price (sealed bid) auction, bidding
the true value is a weakly dominating strategy.
• If the highest bid of the others is lower than my
valuation I can only win by bidding my valuation.
• If the highest bid of the others is higher than my
valuation I can possibly win by lowering my bid
to my valuation.
Hence, truth telling is a Nash equilibrium
(there may be others)
5
Auctions, Nash Equilibria
first & second price auctions with
independent private valuations
• In a first price (sealed bid) auction, bidding the
true value is not a dominating strategy: It is
better to bid lower when the highest bid of the
others is lower than my valuation.
A simple case:
First price (sealed bid) auction with 2 bidders,
where the valuations are uniformly distributed
between [0,1]
6
Auctions, Nash Equilibria
A simple case:
First price (sealed bid) auction with 2 bidders, where the
valuations are uniformly distributed between [0,1]
There is an equilibrium in which all types bid
half their valuation:
b(v) = ½v
Assume all types of player 2 bid as above.
If player 1 bids more than ½ he certainly wins (v-b).
If player 1 bids b < ½, he wins if player 2’s bid is
lower than b, i.e. if player 2’s valuation is lower than
2b. This happens with probability 2b.
7
In this case his expected gain is 2b(v-b).
Auctions, Nash Equilibria
A simple case:
First price (sealed bid) auction with 2 bidders, where the
valuations are uniformly distributed between [0,1]
for v > ½ the payoff function is:
The maximum is at b = ½v
2b(v-b)
v-b
½v
½
v
b
8
Auctions, Nash Equilibria
A simple case:
First price (sealed bid) auction with 2 bidders, where the
valuations are uniformly distributed between [0,1]
for v < ½ the payoff function is somewhat different but the
There is an equilibrium in which all types bid
maximum is as before at b = ½v
half their valuation:
2b(v-b)
½v
v
b(v) = ½v
i.e. each type of player 1
wants to use the same
strategy
½
b
v-b
9
Auctions, Nash Equilibria
A simple case:
First price (sealed bid) auction with 2 bidders, where the
valuations are uniformly distributed between [0,1]
There is an equilibrium in which all types bid
half their valuation:
2b(v-b)
½v
v
b(v) = ½v
i.e. each type of player 1
wants to use the same
strategy
½
b
v-b
10
Auctions, Nash Equilibria
A simple case:
First price (sealed bid) auction with 2 bidders, where the
valuations are uniformly distributed between [0,1]
There is an equilibrium in which all types bid
half their valuation:
b(v) = ½v
A player with valuation v, bids v/2 and will pay it
if his valuation is the highest, this happens with
probability v, i.e. he expects to pay v2/2
11
Auctions, Nash Equilibria
Now consider this simple case for a second price auction
second price (sealed bid) auction.
(2 bidders)
• Each player’s valuation is independently drawn
from the uniform distribution on [0,1]
• A player whose valuation is v, will bid v.
• He wins with probability v, and expects to pay
v2/2.
v
v2
0 sds  122
same expected payoff as in the first price auction
Auctions
First price (sealed bid) auction with n bidders.
Valuations are independently drawn from the cumulative
distribution F( ).
We look for a symmetric equilibrium
let βi  v  be the bid of player i whose valuation is v.
assume that βi  v   β  v  (a symmetric equilibrium)
and that β  v  is an increasing function of v .
v
b
The inverse function
dβ -1  b 
db
=
1
β  β -1  b 


β-1(b)
β(v)
v




β β -1  bb = b  β  β -1  b  β -1  b 13= 1
 assume all players use the bid funtion b = β  v  .
 a player whose valuation is v and who bids b expects
to earn
 v - b  Pr(All other bids  b )
 a player will bid  b if his valuation is  β
-1
 b .
 the probability that one player's valuation is  β -1  b 

is F β -1  b 

 the probability that all n - 1 players' valuation are
β
-1
b
 
is F β
-1
 b
n-1
.
14
assume all players use the bid funtion b = β  v  .
a player whose valuation is v and who bids b expects
to
earn
to earn
n-1
-1
v
b
Pr
(All
other
bids
b)
 v - b  F  β  b  


a player will bid  b if his valuation is  β
-1
 b .
the probability that one player's valuation is  β

-1
-1
b
-1
b

is F β  b 
the probability that all n - 1 players' valuation are
β
 
is F β
-1
 b 
n-1
.
15
a player whose valuation is v and who bids b expects
to earn
 v - b   F  β  b
-1
n-1
he should choose his bid b to maximize his expected
gain.
16
max  v - b   F  β  b   
-1
n-1
b
 v - b  n - 1  F  β  b   
n-1
-1
-  F  β b  +
β   β -1  b  
-1
n-2

F  β -1  b 

=0
now if the bidding function β   is an equilibrium
then b = β  v  should be the solution of the
above equation.
substitute b = β  v  in the equation above.
17
 
- F β
-1
 b 
n-1
-  F v 
+
n-1
 

β  β  b 
 v - b  n - 1 F β
-1
b
n-2

F  β -1  b 

-1
v - β  v    n - 1  F  v  

+
β  v   F  v 
β  v 
n-1
 β v   F v 

F  v 
+ β  v  n - 1   F  v  
= v  n - 1  F  v  
n-1
n-1
n-2
n-2
n-2
=0
=0
F  v  =
F  v 
v

n-2

x  n - 1   F  x   F   x  dx
 v
18

β v   F v 
n-1

v
v
x  n - 1  F  x 
n-2
F   x  dx
 F  x  n-1 


β v   F v 
n-1
n-1 


x  F  x    dx

v 

v
19
β v   F v 
n-1
n-1 


x  F  x    dx

v 

v
integration by parts :
β v   F v 
n-1
 v  F v 
v

v
β v   v 
n-1

v
F
x




v
 F  x 
 F  v 
F  x 
β v   v   
 F  v  
v

v
n-1
n-1
dx
Is this an
dx increasing
n-1
function of
???
v
n-1
dx
20
The Optimality of Auctions
An example:
• A seller sells an object whose value to him is
zero, he faces two buyers.
• The seller does not know the value of the object
to the buyers.
• Each of the buyers has the valuation 3 or 4 with
probability p, 1-p (respc.)
•The seller wishes to design a
?
mechanism that will yield the
highest possible expected payoff.
21
The Optimality of Auctions
Consider the ‘first best’ case:
If the seller can identify the buyer's type
2
2
he could earn : 3p + 4(1 - p ) = 4 - p
2
the probability that both buyers value the object at 3
the probability that at least one buyer values
the object at 4
22
The Optimality of Auctions
Posted Prices
(take it or leave it offer)
only 3,4
Posting the price 3, the seller will earn 3.
Posting the price 4, the seller will earn 4(1 - p2 ).
the probability that at least one buyer values
the object at 4
23
The Optimality of Auctions
Posted Prices
(take it or leave it offer)
Posting the price 3, the seller will earn 3.
2
Posting the price 4, the seller will earn 4(1 - p ).
2
If p < 1/2 then 3 < 4(1 - p )
2
2
If 0 < p < 1 then 3, 4(1 - p ) < 4 - p .
the first best
24
The Optimality of Auctions
Second price auction
Truth telling is an equilibrium : The expected payoff is
2
2


= 3 + 1 - p
4 1 - p + 3 1 - 1 - p 


2
if p < 1 then 3 < 3 +  1 - p 

2

2
2
2
if
< p < 1 then 4 1 - p < 3 +  1 - p 
5
Posted price 4.
the probability that both buyers value the object at 4.
25
The Optimality of Auctions
Modified Second price auction
The buyers are restricted to bid only 3,4.
The winner pays the average of the two bids.
Truth telling is an equilibrim.
It is optimal for L
(the player with a low valuation 3 ) to bid 3.
Player H (High) :
If he bids 4 he wins against L and gains :
1
1
1
4 -  3+4  = , i.e. he gains p.
2
2
2
26
The Optimality of Auctions
Modified Second price auction
Truth telling is an equilibrim.
It is optimal for L
(the player with a low valuation 3 ) to bid 3.
Player H (High) :
If he bids 4 he wins against L and gains :
1
1
1
4 -  3 + 4  = , i.e. he gains p.
2
2
2
1
If he bids 3 he wins against L with probability p
2
1
1
27
and earns 1 p = p.
2
2
The Optimality of Auctions
Modified Second price auction
The buyers are restricted to bid only 3,4.
The winner pays the average of the two bids.
Truth telling is an equilibrim.
The seller expects to earn :
1
2
4  1 - p  +  3 + 4  2p  1 - p  + 3p 2 = 4 - p
2
2
if 0 < p < 1 then 3 +  1 - p  < 4 - p
1
2
if
< p  1 then 4  1 - p  < 4 - p
4
Posting price 4
Second price auction28