Combinatorial auctions without money

DOI10.1007/S00453-015-0105-8zbMATH Open1411.91254arXiv1310.0177OpenAlexW3138967961MaRDI QIDQ521808FDOQ521808

Authors: Dimitris Fotakis, Piotr Krysta, Carmine Ventre 

Publication date: 12 April 2017

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of $k$-minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.

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

Recommendations

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

zbMATH Keywords

algorithmic mechanism designapproximate mechanism design without moneycombinatorial auctionsmechanisms with verification

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

• Algorithmic Game Theory
• When are local incentive constraints sufficient?
• On the complexity of approximating \(k\)-set packing
• Algorithmic mechanism design
• Scheduling without payments
• Winner-imposing strategyproof mechanisms for multiple facility location games
• Optimal collusion-resistant mechanisms with verification
• Combinatorial auctions with verification are tractable
• Approximately optimal mechanism design via differential privacy
• Mechanism design. A linear programming approach.
• Truthful approximation mechanisms for restricted combinatorial auctions
• Approximation techniques for utilitarian mechanism design
• Truth revelation in approximately efficient combinatorial auctions
• Mechanism design with weaker incentive compatibility constraints
• Partially Verifiable Information and Mechanism Design
• Frugality in path auctions
• Utilitarian mechanism design for multiobjective optimization
• (Incremental) priority algorithms
• Bundling equilibrium in combinatorial auctions
• Title not available (Why is that?)
• Truthfulness flooded domains and the power of verification for mechanism design
• Online mechanism design (randomized rounding on the fly)
• On the limitations of greedy mechanism design for truthful combinatorial auctions
• Two Randomized Mechanisms for Combinatorial Auctions
• Global Incentive Constraints in Auction Design
• Price discrimination through communication
• Mathematical Foundations of Computer Science 2005
• Collusion-resistant mechanisms with verification yielding optimal solutions
• Implementation with partial verification

Cited In (8)

• On the limitations of greedy mechanism design for truthful combinatorial auctions
• Efficient money burning in general domains
• Efficient money burning in general domains
• Mechanisms with monitoring for truthful RAM allocation
• Approximation guarantee of OSP mechanisms: the case of machine scheduling and facility location
• The power of verification for greedy mechanism design
• Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
• From monetary to nonmonetary mechanism design via artificial currencies

This page was built for publication: Combinatorial auctions without money

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