Knowledge Benchmarks in Adversarial Mechanism Design (Part I) and Implementation in Surviving Strategies (Part I)

We put forward new benchmarks and solution concepts for Adversarial Mechanism Design, as defined by [MV07.a], and we exemplify them in the case of truly combinatorial auctions.We benchmark the combined performance (the sum of the auction's effciency and revenue)of a truly combinatorial auction against a very relevant but private knowledge of the players: essentially, the maximum revenue that the best informed player could guarantee if he were the seller. (I.e., by offering each other player a subset of the goods for a take-it-or-leave-it price.) We achieve this natural benchmark within a factor of 2, by means of a new and probabilisticauction mechanism, in KNOWLINGLY SURVIVING STRATEGIES. That is, the above performance of our mechanism is guaranteed in any rational play, independent of any possible beliefs of the players. Indeed, our performance guarantee holds for any possible choice of strategies, so long as each player chooses a strategy among those surviving iterated elimination of knowingly dominated strategies.Our mechanism is extremely robust. Namely, its performance guarantees hold even if all but one of the players collude (together or in separate groups) in any possible but reasonable way. Essentially, the only restriction for the collective utility function of a collusive subset S of the players is the following: the collective utility increases when one member of S is allocated asubset of the goods "individually better" for him and/or his "individual price" is smaller, while the allocations and prices of all other members of S stay the same.Our results improve on the yet unpublished ones of [MV07.b]. The second part of this paper, dealing with a more aggressive benchmark (essentially, the maximum welfare privately known to the players) is forthcoming.