Welfare maximization via posted prices

Posted price mechanisms are simple, straightforward, and strategy proof. We study two scenarios of combinatorial markets where sequential posted price mechanisms achieve optimal or nearly optimal welfare. The first scenario is matching markets with full information, where optimal welfare is obtained. The second is markets with submodular (and XOS) valuations with Bayesian information, where half of the optimal welfare is obtained. We distinguish between static and dynamic pricing, and present various extensions of the above findings. Finally, we mention surprising relations between price of anarchy results and posted price mechanisms.

Based on joint works with Vincent Cohen-Addad, Alon Eden and Amos Fiat (2016), with Nick Gravin and Brendan Lucier (2015) and with Paul Duetting, Thomas Kesselheim, and Brendan Lucier (2016).