Single-parameter combinatorial auctions with partially public valuations

DOI10.1007/978-3-642-16170-4_21MaRDI QIDQ3162522zbMATH OpenOpenAlexFDO

Authors Gagan Goel, C. Karande, Lei Wang

Publication date 19 October 2010

Published in Algorithmic Game Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We consider the problem of designing truthful auctions, when the bidders' valuations have a public and a private component. In particular, we consider combinatorial auctions where the valuation of an agent $i$ for a set $S$ of items can be expressed as $v_{i}f(S)$, where $v_i$ is a private single parameter of the agent, and the function $f$ is publicly known. Our motivation behind studying this problem is two-fold: (a) Such valuation functions arise naturally in the case of ad-slots in broadcast media such as Television and Radio. For an ad shown in a set $S$ of ad-slots, $f(S)$ is, say, the number of {em unique} viewers reached by the ad, and $v_i$ is the valuation per-unique-viewer. (b) From a theoretical point of view, this factorization of the valuation function simplifies the bidding language, and renders the combinatorial auction more amenable to better approximation factors. We present a general technique, based on maximal-in-range mechanisms, that converts any $alpha$-approximation non-truthful algorithm ($alphaleq1$) for this problem into $Omega(fracalphalogn)$ and $Omega(alpha)$-approximate truthful mechanisms which run in polynomial time and quasi-polynomial time, respectively.

Recommendations

• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
• scientific article; zbMATH DE number 2079341
• Truthful approximation mechanisms for restricted combinatorial auctions
• Truthful randomized mechanisms for combinatorial auctions
• Truthful randomized mechanisms for combinatorial auctions

Cites work

• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Bayesian algorithmic mechanism design
• Bundling equilibrium in combinatorial auctions
• scientific article; zbMATH DE number 2079341 (Why is no real title available?)
• Inapproximability for VCG-based combinatorial auctions
• Limitations of VCG-based mechanisms
• Optimal approximation for the submodular welfare problem in the value oracle model
• Single-parameter combinatorial auctions with partially public valuations
• Single-value combinatorial auctions and algorithmic implementation in undominated strategies
• Truth revelation in approximately efficient combinatorial auctions
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Truthful approximation mechanisms for restricted combinatorial auctions

Cited in

(5)

• Price of fairness for allocating a bounded resource
• On black-box transformations in downward-closed environments
• Black-box reductions in mechanism design
• Single-parameter combinatorial auctions with partially public valuations
• Combinatorial auctions with conflict-based externalities

This page was built for publication: Single-parameter combinatorial auctions with partially public valuations

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