Transcript ppt

Auction Theory
Class 2 – Revenue equivalence
1
This class: revenue
• Revenue in auctions
– Connection to order statistics
• The revelation principle
• The revenue equivalence theorem
– Example: all-pay auctions.
2
English vs. Vickrey
The English Auction:
• Price starts at 0
Vickrey (2nd price) auction:
• Bidders send bids.
• Price increases until only one
bidder is left.
• Highest bid wins,
pays 2nd highest bid.
• Private value model: each person has a privately
known value for the item.
• We saw: the two auctions are equivalent in the
private value model.
• Auctions are efficient:
dominant strategy for each player: truthfulness.
3
Dutch vs. 1st-price
The Dutch Auction:
• Price starts at max-price.
• Price drops until a bidder
agrees to buy.
1st-price auction:
• Bidders send bids.
• Highest bid wins,
pays his bid.
• Dutch auctions and 1st price auctions are strategically
equivalent. (asynchronous vs simple & fast)
• No dominant strategies. (tradeoff: chance of winning,
payment upon winning.)
• Analysis in a Bayesian model:
– Values are randomly drawn from a probability distribution.
• Strategy: a function. “What is my bid given my value?”
4
Bayes-Nash eq. in 1st-price auctions
• We considered the simplest Bayesian model:
– n bidders.
– Values drawn uniformly from [0,1].
Then:
In a 1st-price auction, it is a (Bayesian) Nash
n 1
vi
equilibrium when all bidders bid
n
• An auction is efficient, if in (Bayes) Nash equilibrium
the bidder with the highest value always wins.
– 1st price is efficient!
5
Optimal auctions
• Usually the term optimal auctions stands for revenue
maximization.
• What is maximal revenue?
– We can always charge the winner his value.
• Maximal revenue: optimal expected revenue in
equilibrium.
– Assuming a probability distribution on the values.
– Over all the possible mechanisms.
– Under individual-rationality constraints (later).
6
Example: Spectrum auctions
• One of the main triggers to
auction theory.
• FCC in the US sells spectrum,
mainly for cellular networks.
• Improved auctions since the
90’s increased efficiency +
revenue considerably.
• Complicated (“combinatorial”)
auction, in many countries.
– (more details further in the course)
7
New Zealand Spectrum Auctions
• A Vickrey (2nd price) auction was run in New Zealand
to sale a bunch of auctions. (In 1990)
• Winning bid:
$100000
Second highest:
$6 (!!!!)
Essentially zero revenue.
• NZ Returned to 1st price method the year after.
– After that, went to a more complicated auction (in few
weeks).
• Was it avoidable?
8
Auctions with uniform distributions
A simple Bayesian auction model:
• 2 buyers
• Values are between 0 and 1.
• Values are distributed uniformly on [0,1]
What is the expected revenue gained by 2nd-price
and 1st price auctions?
Revenue in 2nd-price auctions
•
In 2nd-price auction, the payment is the minimum of
the two values.
–
•
E[ revenue] = E[ min{x,y} ]
Claim:
when x,y ~ U[0,1] we have E[ min{x,y} ]=1/3
Revenue in 2nd-price auctions
•
Proof:
–
assume that v1=x. Then, the expected revenue is:
2
x
x
x   1  x   x  x 
2
2
•
0
x
We can now compute the expected revenue
(expectation over all possible x):
1
1
2
2
x
x
E[min{x,y}]   ( x  )  f ( x)dx   ( x  )dx 
2
2
0
0
1
x
1
x 
    
3
 2 6 0
2
3
1
Order statistics
Let v1,…,vn be n random variables.
–
–
–
–
The highest realization is called the 1st-order statistic.
The second highest is the called 2nd-order statistic.
….
The smallest is the nth-order statistic.
Example: the uniform distribution, 2 samples.
–
The expected 1st-order statistic: 2/3
•
–
In auctions: expected efficiency
The expected 2nd-order statistic: 1/3
•
In auctions: expected revenue
Expected order statistics
One sample
0
1
1/2
Two samples
0
1/3
1
2/3
Three samples
0
1/4
2/4
3/4
1
In general, for the uniform distribution with n
samples:
• k’th order statistic of n variables is (n+1-k)/n+1)
• 1st-order statistic: n/n+1
Revenue in 1st-price auctions
• We still assume 2 bidders, uniform distribution
Revenue in 1st price:
• bidders bid vi/2.
• Revenue is the highest bid.
Expected revenue
= E[ max(v1/2,v2/2) ]
= ½ E[ max(v1,v2)]
= ½ × 2/3
= 1/3
Same revenue as in 2nd-price auctions.
14
1st vs. 2nd price
Revenue in 2nd price:
Revenue in 1st price:
• Bidders bid truthfully.
• Revenue is 2nd highest bid:
• bidders bid
• Expected revenue is
E[revenue] 
n 1
n 1

