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.
@cite_22: We study the question of setting and testing reserve prices in single item auctions when the bidders are not identical. At a high level, there are two generalizations of the standard second price auction: in the lazy version we first determine the winner, and then apply reserve prices; in the eager version we first discard the bidders not meeting their reserves, and then determine the winner among the rest. We show that the two versions have dramatically different properties: lazy reserves are easy to optimize, and A B test in production, whereas eager reserves always lead to higher welfare, but their optimization is NP-complete, and naive A B testing will lead to incorrect conclusions. Despite their different characteristics, we show that the overall revenue for the two scenarios is always within a factor of 2 of each other, even in the presence of correlated bids. Moreover, we prove that the eager auction dominates the lazy auction on revenue whenever the bidders are independent or symmetric. We complement our theoretical results with simulations on real world data that show that even suboptimally set eager reserve prices are preferred from a revenue standpoint.
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.