Mechanism Design for Single-Value Domains

Abstract

In “Single-Value domains”, each agent has the same private value for all desired outcomes. We formalize this notion and give new examples for such domains, including a “SAT do-main ” and a “single-value combinatorial auctions ” domain. We study two informational models: where the set of de-sired outcomes is public information (the “known ” case), and where it is private information (the “unknown ” case). Un-der the “known ” assumption, we present several truthful ap-proximation mechanisms. Additionally, we suggest a general technique to convert any bitonic approximation algorithm for an unweighted domain (where agent values are either zero or one) to a truthful mechanism, with only a small approxima-tion loss. In contrast, we show that even positive results from the “unknown single minded combinatorial auctions ” litera-ture fail to extend to the “unknown ” single-value case. We give a characterization of truthfulness in this case, demon-strating that the difference is subtle and surprising.