Author
Listed:
- 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)
AbstractWe 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 .
Suggested Citation
Alon Eden & Michal Feldman & Amos Fiat & Kira Goldner & Anna R. Karlin, 2024.
"Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue,"
Mathematics of Operations Research, INFORMS, vol. 49(2), pages 653-674, May.
Handle:
RePEc:inm:ormoor:v:49:y:2024:i:2:p:653-674
DOI: 10.1287/moor.2023.1371
Download full text from publisher
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:49:y:2024:i:2:p:653-674. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.