Separation between Second Price Auctions with Personalized Reserves and the Revenue Optimal Auction
Will Ma Balasubramanian Sivan




Separation between Second Price Auctions with Personalized Reserves and the Revenue Optimal Auction


    Will MaGoogle Research. willma@google.com.
 Balasubramanian SivanGoogle Research. balusivan@google.com.

    
============================================================================================================





What fraction of the single item n buyers setting's expected optimal revenue () can the second price auction with reserves achieve? In the special case where the buyers' valuation distributions are all drawn i.i.d. and the distributions satisfy the regularity condition, the second price auction with an anonymous reserve () is the optimal auction itself.  As the setting gets more complex, there are established upper bounds on the fraction of  that  can achieve. On the contrary, no such upper bounds are known for the fraction of  achievable by the second price auction with eager personalized reserves (). In particular, no separation was earlier known between 's revenue and  even in the most general setting of non-identical product distributions that don't satisfy the regularity condition. In this paper we establish the first separation results for : we show that even in the case of distributions drawn i.i.d., but not necessarily satisfying the regularity condition, the  cannot achieve more than a 0.778 fraction of  in general. Combined with the result from <cit.> that  can achieve at least a 0.745 fraction of , this nearly bridges the gap between upper and lower bounds on 's approximation factor.





§ INTRODUCTION

