Understanding Posted Prices via Prophet Inequalities

• Applicant: Professor Dr. Thomas Kesselheim
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 437739576

Prophet inequalities provide a framework for probabilistic analyses of online algorithms and online mechanisms. They originate in optimal-stopping theory, where the task is to stop a sequence of numbers at its highest value. In advance, an algorithm knows the probability distributions the numbers are drawn from. Its performance is compared to the optimal choice in hindsight, that is, what a hypothetical prophet who knows the future would have done.In recent years, numerous extensions to combinatorial settings such as matroids and combinatorial auctions have been introduced. One reason for recent interest is that such algorithm have a particularly convincing application as posted-prices mechanisms. In the case of a combinatorial auction, items are assigned fixed prices, buyers arrive one by one and each buyer is assigned the bundle that maximizes their utility from all remaining items. In the context of algorithmic mechanism design, they correspond to simple, suboptimal, truthful mechanisms with provable approximation guarantees.Guarantees in prior work are inherently pessimistic. The usual assumption is that probability distributions can be arbitrary. Upper and lower bounds match in many cases only because of corner cases. For this reason, in this project, we seek to understand the effects of different choices of distributions. This gives us not only the chance of better guarantees and a more fine-grained pictured but also the opportunity to understand why prophet inequalities work the first place. For example, in the case of general distributions, the simplest cases turns out to be the one with worst guarantees. To this point, it is not clear whether this is an artifact of worst-case analysis or a general pattern. In more detail, we will first turn our attention to more restricted classes of distributions. We focus on cases that are well-motivated and established in economic contexts. For these, we will be able to derive stronger guarantees. Besides obtaining knowledge about particular classes of distributions, a related goal is to characterize distributions that allow better guarantees. Finally, we will consider settings of reduced knowledge of the distributions, such as for example sample access. Distinguishing between distributions will allow us to develop a more fine-grained picture here as well.

• DFG Programme: Research Grants