Algorithmic Game Theory, Summer 2019 Lecture 18 (5 pages)

Revenue Maximization with Identical Distributions

Thomas Kesselheim Last Update: June 17, 2019

Last time, we introduced the problem of maximizing revenue in an auction. We saw a

reasonably simple mechanism for the case of a single item. The results also hold for other
single-parameter settings—for example, if we have multiple copies of the same items.
We assume that the bidders’ valuations v1 , . . . , vn are drawn from known distributions.
Today, we will consider the case that these are identical. That is, v1 , . . . , vn are independent and
identically distributed according to D. The distribution is continuous; it has density function
f and cumulative distribution function F . We define a function ϕ by ϕ(t) = t − 1−F (t)
f (t) . This
function is called the virtual-value function. Today, we will keep the assumption that the
distribution is regular, which means that ϕ is increasing.
Our main result last time was that the expected revenue of a truthful mechanism equals its
expected virtual welfare:
" # " #
X X
Ev1 ,...,vn ∼D pi (v) = Ev1 ,...,vn ∼D ϕ(vi )xi (v) .
i∈N i∈N

From this, it is easy to conclude that a mechanism that chooses x(b) so as to maximize
P
i∈N ϕ(bi )xi (b) maximizes the expected revenue. Note that this allocation rule is monotone
and this way gives a truthful mechanism if and only if the distribution is regular.
For a single item, this means to select the bidder with the highest virtual bid ϕ(bi ) if this
value is positive. Otherwise, the item is not allocated.

1 Virtual-Welfare Maximization
We have seen that choosing the allocation with maximum virtual welfare maximizes the expected
revenue. In the case of a single item, this means to give the item the bidder i who maximizes
ϕ(bi ) if ϕ(bi ) ≥ 0. In the case of identical, regular distributions, because of monotonicity and
because the functions are identical, this is the bidder with maximal bi . Call this bidder i∗ .
The payment is again the smallest bid t that would make him a winner. Two possible cases
can happen: If ϕ(maxi6=i∗ bi ) ≥ 0, then some other bidder would have won in the absence of i∗ .
So, he has to pay t = maxi6=i∗ bi . If ϕ(maxi6=i∗ bi ) < 0, then nobody would have won the item.
However, i∗ still would have to bid so that ϕ(t) ≥ 0. In other words, he has to pay ϕ−1 (0).
Summarizing, the payment of bidder i∗ is
 
−1
max ϕ (0), max
∗
bi .
i6=i

That is, we have a second-price auction with a reserve price of ϕ−1 (0). Just add a bidder bidding
ϕ−1 (0) to the second-price auction and if this bidder wins, nobody gets the item.

2 Comparison to Second-Price Auction

We have seen a revenue-optimal mechanism for identically distributed bidders. In comparison to
the general case, the mechanism is fairly easy. But what if we want an easier mechanism? For
example, if we didn’t know about the results on revenue maximization, we would probably use
the second-price auction. How well does it perform?
Algorithmic Game Theory, Summer 2019 Lecture 18 (page 2 of 5)

Lemma 18.1. If all valuations are drawn from the same regular distribution, the second-price
auction maximizes the expected revenue among all truthful mechanisms that always allocate the
item.

Proof. Let M∗ = (x∗ , p∗ ) be the second-price auction and let M = (x, p) be any other truthful
mechanism that always allocates the item.
Both mechanisms always allocate the item. That is, given any valuation/bid profile v, there
are i∗ , i0 ∈ N such that the second-price auction allocates to i∗ and M allocates to i0 . The
second-price auction gives the item to the bidder of highest value/bid, so vi∗ ≥ vi0 . Furthermore,
ϕ is monotone, that is,

ϕ(vi )x∗ (v) = ϕ(vi∗ ) ≥ ϕ(vi0 ) =

X X
ϕ(vi )x(v) .
i∈N i∈N

By taking expectations on both sides, we get

" # " # " # " #
p∗i (v) = Ev ϕ(vi )x∗ (v) ≥ Ev
X X X X
Ev ϕ(vi )x(v) = Ev pi (v) .
i∈N i∈N i∈N i∈N

This observation already nicely proves some intuition to be correct: The additional revenue
that can be obtained compared to a second-price auction is due to the fact that one sometimes
does not allocate the item.
Another theorem takes this observation to the next level.

Theorem 18.2 (Bulow/Klemperer, 1996). Consider a regular distribution D. For any n ∈ N,

the expected revenue of a second-price auction with n + 1 bidders drawn from D is at least as
high as the optimal expected revenue with n bidders drawn from D.

