Combinatorial Auctions without Money
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. 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. In this setting we characterize the class of truthful mechanisms and give a host of upper and lower bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms. Our results provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 2014
- Accession Number
- ADA601742
Entities
People
- Carmine Ventre
- Dimitris Fotakis
- Piotr Krysta