Transcript Optimal Mechanisms (again)

Auction Seminar
Optimal Mechanism
Presentation by: Alon Resler
Supervised by: Amos Fiat
Review

1.
2.
3.
Myerson Auction for distributions with strictly
increasing virtual valuation:
Solicit a bid vector from the agents.
Allocate the item to the bidder with the largest virtual
value i (bi ) , if positive, and otherwise, do not allocate.
Charge the winning bidder i, if any, the minimum value
she could bid and still win, i.e.
i 1  max(0,{ j (b j )} j i 
2
Review

we defined the virtual value of agent i to be:
1  Fi (vi )
i (vi ) : vi 
f i (vi )

We saw that when the bidders values drawn from
independent distributions with increasing virtual
valuations the Myerson auction is optimal, i.e.
it maximized the expected auctioneer revenue in
Bayes-Nash equilibrium
3
Review
4
Review
Characterization of BNE:
Let A be an auction for selling a single item, where bidder i’s
value V is drawn independently from Fi .
i
If  1 ,..., n  is a BNE, then for each agent i:
1. The probability of allocation ai (vi ) is monotone increasing in vi
2. The utility u (v ) is a convex function of v with
i

i
i
vi
ui (vi )   ai ( z )dz
0
3.
The expected payment is determined by the allocation
probabilities:
vi
vi
pi (vi )  vi ai (vi )   ai ( z )dz   zai( z )dz
0
0
5
Today issues:
We will show a generalization version of
Myerson’s optimal mechanism, that
doesn’t require that virtual valuations be
increasing.
 We will see one examples

6
Optimal Mechanism
Our goal now is to derived the general version of Myerson’s optimal
mechanism, that doesn’t require that virtual valuations be
increasing.

We will a change in variables to quantile space, and define:
q : F (v )

The payment function:

The allocation function:

Notice that:
v(q) : F 1 (q)
pˆ (q) : p(v(q))
aˆ (q) : a(v(q))
a(v)  aˆ ( F (v)) f (v)
7
Optimal Mechanism

Given any v0 and q0  F (v0 ) we have:
ˆ (q0 )  p(v0 ) 
p
v0
 a(v)vdv
0
v0
q0
0
0
  aˆ( F (v))vf (v)dv   aˆ(q)v(q)dq
a(v)  aˆ ( F (v)) f (v)
q  F (v )
dq  f (v)dv
8
Optimal Mechanism


From this formula, we derive the expected revenue
from this bidder.
Let Q be the random variable representing this bidder’s
draw from the distribution in quantile space, i.e.,
Q=F(V) [Notice that 0  Q  1 ]. Then,
1 q0
[ pˆ (Q)]    aˆ (q)v(q)dqdq0
0 0
Reversing the order of integration, we get
9
Optimal Mechanism
1
1
0
q
[ pˆ (Q)]   aˆ (q )v(q )  dq0 dq
1
1
0
0
  aˆ (q )(1  q )v(q )dq   aˆ (q ) R (q )dq


Where R(q )  (1  q )v(q ) is called the revenue
curve.
It represents the expected revenue to a seller from
offering a price of v(q) to a buyer whose value V is
drawn from F.
10
Optimal Mechanism

Integrating by parts…
1
[ p(Q)]   R(q)aˆ (q) 0   aˆ (q ) R(q )dq
1
0
1
   aˆ (q ) R(q )dq  [aˆ (Q) R(Q)]
0
Explanation: R(1) = 0 and because Fi is on o, hi 
we get,
aˆ (0)  a(v(0))  a( F 1 (0))  a(0)  0
11
Optimal Mechanism
To summarizing, we proved a lemma:
Consider a bidder with value V drawn from distribution F,
with Q=F(V). Then his expected payment in a BIC
auction is

[ p(Q)]  [aˆ (Q) R(Q)]  [aˆ (Q) R(Q)]
Where R(q)  (1  q)v(q)
is the revenue curve.
12
Optimal Mechanism
Lemma: let
Proof:
q  F (v )
Then,
1  F (v )
 (v )  v 
  R '(q)
f (v )
d
d
R '(q) 
((1  q)v(q))  v  (1  q) v(q)
dq
dq
From v(q)  F 1 (q) and q  F (v ) we get:
1  F (v )
 v 
f (v )
13
Optimal Mechanism


As we discussed in David’s class (two weeks ago),
allocation to the bidder with the highest virtual value
(or equivalently, the largest –R’(q)) yields the optimal
auction, provided that virtual valuations are increasing.
Hedva Observation:
Let R(q)  (1  q)v(q) be the revenue curve with
q  F (v ). Then  (v)   R '(q) is (weakly) increasing
if and only if R(q) is concave. (a function is concave if it’s
derivative is increasing ).
14
Optimal Mechanism

To derived an optimal mechanism for the case when R(q) is
not concave envelope R (q) of R ( q )

Definition: R (q) is the infimum over concave functions
such that


g (q)
g (q)  R(q) for all q  [0,1] .
Passing from R () to
R ()
is called ironing.
R () can also be interpreted as a revenue curve when
randomization is allowed.

Definition: The iron virtual value of bidder i with value
v(qi ) is:
i (v)   Ri(qi )
15
Myerson auction with ironing

Now we can replace virtual values with ironed virtual values
to obtain an optimal auction even when virtual valuations are
not increasing.
Definition: The Myerson auction with ironing:
1.
Solicit a bid vector b from the bidders.
2.
Allocate the item to the bidder with the largest value of
i (bi ), if positive, and otherwise do not allocate.
3.
Charge the winning bidder i, if any, her threshold bid, the
minimum value she could bid and still win.
16
Optimal Mechanism


Theorem: The Myerson Auction described above is
optimal, i.e., it maximized the expected auctioneer
revenue in Bayes-Nash equilibrium when bidders values
are drawn from independent distribution.
Proof: The expected profit from a BIC auction is




  pˆ (Qi )      aˆi (Qi )( R(Qi ))  
 i

 i




ˆ
    ai (Qi ) Ri (Qi ) 
 i

17
Proof cont.




ˆ
ˆ
  ai (Qi )( R 'i (Qi ))     ai '(Qi )  Ri (Qi )  Ri (Qi )  
 i

 i

(add and subtract



 ).
  aˆi (Qi )( R 'i (Qi ))      aˆi(Qi )( Ri (Qi )) 
 i

 i

[aˆ (Q) R(Q)]  [aˆ (Q) R(Q)]
18
Proof cont.
Consider choosing a BIC allocation rule  () to
maximize the first term:


ˆ

   i (Q1 ,..., Qn )( Ri ) (Qi )  .
 i



This is optimized by allocating to the bidder with the
largest i (v)   Ri(qi ) , if positive.
Moreover, because R () is concave, this is an
increasing allocation rule and hence yields a dominant
strategy auction.
19
Proof cont.

Notice also that  Ri() is constant in each interval of nonconcavity of R () , and hence in each such interval
ai (q)

is constant and thus ai(q)  0.
Consider now the second term: In any BIC auction,
ai () must be increasing and hence
ai(q)  0 for all q.
But R(q)  R (q) for all q and hence the second term is nonpositive. Since the allocation rule that optimized the first term
has a( q )  0 whenever R(q)  R (q) , it ensures that the second
term is zero, which is best possible.




ˆ
ˆ
  ai (Qi )( R 'i (Qi ))     ai '(Qi )  Ri (Qi )  Ri (Qi )  
 i

 i

20
The advantage of just one more bidder…

One of the downside of implementing the optimal
auction is that it requires that the auctioneer know the
distributions from which agents values are drawn.

The following result shows that in instead of knowing
the distribution from which n independently and
identical distributed bidders are drawn, it suffices to
add just one more bidder into the auction.
21
Theorem
Let F be a distribution for which virtual valuations are
increasing. The expected revenue in the optimal auction
with independently and identical distributed bidders
with values drawn from F is upper bounded by the
expected revenue in a Vickrey auction with n+1
independently and identical distributed bidders with
values drawn from F.
22
Proof

The optimal (profit-maximizing) auction that is required
to sell the item is the Vichrey auction (this follows from
the lemma we saw in previous class, which says that for
any auction, the expected profit is equal to the
expected virtual value of the winner).

Second, observe that one possible n+1 bidder auction
that always sells the item consist of, first, running the
optimal auction with n bidders, and then, if the item is
unsold, giving the item to the n+1–st bidder for free.
23
First example:
War of Attrition
24
War of attrition (Reminder)

In Liran’s class we considered the war of attrition: this
single item auction allocates the item to the player that
bids the highest, charges the winner the second-highest
bid, and charge all others players their bid.

Notice that in this auction the bidders decides at the
beginning of the game when to drop out.
25
War of attrition (Reminder)
Formulas that we derived in Liran’s class that we will need
for today: Let  be a symmetric strictly increasing
equilibrium strategy, Then:
 Expected payment of an agent in a war-of-attrition
auction in which all bidders use  is

And
26
Dynamic war of attrition

A more natural model is for bidders to dynamically decide
when to drop out.

The last player to drop out is then the winner of the item.

With two players this is equivalent to the model discussed in
Liran’s class:

The equilibrium strategy  (v ) := how long a player with
value v waits before dropping out.
27
Dynamic war of attrition
v

 satisfies:
Where h( w) 
v
f ( w)
 (v )   w
dw   wh( w)dw
1  F ( w)
0
0
f ( w)
f ( w)

1  F ( w) F ( w)
is the hazard rate of
the distribution F.
(it followed from the equilibrium we found in Liran’s class:
).
28
Dynamic war of attrition



We rederive this here without the use of revenue
equivalence.
To this end, assume that the opponent plays  () .
The agent’s utility from playing  ( w) when his value is
v is:
w
u ( w | v)  vF ( w)  F ( w)  ( w)    ( z ) f ( z )dz
0

Differentiating with respect to w, we have:
u ( w | v)
 vf ( w)  f ( w)  ( w)  F ( w)  (w)   ( w) f ( w)
w
 vf ( w)  F ( w)  ( w)
29
Dynamic war of attrition

For this to be maximized at
w  v , we must have
vf (v)  F (v)  (v)
implying
v
v
f ( w)
 (v)   wh( w)dw   w
dw
F ( w)
0
0
30
Dynamic war of attrition

With three players strategy has two component,  (v ) and
 ( y, v) .

For a player with value v, he will drop out at time
 (v )
if
no one else dropped out earlier.

Otherwise, if another player dropped out at time  ( y )   (v)
 ( y )   ( y, v)
, our player will continue until time
.
31
Dynamic war of attrition

The case of two players applied at time y implies that in
equilibrium
v
 ( y, v)   zh( z )dz
y
f ( z)
Since the update density F ( y ) 1z  y has the same hazard
rate as f.

Unfortunately there is no equilibrium once there are
three players…
32
Dynamic war of attrition

To see this, suppose that players 2 and 3 are playing
 () and  (, ) , and player 1 with value v plays  (v   )
instead of  (v ) .
Then
0  u(v | v)  u(v   | v)  C 2  F (v) 2 ( (v)   (v   ))

Since with probability F (v)2 , the other two players outlast player
1 and then he pays an additional
for naught.

 (v )   (v   )
2


2
f
(
z
)
dz

C



And with probability
for some constant C,

 v 

both of the others players drop out first.
v
33
Dynamic war of attrition

Thus, it must be that
 (v)   (v   )  C 2 F (v)2

And for any k we have:
C
C
2
2
 (v  k  )   (v  k    ) 



F (v  k  ) 2
F (v)2
(since
F (v) is non-increasing function).
34
Dynamic war of attrition

Summing from k=0 to
v/
:
 (v)   (v   )    (v   )   (v  2 )   ...    (v  (

   (v)   (0)   CF (v) 2  2
v

v 
 1) )   (v   ) 

 
v
 CF (v) 2  v
 (v)  CF (v)2  v

And hence:

Finally, we observe that
 (v )  0
 (v )  0
is not equilibrium since a
player, knowing that the other players are going to drop out
immediately, will prefer to stay in.
35
Thanks for listening
36