Power of Posted-price Mechanisms for Prophet Inequalities

We study the power of posted pricing mechanisms for Bayesian online optimization problems subject to combinatorial feasibility constraints. When the objective is to maximize social welfare, the problem is widely studied in the literature on prophet inequalities. While most (though not all) existing algorithms for prophet inequalities are implemented using a pricing mechanism, whether or not this can be done in general is unknown, and was formally left as an open question by Dütting, Feldman, Kesselheim, and Lucier (FOCS 2017, SICOMP 2020). Understanding the power and limitations of posted prices is important from a mechanism design perspective because any posted price mechanism is truthful, and is also interesting in its own right as it can guide future research on prophet inequalities.

We show that any prophet inequality has an implementation using a posted price mechanism, thereby resolving the open question of Dütting et al. Given an algorithm for Bayesian online optimization, we show that it can be transformed, in a black-box manner, to a posted price algorithm that has the same or higher expected social welfare and preserves the distribution over the assigned outcomes. We further show how to implement our reduction efficiently under standard assumptions using access to a sampling oracle. As an immediate consequence, we obtain improved pricing-based prophet inequalities for maximum weight matching, resolving an open problem of Ezra, Feldman, Gravin and Tang (EC 2020, MOR 2022). Correa and Cristi (STOC 2023) proved recently an existence of prophet inequality with constant approximation ratio for online social welfare maximizing combinatorial auctions with subadditive valuations. They left as an open problem to provide a posted pricing based implementation of their algorithm. Our technique resolves this question in affirmative as well.

This paper was published at SODA 2024 and it is joint work with Kiarash Banihashem, Mohammad Taghi Hajiaghayi, Dariusz Kowalski and Jan Olkowski.