2026-07-21T19:59:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14603 2024-03-06T10:54:25Z ddc:004 open_access

Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions Braun, Alexander Buttkus, Matthias Kesselheim, Thomas Prophet Inequalities Monotone Hazard Rate Competitive Analysis Posted Prices Combinatorial Auctions Matching We consider the problem of posting prices for unit-demand buyers if all n buyers have identically distributed valuations drawn from a distribution with monotone hazard rate. We show that even with multiple items asymptotically optimal welfare can be guaranteed. Our main results apply to the case that either a buyer’s value for different items are independent or that they are perfectly correlated. We give mechanisms using dynamic prices that obtain a 1 - Θ (1/(log n))-fraction of the optimal social welfare in expectation. Furthermore, we devise mechanisms that only use static item prices and are 1 - Θ ((log log log n)/(log n))-competitive compared to the optimal social welfare. As we show, both guarantees are asymptotically optimal, even for a single item and exponential distributions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Braun and Matthias Buttkus and Thomas Kesselheim 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.22 urn:nbn:de:0030-drops-146038 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.22 eng https://creativecommons.org/licenses/by/4.0/legalcode