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_21: Abstract In this work we prove that designing PPMs is equivalent to finding stopping rules for prophets. This extends the connection that any prophet type inequality can be turned into a PPM with the same approximation guarantee ( 2007; 2010). Our reduction is robust under multiple settings including matroid feasibility constraints, or different arrival orderings. One fundamental observation implied by this result is that designing PPMs in general is equally hard from an approximation perspective to designing PPMs when the valuations are regular.
@cite_6: In the Prophet Secretary problem, samples from a known set of probability distributions arrive one by one in a uniformly random order, and an algorithm must irrevocably pick one of the samples as soon as it arrives. The goal is to maximize the expected value of the sample picked relative to the expected maximum of the distributions. This is one of the most simple and fundamental problems in online decision making that models the process selling one item to a sequence of costumers. For a closely related problem called the Prophet Inequality where the order of the random variables is adversarial, it is known that one can achieve in expectation 1 2 of the expected maximum, and no better ratio is possible. For the Prophet Secretary problem, that is, when the variables arrive in a random order, (2015) showed that one can actually get 1-1 e of the maximum. The 1-1 e bound was recently extended to more general settings by (2018). Given these results, one might be tempted to believe that 1-1 e is the correct bound. We show that this is not the case by providing an algorithm for the Prophet Secretary problem that beats the 1-1 e bound and achieves 1-1 e+1 400 times the expected maximum. We also prove a hardness result on the performance of algorithms under a natural restriction which we call deterministic distribution-insensitivity.
In another variation of prophet inequalities, the gambler can pick the random variables in her desired order. This variation is known as . We first note, as recently shown by @cite_21 , that any approximation for SPMs implies the same approximation for free-order prophets. The bound on the best possible approximation by also holds for this setting. give a @math approximation for the SPM problem. Recall that under SPMs, the seller approaches the buyers in decreasing order of their prices. This bound of @math was recently surpassed by @cite_6 to @math , and their bound also extends to , in which the random variables arrive in a uniformly random order. Our bound of @math for SPMs, which implies the same bound for free-order prophets by the result of , is the best known bound for free-order prophets so far. More precisely, just like for SPMs and ESP auctions, ours is the first paper to go beyond the @math bound for every @math in the free-order prophets setting.