We study the design of mechanisms in combinatorial auction domains. We focus on settings where the auction is repeated, motivated by auctions for licenses or advertising space. We consider models of agent behaviour in which they either apply common learning techniques to minimize the regret of their bidding strategies, or apply short-sighted best-response strategies. We ask: when can a black-box approximation algorithm for the base auction problem be converted into a mechanism that approximately preserves the original algorithm's approximation factor on average over many iterations? We present a general reduction for a broad class of algorithms when agents minimize external regret. We also present a new mechanism for the combinatorial auction problem that attains an @math approximation on average when agents apply best-response dynamics.
@cite_10 study implementation of algorithms in undominated strategies, which is a relaxation of the dominant strategy truthfulness concept. They focus on a variant of the CA problem in which agents are assumed to have single-value'' valuations, and present a mechanism to implement such auctions in a multi-round fashion. By comparison, mechanisms in our proposed model solve each instance of an auction in a one-shot manner, and our solution concept assumes that the auction is repeated multiple times.
@cite_10
2142270691
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 PeNP). This mechanism is an algorithmic implementation in undominated strategies, a notion that we define and justify, and is of independent interest.