n -1 
 n -1
E max
v1 ,...,
vn 
n
 n


n -1

Emax v1 ,...,vn 
n

n -1 n
n n 1
n -1

n 1
What happened? Coincidence?
15
This class
• Revenue in auctions
– Connection to order statistics
• The revelation principle
• The revenue equivalence theorem
– Example: all-pay auctions.
16
Implementation
Our general goal: given an objective (for example,
maximize efficiency or revenue), construct an auction
that achieves this goal in an equilibrium.
– "Implementation”
– Equilibrium concept: Bayes-Nash
For example: when our goal is maximal efficiency
– 2nd-price auctions maximize efficiency in a Bayes-Nash
equilibrium
• Even stronger solution: truthfulness (in dominant strategies).
– 1st price auctions also achieve this goal.
• Not truthful, no dominant strategies.
– Many other auctions are efficient (e.g., all-pay auctions).
Terminology
Direct-revelation mechanism: player are asked to report
their true value.
– Non direct revelation: English and Dutch auction, most
iterative auctions, concise menu of actions.
– Concepts relates to the message space in the auction.
Truthful mechanisms: direct-revelation mechanisms
where revealing the truth is (a Bayes Nash) equilibrium.
– Other solution concepts may apply.
– Alternative term: Incentive Compatibility.
• What’s so special about revealing the truth?
– Maybe better results can be obtained when people report half
their value, or any other strategy?
The revelation principle
• Problem: the space of possible mechanisms is often too
large.
• A helpful insight: we can actually focus our attention to
truthful (direct revelation) mechanisms.
– This will simplify the analysis considerably.
• “The revelation principle”
– “every outcome can be achieved by truthful mechanism”
• One of the simplest, yet trickiest, concepts in auction
theory.
The revelation principle
Theorem (“The Revelation Principle”):
Consider an auction where the profile of strategies s1,…,sn
is a Bayes-Nash equilibrium.
Then, there exists a truthful mechanism with exactly the
same allocation and payments (“payoff equivalent”).
Recall: truthful =
direct revelation + truthful Bayes-Nash equilibrium.
• Basic idea: we can simulate any mechanism via a
truthful mechanism which is payoff equivalent.
The revelation principle
• Proof (trivial): The original mechanism:
Bidders
v1
v1ss11(v
(v11))
v2
v2 ss22(v
(v22))
v3
v3 ss33(v
(v33))
v4
v4 ss44(v
(v44))
Auction mechanism
Allocation
(winners)
Auction
protocol
payments
The revelation principle
• Proof (trivial): A direct-revelation mechanism:
Bidders reports their true types,
The auction simulates their equilibrium
strategies.
v1
v1s1(v1)
v2
v2 s2(v2)
v3
v3 s3(v3)
v4
Allocation
(winners)
Auction
protocol
payments
v4 s4(v4)
Equilibrium is straightforward: if a bidder had a profitable deviation
here, he would have one in the original mechanism.
The revelation principle
• Example:
– In 1st-price auctions with the uniform distribution:
bidders would bid truthfully and the mechanism will
“change” their bids to be n  1 v
i
n
– In English auctions (non direct revelation):
people will bid truthfully, and the mechanism will raise hands
according to their strategy in the auction.
• Bottom line: Due to the revelation principle, from now
on we will concentrate on truthful mechanisms.
This class
• Revenue in auctions
– Connection to order statistics
• The revelation principle
• The revenue equivalence theorem
– Example: all-pay auctions.
24
Revenue equivalence
• We saw examples where the revenue in 2nd-price and
1st-price auctions is the same.
• Can we have a general theorem?
• Yes.
Informally:
What matters is the allocation. Auctions with the
same allocation have the same revenue.
25
Revenue Equivalence Theorem
Assumptions:
– vi‘s are drawn independently from some F on [a,b]
– F is continuous and strictly increasing
– Bidders are risk neutral
Theorem (The Revenue Equivalence Theorem):
Consider two auction such that:
1. (same allocation) When player i bids v his probability to win
is the same in the two auctions (for all i and v) in
equilibrium.
2. (normalization) If a player bids a (the lowest possible
value) he will pay the same amount in both auctions.
Then, in equilibrium, the two auctions earn the same revenue.
Proof
• Idea:
we will start from the incentive-compatibility
(truthfulness) constraints.
We will show that the allocation function of the
auction actually determines the payment for each
player.
– If the same allocation function is achieved in equilibrium, then the
expected payment of each player must be the same.
• Note: Due to the revelation principle, we will look at
truthful auctions.
27
Proof
• Consider some auction protocol A, and a bidder i.
• Notations: in the auction A,
– Qi(v) = the probability that bidder i wins when he bids v.
– pi(v) = the expected payment of bidder i when he bids v.
– ui(v) = the expected surplus (utility) of player i when he
bids v and his true value is v.
ui(v) = Qi(v) v - pi(v)
• In a truthful equilibrium: i gains higher surplus when
bidding his true value v than some value v’.
– Qi(v) v - pi(v) ≥ Qi(v’) v - pi(v’)
=ui(v)
=ui(v’)+ ( v – v’) Qi(v’)
We get: truthfulness  ui(v) ≥ ui(v’)+ ( v – v’) Qi(v’)
28
Proof
• We get: truthfulness 
ui(v) ≥ ui(v’)+ ( v – v’) Qi(v’) or
u i (v) - u i (v’ )
 Qi (v' )
v – v’
• Similarly, since a bidder with true value v’ will not prefer
bidding v and thus
u i (v) - u i (v’ )
ui(v’) ≥ ui(v)+ ( v’ – v) Qi(v) or
 Q (v )
v – v’
Let dv = v-v’
i
u i (v' dv) - u i (v’ )
Qi (v' ) 
 Qi (v' dv )
dv
Taking dv  0 we get:
du i (v' )
 Qi (v ' )
dv'
29
Proof
du i (v' )
• We saw:
 Qi (v ' )
dv'
Assume ui(a)=0
integrating
v'
v'
a
a
u ii (v'
(v' )  u iQ(a)
i ( v)dv
 Qi (v)dv
• We know:
u i (v')  v' Qi (v' )  pi (v' )
• And conclude:
pi (v' )  v' Qi (v' )  u i (v')
v'
pi (v' )  v' Qi (v' )   Qi (v)dv
a
• Of course:
n
Erevenue   pi (vi )
i 1
• Interpretation: expected revenue, in equilibrium,
depends only on the allocation.
– same allocation  same revenue (as long as Q() and ui(a) are the same).
30
Picture
v'
pi (v' )  v' Qi (v' )   Qi (v)dv
Qi (v)
a
Qi (v' )
a
v'
v
31
Example: 2 players, uniform dist.
Q1(v)= v
pi(1/2)= 1/2*1/2*1/2
pi(v)= v*v*1/2=v2/2
The expected revenue from bidder 1:
1

0
3 1
2
v
v
dv 
2
6
0

1
6
For 2 bidders: E[revenue]=1/6+1/6=1/3
Qi (v)
v'
1/2
pi (v' )  v' Qi (v' )   Qi (v)dv
a
1/2
v
32
Revenue equivalence theorem
• No coincidence!
– Somewhat unintuitively, revenue depends only on the way
the winner is chosen, not on payments.
– Since 2nd-price auctions and 1st-price auctions have the
same (efficient) allocation, they will earn the same
revenue!
• One of the most striking results in mechanism design
• Applies in other, more general setting.
• Lesson: when designing auctions, focus on the allocation, not
on tweaking the prices.
33
Remark: Individual rationality
• The following mechanism gains lots of revenue:
– Charge all players $10000000
• Bidder will clearly not participate.
• We thus have individual-rationality (or participation)
constraints on mechanisms:
bidders gain positive utility in equilibrium .
– This is the reason for condition 2 in the theorem.
34
This class
• Revenue in auctions
– Connection to order statistics
• The revelation principle
• The revenue equivalence theorem
– Example: all-pay auctions.
35
Example: All-pay auction (1/3)
• Rules:
– Sealed bid
– Highest bid wins
– Everyone pay their bid
• Claim: Equilibrium with the uniform distribution:
n 1 n
v
b(v)=
n
• Does it achieve more or less revenue?
– Note: Bidders shade their bids as the competition
increases.
36
All-pay auction (2/3)
• expected payment per each player: her bid.
n 1 n
b (v ) 
v
n
• Expected payment for each bidder:
• Each bidder bids

1n
0
1 n
n 1
v dv 
n
n
1
v
0
n
dv 
1
n

1

n 1 v
1  n 1


  
n

1
n 
 0 n  n  1 
• Revenue: from n bidders E[revenue]  n  1
n 1
• Revenue equivalence!
37
All-pay auction (3/3)
• Examples:
– crowdsourcing over the internet:
• First person to complete a task for me gets a reward.
• A group of people invest time in the task. (=payment)
• Only the winner gets the reward.
– Advertising auction:
• Collect suggestion for campaigns, choose a winner.
• All advertiser incur cost of preparing the campaign.
• Only one wins.
– Lobbying
– War of attrition
• Animals invest (b1,b2) in fighting.
38
What did we see so far
• 2nd-price, 1st-price, all pay:
all obtain the same seller revenue.
• Revenue equivalence theorem:
Auctions with the same allocation decisions earn the
same expected seller revenue in equilibrium.
– Constraint: individual rationality (participation constraint)
• Many assumptions:
–
–
–
–
–
statistical independence,
risk neutrality,
no externalities,
private values,
…
39
Next topic
• Optimal revenue:
which auctions achieve the highest revenue?
40