Proof. What makes the proof complicated is the fact that we have to deal with different numbers
of bidders. We can make our life easier by assuming that there are n + 1 bidders overall. The
revenue-optimal mechanism for n bidders can be interpreted in this setting as a mechanism that
simply ignores bidder n + 1. Let M be this mechanism.
We can turn M into a mechanism M0 that always allocates the item by assigning it to
bidder n + 1 for free if M does not allocate it. Note that the expected revenue of M and M0
are identical.
Now, let M∗ be the second-price auction. By Lemma 18.1, we know that the expected
revenue of M∗ is at least as high as the expected revenue of M0 .

3 Posting One Price

There is an even simpler mechanism than a second-price auction: Simply fix a price p∗ and ask
the bidders one after the other if they want to buy the item at price p∗ . To set this price, we
will make use of a result in optimal stopping theory.

Theorem 18.3 (i.i.d. Prophet Inequality). Let Y1 , . . . , Yn be independent, identically distributed,

non-negative random variables. Let τ be a threshold such that Pr [Yi > τ ] = n1 and let Yselect be
the value of the first Yi variable above this threshold, 0 if there is none. Then
n 
1
   
E [Yselect ] ≥ 1 − 1 − E max Yi .
n i
 n
1 1
Note that 1 − 1 − n ≥1− e ≈ 0.63 for all n.
Algorithmic Game Theory, Summer 2019 Lecture 18 (page 3 of 5)

Proof. Note that to bound the expectation it is sufficient to show that for all z ≥ 0
n 
1
   
Pr [Yselect ≥ z] ≥ 1 − 1 − Pr max Yi ≥ z .
n i

We distinguish two cases. If z ≤ τ , then we use that Yselect automatically has value τ if any
Yi exceeds the threshold. Therefore
n
1

Pr [Yselect ≥ z] = Pr [∃i : Yi > τ ] = 1 − 1 − .
n

As Pr [maxi Yi ≥ z] ≤ 1, this implies the claim.

Now we consider z > τ . We can decompose the event Yselect ≥ z into disjoint events
Y1 , . . . , Yi−1 ≤ τ, Yi ≥ z. Because the Yi are independent and identically distributed, this is
n
X
Pr [Yselect ≥ z] = Pr [Y1 , . . . , Yi−1 ≤ τ, Yi ≥ z]
i=1
Xn
= Pr [Y1 ≤ τ ] . . . Pr [Yi−1 ≤ τ ] Pr [Yi ≥ z]
i=1
n  i−1
X 1
= 1− Pr [Y1 ≥ z]
i=1
n
 n
1
1− 1− n
=   Pr [Y1 ≥ z]
1
1− 1− n
1 n
   
= 1− 1− nPr [Y1 ≥ z]
n
  n
1 n X
 
= 1− 1− Pr [Yi ≥ z] .
n i=1

Furthermore, we can re-write the event that the maximum Yi is at least z as a union of
disjoint events of the form Y1 < z, . . . , Yi−1 < z, Yi ≥ z
  " n #
