Mechanism Design for Single-Value Domains

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 20

Auctions and Market-Based Systems

n ``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 truthfulnessin this case, demonstrating that the difference is subtle and surprising.