Institute for Software Research
School of Computer Science, Carnegie Mellon University
A Theory of Expressiveness in Mechanisms
Michael Benisch, Norman Sadeh, Tuomas Sandholm
Also appears as Computer Science
We also provide a way to determine an upper bound on the expected efficiency of any mechanism under its most efficient Nash equilibrium which, remarkably, depends only on the mechanism's expressiveness. We show that for any setting and any prior over agent preferences, the bound on efficiency of a mechanism designed optimally under a constraint on expressiveness increases strictly as more expressiveness is allowed (until the bound reaches full efficiency). In addition, we prove that a small increase in expressiveness can potentially lead to an arbitrarily large increase in the efficiency bound, depending on the prior.
We conclude with a study of a restricted class of mechanisms which we call channel based. The restriction is that these mechanisms take expressions of value through channels from agents to outcomes, and select the outcome with the largest sum. (Channel-based mechanisms subsume most combinatorial and multi-attribute auctions, any Vickrey-Clarke-Groves mechanism, etc.) In this class, a natural measure of expressiveness is the number of channels allowed (this generalizes the k-wise dependence measure of expressiveness traditionally used in the combinatorial auction literature). As a sanity check of our general domain-independent measure of expressiveness, we show that it appropriately relates to the number of channels when applied to channel-based mechanisms. This allows us to transfer all of our results regarding efficiency to this domain.