### Single-value combinatorial auctions and algorithmic implementation in undominated strategiesSingle-value combinatorial auctions and algorithmic implementation in undominated strategies

Access Restriction
Subscribed

 Author Babaioff, Moshe ♦ Lavi, Ron ♦ Pavlov, Elan Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Combinatorial auctions ♦ Incentives ♦ Mechanism design ♦ Undominated strategies 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 $\textit{algorithm}$ to a dominant-strategy ascending $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-02-03 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 1 Page Count 32 Starting Page 1 Ending Page 32

#### Open content in new tab

Source: ACM Digital Library