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 Moved these two paragraphs here. Todo Finally, we compare our result with the results of @cite_6 . Though they have a worse factor, their posted price result is applicable for a more general setting: i.e., applicable both for a fixed-seller-chosen ordering of buyers, and random ordering of buyers, whereas our posted pricing result is applicable only for a fixed-seller-chosen-ordering of buyers (namely, descending order of prices). While the random order setting is more general, note that a random order model for posted pricing does not give any additional benefit over the fixed-ordering when it comes to approximation for second price auctions with eager reserves.
@cite_6
1656659859
We study prior-free revenue maximization for a seller with unlimited supply of n item types facing m myopic buyers present for k < log n days. We show that a certain randomized schedule of posted prices has an approximation factor of O(log m+log n k). This algorithm relies on buyer valuations having hereditary maximizers, a novel natural property satisfied for example by gross substitutes valuations. We obtain a matching lower bound with multi-unit valuations. In light of existing results [2], k days can thus improve the approximation by a Θ(k) factor. We also provide a posted price schedule with the same factor for positive affine allocative externalities, despite an increase in the optimal revenue.