Power of Posted-price Mechanisms for Prophet Inequalities

Banihashem, Kiarash, Hajiaghayi, MohammadTaghi, Kowalski, Dariusz R, Krysta, Piotr and Olkowski, Jan (2024) Power of Posted-price Mechanisms for Prophet Inequalities. In: 35th ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), 2024-1-7 - 2024-1-10.

Text Prophet_Pricing_Accepted.pdf - Unspecified Download (265kB) | Preview

Abstract

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.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	11 Dec 2023 09:37
Last Modified:	10 Apr 2024 13:24
DOI:	10.1137/1.9781611977912.163
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3177238