Accession Number:

ADA601742

Title:

Combinatorial Auctions without Money

Descriptive Note:

Conference paper

Corporate Author:

NATIONAL TECHNICAL UNIV ATHENS (GREECE)

Report Date:

2014-05-01

Pagination or Media Count:

9.0

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.

Subject Categories:

  • Economics and Cost Analysis
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE