A key trend in the world–especially in electronic commerce–is a demand for higher levels of expressiveness in the mechanisms that mediate interactions, such as the allocation of resources, matching of peers, and elicitation of opinions from large and diverse communities. Intuitively, one would think that this increase in expressiveness would lead to more efficient mechanisms (e.g., due to better matching of supply and demand). However, until now we have lacked a general way of characterizing the expressiveness of these mechanisms, analyzing how it impacts the actions taken by rational agents–and ultimately the outcome of the mechanism. In this technical report we introduce a general model of expressiveness for mechanisms. Our model is based on a new measure which we refer to as the maximum impact dimension. The measure captures the number of different ways that an agent can impact the outcome of a mechanism. We proceed to uncover a fundamental connection between this measure and the concept of shattering from computational learning theory.

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.

42 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]