Abstract: A Lookahead Auction (LA), introduced by Ronen, is an auction format for the sale of a single item among multiple buyers, which is considered simpler and more fair than the optimal auction. Indeed, it anonymously selects a provisional winner by a symmetric ascending-price process, and only then uses a personalized posted price. A LA auction extracts at least 1/2 of the optimal revenue, even under a correlated value distribution. This bound is tight, even for 2 buyers with independent values. We introduce a natural extension of LA, called lookahead with pooling (LAP). A LAP auction proceeds as LA, with one difference: it allows the seller to pool together a range of values during the ascending-price stage, and treat them the same; thus, it preserves the simplicity and fairness of LA. Our main result is that this simple pooling operation improves the revenue guarantees for independent buyers from 1/2 to 4/7 of the optimal revenue. We also give a complementary negative result, showing that for arbitrary correlated priors LAP cannot do better than 1/2 approximation.
Our main result is an improved bound on the approximation ratio of lookahead auction with pooling (LAP). The following is valid: Theorem. For any setting with an arbitrary number of independent bidders, LAP achieves a \(\frac{4}{7}\)-approximation to the optimal revenue. In Section 4, the authors construct a correlated distribution with the following unnatural cryptographic feature: the seller can precisely recover the value of the lower bidder from the bid of the higher bidder, while the lower bid reveals almost no useful information about the top value. The following proposition is valid: Theorem. No LAP mechanism achieves better than \(\frac{1}{2} +o(1)\) approximation to the optimal revenue for the above instance of correlated distribution. For the entire collection see [Zbl 1515.91014].
