Mechanism Design for Single-Value Domains

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 domain” and a “single-value combinatorial auctions” domain. We study two informational models: where the set of desired outcomes is public information (the “known” case), and where it is private information (the “unknown” case). Under the “known” assumption, we present several truthful approximation 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 approximation loss. In contrast, we show that even positive results from the “unknown single minded combinatorial auctions” literature fail to extend to the “unknown” single-value case. We give a characterization of truthfulness in this case, demonstrating that the difference is subtle and surprising.

Authors

• Moshe Babaioff

Keywords

No keywords are indexed for this paper.