Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue

Alon Eden (), Michal Feldman (), Amos Fiat (), Kira Goldner () and Anna R. Karlin ()
Additional contact information
Alon Eden: School of Computer Science and Engineering, Hebrew University, 9190401 Jerusalem, Israel
Michal Feldman: School of Computer Science, Tel Aviv University, 6997801 Tel Aviv, Israel
Amos Fiat: School of Computer Science, Tel Aviv University, 6997801 Tel Aviv, Israel
Kira Goldner: Faculty of Computing & Data Sciences, Boston University, Boston, Massachusetts 02215
Anna R. Karlin: Paul G. Allen School of Computer Science and Engineering, University of Washington, Seattle, Washington 98195

Mathematics of Operations Research, 2024, vol. 49, issue 2, 653-674

Abstract: We study combinatorial auctions with interdependent valuations, where each agent i has a private signal s i that captures her private information and the valuation function of every agent depends on the entire signal profile, s = ( s 1 , … , s n ) . The literature in economics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer science 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 guarantees 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 multidimensional signals and separable -SOS valuations; and (iii) ( k + 3) and (2 log( 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 .

Keywords: Primary: 91B03; 91A68; 91B26; 91B44; mechanism design; interdependent valuations; combinatorial auctions; algorithmic game theory (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.1371 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:2:p:653-674

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().