We study revenue maximization through sequential posted price mechanisms (SPMs) in single-dimensional settings with n buyers, and independent but not necessarily identical value distributions. We construct our SPMs by considering two simple pricing schemes: one that imitates Myerson's mechanism via taxation principle, and the other that posts a uniform price. We design a factor revealing LP that crisply captures the approximation factor of this SPM. In the H-units setting, our SPM yields the first improvement in approximation over the correlation-gap-based approximation factor from over eight years ago (Yan 2011). In the position auction setting, our SPM yields the first higher-than 1-1 e approximation factor. In the 1-unit setting, our SPM yields better than the current best known approximation factor for small values of the number of buyers n. Our results on SPMs immediately imply improved performance guarantees for the equivalent free-order prophet inequality problem. In the recent surge of results that show an improvement over 1-1 e for SPMs, ours is the only technique that generalizes beyond the 1-unit setting, and yields the first improvement over long established approximation factors in several settings.
false study the question of approximating the optimal mechanism's revenue via Vickrey auction with personalized reserve prices, and show that for regular distributions, the second price auction with the so-called monopoly reserve prices yield a @math -approximation for regular distributions, and that for irregular distributions no constant factor approximation is possible with the monopoly reserves. study the question of computing the optimal personalized reserve prices in a correlated distribution setting, and show that the problem is NP-hard. The hardness status of this problem is unknown for independent distributions. show that this problem is APX-hard for correlated distributions and give a @math -approximation. Second price auctions with lazy personalized reserve prices are incomparable to second price auctions with eager reserve prices for general correlated distributions, but are within a factor @math of each other @cite_22 . However, when the distributions are independent, or when the buyers are symmetric, show that the optimal eager auction dominates the revenue of the optimal lazy auction.
@cite_22
203000141
The VCG mechanism is the gold standard for combinatorial auctions (CAs), and it maximizes social welfare. In contrast, the revenue-maximizing (aka optimal) CA is unknown, and designing one is NP-hard. Therefore, research on optimal CAs has progressed into special settings. Notably, Levin [1997] derived the optimal CA for complements when each agent's private type is one-dimensional. (This does not fall inside the well-studied "single-parameter environment".) We introduce a new research avenue for increasing revenue where we poke holes in the allocation space--based on the bids--and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduce a new form of "reserve pricing" into CAs. We show that Levin's optimal revenue can be 2-approximated by using "monopoly reserve prices" to curtail the allocation set, followed by welfare-maximizing allocation and Levin's payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocation-monotonic mechanism equals the expected virtual valuation; this generalizes Myerson's lemma [1981] from the single-parameter environment. Our mechanism is close to the gold standard and thus easier to adopt than Levin's. It also requires less information about the prior over the bidders' types, and is always more efficient. Finally, we show that the optimal revenue can be 6- approximated even if the "reserve pricing" is required to be symmetric across bidders.