Approximating the optimal auction's expected revenue  by simple mechanisms has received a lot of attention in the algorithmic game theory literature, especially in the last decade. The seminal result of <cit.> describes the optimal auction in a single agent n-items setting when buyer valuations are drawn from a product distribution. When the buyer valuation distributions are independent and identical (i.i.d.) and satisfy a technical regularity condition, Myerson's optimal auction coincides with the second price (Vickrey's) auction with an anonymous reserve price (). When the setting gets more complex, either because the distributions are not identical or because the distributions don't satisfy the regularity condition, or both,  ceases to be the optimal auction.  Bounds on the suboptimality are known in many cases:

    
  * when the distributions are non-identical (independent) and irregular, <cit.> show that  cannot get more than a 1/n fraction of  in general, and it is straightforward to show that this is tight;
    
  * when the distributions are non-identical (independent) and regular, <cit.> show that  cannot get more than a 1/2 fraction of  in general, <cit.> show that  can achieve a 1/e fraction of  in general, and recently <cit.> show that  cannot get more than a 1/2.15 fraction of  in general;
    
  * when the distributions are identical (independent) and irregular, the pricing problem can be reduced to the prophet inequalities problem on ironed virtual values, for which a 1/2 approximation via a uniform threshold is known (<cit.>). Since the distributions are identical, the uniform threshold in the ironed virtual value space translates into a uniform threshold in the value space, thus showing that ASP can achieve a 1/2 approximation as well.  This approximation factor of  is tight, as shown in <cit.>, although we will also provide a self-contained proof here as a corollary.


On the contrary, no upper bounds are known on the fraction of  obtainable by a second price auction with personalized reserve prices.
When the reserve prices are personalized, it matters whether the bidders are ranked after eliminating those below the reserve (eager, “") or before eliminating those below the reserve (lazy, “").
In the eager version, we first eliminate bidders below their respective reserves, and then charge the highest surviving bidder (if any) the maximum of his own reserve price and the second highest surviving bid.
In the lazy version, we first decide the potential winner to be the highest bidder, eliminate him if he doesn't survive his reserve price (in which case we allocate the good to nobody), and then if he survives allocate the good to him at a price of maximum of his reserve price and the second highest bid. <cit.> show that for general correlated distributions, the optimal revenue obtainable from  and  are incomparable (i.e. either could be higher on a specific instance), but are within a factor of two. When the distributions are independent  show that the optimal 's revenue dominates the optimal 's revenue. Therefore from the perspective of upper bounding the fraction of  that is obtainable, 
any result for  implies a result for .
ESP's are also more widely used, and are a more natural auction to run[For instance, when there is at least one buyer that survives their reserve price,  always allocates the item, whereas  could result in no allocation even then.]).



  
Our result. Our main result (Theorem <ref>) is an upper bound on the maximum fraction of  that  can obtain. We show that in the n buyers single item setting, even when the buyer values are drawn i.i.d. (but not necessarily from a regular distribution), the fraction of  that  can extract in general is at most 0.778. The i.i.d. irregular setting is the simplest non-trivial setting to consider since, as discussed earlier, the i.i.d. regular setting results in a 1 approximation from even a second price auction with anonymous reserve price. 



  
Corollary. Our construction can also be modified to show that  cannot get more than 1/2 of  for i.i.d. irregular valuations, establishing that the 1/2 approximation factor for  is tight.



  
Near tightness of ESP result. A mechanism very related to  is the sequential posted price mechanism () where the seller computes one price per buyer, and then approaches the buyers in the descending order of posted prices until the item is sold. In general single-parameter environments with matroid feasibility constraints (this includes the single item setting we study as a special case), <cit.> showed the the revenue of an   that uses the posted prices of an  as its personalized reserve prices is at least as high as the 's revenue. This, combined with the recent result of <cit.> showing that  can achieve a 0.745 fraction of  in the i.i.d. setting with possibly irregular distributions, shows that  can also achieve at least a 0.745 approximation factor in the i.i.d. setting. Thus, our upper bound of 0.778 on 's approximation factor in the i.i.d. setting is quite close to this lower bound of 0.745. In the case of   both the upper and lower bound are known to be 0.745: the upper bound of 0.745 for s was established by <cit.> about 3.5 decades prior to the matching lower bound established by 



  
 vs : the benefit of simultaneity. The primary advantage of  over  is that  considers all buyers simultaneously while  considers buyers sequentially. Thus, as <cit.> show,  should only earn better revenue by benefiting from this simultaneity. Our upper bound of 0.778 on the approximation factor of  shows that this benefit of simultaneity is quite small in general, given that s themselves can achieve a 0.745 approximation. In a sense, our result shows that discrimination is more crucial for revenue maximization than simultaneity. Closing this gap further, or establishing a separation between  and  remains an interesting open problem. 



§ UPPER BOUND ON ESP APPROXIMATION FACTOR

We provide an example that establishes the upper bound on 's approximation factor.
 
There are n buyers, with n→∞.  Each buyer's valuation is drawn i.i.d. from a discrete distribution F where


    v∼ F = 
    n,    w.p. 1/n^2
    α/β,    w.p. β/n - 1/n^2
    
    0,    w.p. 1 - β/n

Here α > 1 and β>0 are constants to be optimized later to minimize the ratio of  earned by  (note that since they are constants they don't scale with n, and therefore β >> 1/n and α < nβ; these are things we use in Lemma <ref> below).


 
In a n buyers setting, when the buyer valuations are drawn i.i.d. from the distribution F described in Example <ref>, the expected revenue  of Myerson's optimal auction approaches

    1+α-1/β(1-e^-β).




We compute the revenue as the expected ironed virtual surplus. To compute the latter, consider the revenue curve R(q)=qF^-1(1-q), where in this case F^-1(1-q) denotes the
maximum

price at which the probability of getting a sale (from a single buyer with valuation drawn from F) is at least q.  It can be computed that

    R(q)=qF^-1(1-q)=
    qn,    0<q≤ 1/n^2; 
    
    qα/β,    1/n^2<q≤β/n; 
    
    0,    β/n<q≤1.

Note that the revenue curve is not concave, because R(1/n^2)=1/n and R(β/n)=α/n>1/n, while R(1/n^2+) = (1/n^2+ϵ)α/β<1/n for sufficiently small >0.
The ironed revenue curve over q∈[1/n^2,β/n] is formed by joining the points (1/n^2,1/n) and (β/n,α/n). The slope of three line segments in the ironed revenue curve are the ironed virtual values corresponding to the three value realizations:

    
  * the slope of the line segment between (0,0) and (1/n^2,1/n) is n and that is the virtual value (which is equal to the ironed virtual value for this segment) of buyers with value n;
    
  * the slope of the line segment between (1/n^2,1/n) and (β/n,α/n) is α-1/β-1/n

and that is the ironed virtual valuation of buyers with value α/β.
    
  * buyers with value 0 have negative ironed virtual value and are irrelevant for revenue purposes.

 
The complete description of Myerson's optimal mechanism here is as follows:

    
  * any buyer who bids below α/β is never allocated, and always pays 0;
    
  * if there are no buyers with bid n or larger: allocate the item to a uniformly random buyer among all buyers with bids in [α/β,n) and charge him α/β;
    
  * if there is exactly one buyer with bid of n or larger, that buyer gets the item with probability 1, and he pays n - (n-α/β)· 1/(1 + num of buyers with bids in  [α/β,n)) which is basically the area to the left of the allocation curve of that buyer;
    
  * if there is more than one buyer with bid of n or larger, allocate the item to a uniformly random buyer among all buyers with bids in [n, ∞) and charge him n. 

The expected revenue of Myerson's optimal mechanism  equals the expected ironed virtual surplus, which can be computed as follows.
With probability 1-(1-1/n^2)^n, at least one buyer has virtual valuation n.
With probability (1-1/n^2)^n-(1-β/n)^n, no buyer has virtual valuation n but at least one buyer has ironed virtual valuation α-1/β - 1/n.
Therefore, the expected ironed virtual surplus, as the number of buyers approaches ∞, is

    lim_n→∞(n(1-(1-1/n^2)^n)+α-1/β - 1/n((1-1/n^2)^n-(1-β/n)^n))=1+α-1/β(1-e^-β),

completing the proof.


 
In a n buyers setting, when the buyer valuations are drawn i.i.d. from the distribution F described in Example <ref>, the expected revenue  of  as n→∞ is at most 

    1+α-lnα-1/β.




Consider any revenue-maximizing ESP auction.  Since the only possible non-zero valuations are n and α/β, it does not lose generality to assume that all reserve prices are set to either n or α/β.
Let z∈{0,1/n,2/n,…,1} denote the fraction of buyers whose reserve is set to n, so that the number of buyers with reserves n and α/β are zn and (1-z)n, respectively.

With probability 1-(1-1/n^2)^zn, at least one of the buyers with reserve n clears their reserve price, and the ESP auction earns the maximum possible revenue of n.
Otherwise, all zn buyers with reserve n are eliminated from the auction and we consider the other buyers.

For the other (1-z)n buyers with reserve α/β,
at least one of them will clear their reserve with probability 1-(1-β/n)^(1-z)n,
in which case the ESP auction is guaranteed to earn at least α/β.
In this case, there is also the possibility of earning the higher revenue of n, if at least two buyers report a valuation of n.
However, the probability of this event is at most n2 times the probability that a given pair of buyers both report n, by the union bound.
Therefore, the expected revenue collected from this event is at most nn2(1/n^2)^2=O(1/n), and can be ignored as n→∞.

Collecting the above terms, for any n and z∈{0,1/n,2/n,…,1}, the expected revenue of the corresponding ESP auction is

    n(1-(1-1/n^2)^zn)+α/β(1-1/n^2)^zn(1-(1-β/n)^(1-z)n) 
    ≤    n(1-(1-zn11/n^2))+α/β(1)(1-e^-β(1-z)) 
    
    =    z+α/β(1-e^-β(1-z))+O(1/n)

where we used the binomial theorem in the first inequality. The maximum of the concave function z+α/β(1-e^-β(1-z)) over z∈[0,1] is attained at z=1-lnα/β, and equals 1-lnα/β+α/β(1-1/α), completing the proof.




Let (n,) and (n,) denote respectively the revenue of the optimal auction (Myerson's auction) and the second price auction with personalized reserves in a single-item setting with n buyers whose values are drawn i.i.d from . Then:

    inf_n,(n,)/(n,)<0.778.




Consider Example <ref>.  By Lemmas <ref> and <ref>, the fraction of Myerson's optimal revenue earned by an ESP auction in this example is at most

    β+α-1-lnα/β+(α-1)(1-e^-β),

for any values of α>1 and β>0.  By numerically minimizing over such values of α and β, it can be checked that when α=2.91 and β=1.89, the value of (<ref>) is less than 0.778, completing the proof.




 §.§ Upper bound on ASP approximation factor


Consider the distribution from Example <ref> with α=β=n and let n→∞.
By Lemma <ref>, the optimal revenue of Myerson is 1+n-1/n(1-e^-n) which approaches 2 as n→∞.
On the other hand,  must set all of the reserves to either n or 1.
By the analysis in Lemma <ref>, this is upper-bounded by expression (<ref>) with z=0 or z=1, i.e. the revenue of  is at most

    max{1-e^-n+O(1/n),1+O(1/n)}

which approaches 1 as n→∞.  This completes the proof.

abbrvnat

