Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue br

• 成果类型: Article
• 署名作者: Eden, Alon; Feldman, Michal; Fiat, Amos; Goldner, Kira; Karlin, Anna R.
• 署名单位: Hebrew University of Jerusalem; Tel Aviv University; Boston University; University of Washington; University of Washington Seattle
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• 发表日期: 2024
• 页码: 653-674
• 关键词: mean-field games

摘要

. We study combinatorial auctions with interdependent valuations, where each agent i has a private signal si that captures her private information and the valuation func-tion of every agent depends on the entire signal profile, s(s1,:::,sn). The literature in eco-nomics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer sci-ence literature provides approximation results for simple single-parameter settings (mostly single-item auctions or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed single crossing (or variants thereof). We consider the class of submodular over signals (SOS) valuations (without imposing any single crossing-type assumption) and provide the first welfare approximation guaran-tees for multidimensional combinatorial auctions achieved by universally ex post incentive- compatible, individually rational mechanisms. Our main results are (i) four approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations; (ii) four approximation for any combinatorial auction with multidimen-sional signals and separable-SOS valuations; and (iii) (k+3) and (2log(k)+4) approximation for any combinatorial auction with single-dimensional signals, with k-sized signal space, for SOS and strong-SOS valuations, respectively. All of our results extend to a parameterized version of SOS, d-approximate SOS, while losing a factor that depends on d