[
Pr max Yi ≥ z = Pr Y1 < z, . . . , Yi−1 < z, Yi ≥ z
i
i=1
n
X n
X
= Pr [Y1 < z, . . . , Yi−1 < z, Yi ≥ z] ≤ Pr [Yi ≥ z] .
i=1 i=1
  n 
1
In combination, this gives us Pr [Yselect ≥ z] ≥ 1 − 1 − n Pr [maxi Yi ≥ z], which is
exactly what we claimed.

Coming now back to our problem of setting a price of maximize revenue, we choose it as
1
  
p∗ = max ϕ−1 (0), F −1 1 − .
n
The first term ensures that we only select bidders of non-negative virtual value. The second
term makes sure that the probability that a bidder is selected is at most n1 .

Theorem 18.4. The mechanism that uses price p∗ and approaches bidders in order 1, . . . , n
gives a 1 − (1 − n1 )n ≥ 1 − 1e -approximation to the optimal expected revenue.
Algorithmic Game Theory, Summer 2019 Lecture 18 (page 4 of 5)

Proof. We use Theorem 18.3 to prove this theorem. Note that it is enough to bound the virtual
welfare rather than the revenue. So, let Yi = max{0, ϕ(vi )} be the virtual value of bidder i but
at least 0. The optimal virtual welfare is exactly maxi∈N Yi . Our mechanism’s virtual welfare is
the first Yi such that vi > p∗ , which is nothing but the first Yi for which Yi > ϕ(p∗ ).
If ϕ−1 (0) ≤ F −1 1 − n1 , Theorem 18.3 gives us exactly what we want. In this case,

1 1
  
Pr [Yi > ϕ(p∗ )] = Pr vi > F −1 1 − = .
n n
So, n 
1
   
E [Yselect ] ≥ 1 − 1 − E max Yi .
n i
 
If ϕ−1 (0) > F −1 1 − 1
n , then

1
Pr [Yi > ϕ(p∗ )] = Pr [Yi > 0] < .
n
So, we choose a higher threshold than Theorem 18.3 tells us to. (It is simply not possible to
set the threshold exactly as the theorem requires because there is a discontinuity of Pr [Yi > τ ]
at τ = 0. However, there is no actual difference because we only might continue the sequence
although Theorem 18.3 would tell us to stop at 0. The value of Yselect can therefore only be
higher.

4 Bonus Content: Beyond Truthfulness

Our insights so far only concern truthful direct mechanisms. One would be tempted to think
that non-truthful mechanisms might yield a higher revenue. For example, given the same bids,
in a first-price auction the revenue is higher than in a second-price auction, which is truthful.
However, this is not true if one takes into consideration the strategic behavior of the bidders.
We will now sketch a proof that considering truthful mechanisms is not actually a restriction.
Theorem 18.5. If all bidder’s distributions are regular, there is no mechanism M0 that has a
Bayes-Nash equilibrium (βi )i∈N in which the revenue is higher than in the dominant-strategy
equilibrium of the virtual-welfare maximizer.
Proof Sketch. Assume that there is a mechanism M0 with a Bayes-Nash equilibrium (βi )i∈N of
higher revenue. Our first observation is that we can build a direct mechanism M00 that given v
first computes β(v) and then runs M0 . For any valuation profile v, Mechanism M00 gives the
same outcome and payments on truthful reports that M0 gives on (βi )i∈N . (This technique is
called the revelation principle.)
Mechanism M00 is what we call Bayes-Nash incentive compatible: Truthful bidding is a
Bayes-Nash equilibrium. (This does not mean that it is dominant-strategy incentive compatible;
we have seen such examples.)
For such Bayes-Nash incentive compatible mechanisms, a variant of Myerson’s lemma holds.
It tells us that the expected payments are unique. For every i ∈ N and every bi , we have
" Z bi #
Ev−i [pi (bi , v−i )] = Ev−i bi xi (bi , v−i ) − fi (t, v−i )dt .
0

It is derived exactly the same way as Myerson’s lemma for dominant-strategy incentive compatible
mechanisms: One can use the payment-difference sandwich, which now holds in expectation.
The exact same calculations as above give us
" # " #
X X
Ev pi (v) = Ev ϕi (vi )xi (v) ,
i∈N i∈N
Algorithmic Game Theory, Summer 2019 Lecture 18 (page 5 of 5)

meaning that still, even under the weaker assumption of Bayes-Nash incentive compatibility, the
expected revenue is equal to the expected virtual welfare.
Among all mechanisms (without any further assumption), the virtual-welfare maximizer has
the highest expected virtual welfare.

5 Bonus Content: Multiple Items

So far, all our results were restricted to single-parameter settings and mostly just to allocating a
single item. If we turn to multiple items, the theory suddenly becomes much more complicate.
To get an idea what it happening, let us consider a single bidder and two items. Note that a
single item you would sell at the price p∗ that maximizes p∗ Pr [v ≥ p∗ ].
We assume that the bidders’ values are v1 for item 1 and v2 for item 2. The valuation is
additive, that is, for getting both items the value is v1 + v2 . We did not consider maximizing
social welfare for such additive valuations because it is trivial: We can treat the items separately.
For example, run a second-price auction for each of them. One might think that this is also true
for revenue. But it is not.

5.1 Item Bundling

Assume that v1 and v2 are independent and both uniformly drawn from {1, 2}. Let us first set
item prices p∗j . If we set p∗j = 1 or p∗j = 2, then the expected revenue from item j is 1. For other
prices it is even less. So, the maximum revenue from item prices is 2.
An alternative mechanism is to only sell items 1 and 2 as a bundle. If we set the price of
bundle {1, 2} to 3 (single items cannot be purchased), then the bidder will always buy the bundle
unless v1 = v2 = 1. So, the revenue is 3(1 − Pr [v1 = v2 = 1]) = 3(1 − 41 ) = 94 > 2.

5.2 Lotteries
There is something even stranger that happens. Our results for a single item are still true if we
allow our mechanism to sell “lottery tickets”. For example, this might mean that with a medium
bid one wins the item with probability 12 , with a small bid the probability is 0, with a high bid
it is 1. Also for those lottery mechanisms, the expected revenue is equal to expected virtual
welfare. We can maximize expected virtual welfare without resorting to selling lotteries. So the
revenue-optimal mechanism works without lotteries.
In the case of multiple items, this is again different. Consider the case that v1 and v2 are
independent; v1 is drawn uniformly from {1, 2}, v2 is drawn uniformly from {1, 3}. The optimal
mechanism that does not sell lottery tickets prices item 1 at 1 and item 2 at 3. Its expected
revenue is 1 + 32 = 52 = 2.5. However, there is a mechanism with higher revenue. It offers the
buyer the following two options. One choice is to get both items for sure and pay 4. The other
one is a lottery ticket for 2.5. This ticket includes item 1 for sure and item 2 with probability 12 .
One can show that this mechanism gives expected revenue 2.625 and that this is the optimal
revenue.