Single-value combinatorial auctions and implementation in undominated strategies

Single-value Combinatorial Auctions (CA) are a generalization of single-minded CA: eachplayer desires any one of several different bundles, but has the same value for each of them. Our main result provides the first polynomial time strategic approximation mechanism for this case,using a new notion of "algorithmic implementation in undominated strategies". We show that this general notion, which is an alternative to the now-standard truthfulness notion, capturesalmost all the advantages of the truthfulness notion. By using it, we achieve an approximation to the social welfare which is close to the best possible in polynomial time (unless ZPP=NP).In addition, we give two general techniques to overcome strategic behavior in two special cases: (1) For the case where player values are the only private information, we provide a deterministictechnique to convert algorithms to truthful ascending mechanisms that almost preserve the original approximation ratio, and (2) For the case where players are single minded, we providea deterministic technique to convert some truthful mechanisms for the case that only the values are private, to mechanisms in undominated strategies for the case that both the bundles andvalues are private. These mechanisms preserve the original approximation ratio.