Combinatorial auctions with conflict-based externalities

DOI10.1007/978-3-662-48995-6_17MaRDI QIDQ3460791zbMATH OpenOpenAlexFDO

Authors Yun Kuen Cheung, Martin Hoefer, Martin Starnberger, Monika R. Henzinger

Publication date 8 January 2016

Published in Web and Internet Economics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1509.09147

zbMATH Keywords

combinatorial auctionsexternalitiesgraph-theoretic modelssocial welfare maximization

Mathematics Subject Classification ID

Applications of graph theory (05C90) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder's valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors' ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree $Delta$. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on $Delta$. For CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful $alpha$-approximation mechanism for conflict-free valuations and yields an $mathcalO(alphaDelta)$-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is $mathcalO((DeltaloglogDelta)/logDelta)$. The ratios are almost optimal given existing hardness results. For the prominent application of adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio $o(Delta)$ when the number of items is only logarithmic in the number of bidders.

Recommendations

• Approximation algorithms for combinatorial auctions with complement-free bidders
• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
• scientific article; zbMATH DE number 2079341
• Single-parameter combinatorial auctions with partially public valuations
• On the limitations of greedy mechanism design for truthful combinatorial auctions

Cites work

• Approximation resistance from pairwise independent subgroups
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combinatorial auctions with conflict-based externalities
• Computing optimal outcomes under an expressive representation of settings with externalities
• scientific article; zbMATH DE number 1182757 (Why is no real title available?)
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Multidimensional mechanism design for auctions with externalities
• Pairwise Independence and Derandomization
• The communication requirements of efficient allocations and supporting prices
• The submodular welfare problem with demand queries
• Truthful randomized mechanisms for combinatorial auctions

Cited in

(1)

• Combinatorial auctions with conflict-based externalities

This page was built for publication: Combinatorial auctions with conflict-based externalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460791)