Most markets we participate in every day work via posted prices. Usually, items have prices and customers choose the (set of) items they like best. From the perspective of combinatorial optimization, allocating items is actually a complex problem. For example, if one wants to maximize social welfare, that is, overall happiness, solving only the allocation problem is already hard. A central question in our research is to what extent prices can yield an (approximately) optimal solution to such optimization problems.

We would like to understand whether it is necessary that prices have complicated structures or not. For example, is it enough to set item prices or do we have to give discounts on greater bundles? Does every potential buyer have to pay the same prices or can we gain a lot from offering different prices or price menus to depending on our prior information regarding the buyers. These questions play and important role also in the context of maximizing revenue.

We often assume that customers’ preferences are not known beforehand. Instead, they are drawn from known probability distributions. A useful tool to understand these settings are prophet inequalities. Originating from optimal-stopping theory, prophet inequalities quantify the loss of decisions based on only knowing probability distributions versus the optimal respective decisions in hindsight. Part of our work is to extend these results to combinatorial settings.

• Paul Dütting, Thomas Kesselheim, Brendan Lucier: An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions. FOCS 2020: 306-317
• Paul Dütting, Thomas Kesselheim: Posted Pricing and Prophet Inequalities with Inaccurate Priors. EC 2019: 111-129
• Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, Sahil Singla: Prophet Secretary for Combinatorial Auctions and Matroids. SODA 2018: 700-714
• Paul Duetting, Michal Feldman, Thomas Kesselheim, Brendan Lucier: Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. FOCS 2017: 540-551

Thomas Kesselheim