2024/02/19 by Kira Goldner, Goldner, Kira, Taylor Lundy +1 · 1 voice
Computer Science · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Healthcare Policy and Management #cs.GT
paper · pdf · doi:10.48550/arxiv.2402.12340
openalex publication_date 2024/02/19 · arxiv published 2024/02/19 · openalex created_date 2024/02/21 · arxiv updated 2025/02/15 · openalex updated_date 2026/07/28
We initiate the study of multidimensional Bayesian utility maximization, focusing on the unit-demand setting where values are i.i.d. across both items and buyers. The seminal result of Hartline and Roughgarden '08 studies simple, information-robust mechanisms that maximize utility for n i.i.d. agents and m identical items via an approximation to social welfare as an upper bound, and they prove this gap between optimal utility and social welfare is Θ(1+logn/m) in this setting. We extend these results to the multidimensional setting. To do so, we develop simple, prior-independent, approximately-optimal mechanisms, targeting the simplest benchmark of optimal welfare. We give a (1- 1/e)-approximation when there are more items than buyers, and a Θ(logn/m)-approximation when there are more buyers than items, and we prove that this bound is tight in both n and m by reducing the i.i.d. unit-demand setting to the identical items setting. Finally, we include an extensive discussion section on why Bayesian utility maximization is a promising research direction. In particular, we characterize complexities in this setting that defy our intuition from the welfare and revenue literature, and motivate why coming up with a better benchmark than welfare is a hard problem itself.