Single-value combinatorial auctions and algorithmic implementation in undominated strategies
Authors:
Open Access
- 1 January 2009
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 56 (1) , 1-32
Abstract
In this article, we are interested in general techniques for designing mechanisms that approximate the social welfare in the presence of selfish rational behavior. We demonstrate our results in the setting of Combinatorial Auctions (CA). Our first result is a general deterministic technique to decouple the algorithmic allocation problem from the strategic aspects, by a procedure that converts any algorithm to a dominant-strategy ascending mechanism . This technique works for any single value domain, in which each agent has the same value for each desired outcome, and this value is the only private information. In particular, for “single-value CAs”, where each player desires any one of several different bundles but has the same value for each of them, our technique converts any approximation algorithm to a dominant strategy mechanism that almost preserves the original approximation ratio. Our second result provides the first computationally efficient deterministic mechanism for the case of single-value multi-minded bidders (with private value and private desired bundles). The mechanism achieves an approximation to the social welfare which is close to the best possible in polynomial time (unless P=NP). This mechanism is an algorithmic implementation in undominated strategies , a notion that we define and justify, and is of independent interest.Keywords
This publication has 26 references indexed in Scilit:
- Combinatorial Auctions2007
- The communication requirements of efficient allocations and supporting pricesJournal of Economic Theory, 2006
- Iterative Combinatorial Auctions2005
- Bundling equilibrium in combinatorial auctionsGames and Economic Behavior, 2004
- Truth revelation in approximately efficient combinatorial auctionsJournal of the ACM, 2002
- Opportunity Cost Algorithms for Combinatorial Auctions2002
- Algorithmic Mechanism DesignGames and Economic Behavior, 2001
- Incentives in TeamsEconometrica, 1973
- Multipart pricing of public goodsPublic Choice, 1971
- COUNTERSPECULATION, AUCTIONS, AND COMPETITIVE SEALED TENDERSThe Journal of Finance, 1961