Using Expressiveness to Improve the Economic Efficiency of Social Mechanisms

Mechanisms are present everywhere in both business and social contexts. They govern the interactions people have with businesses, governments, and each other. One emerging trend over the past decade is a demand for higher levels of expressiveness in mechanisms that mediate interactions such as the allocation of resources, matching of peers, and elicitation of opinions. A driving force behind this trend is that greater expressiveness begets better matches, or greater efficiency of the outcomes. Yet, expressiveness does not come for free; it burdens users to specify more preference information. Today's mechanisms have relied on empirical tweaking to determine how to deal with this and related tradeoffs. In this thesis, we propose to establish the foundations of expressiveness in mechanisms and its relationship to their efficiency, as well as a methodology for determining the most effective forms of expressiveness for a particular setting.

In one stream of research, we propose a domain independent theory of expressiveness for mechanisms. We show that the best-case efficiency of an optimally designed mechanism increases strictly as we allow more expressiveness. We also show that in some cases a small increase in expressiveness can yield an arbitrarily large increase in a mechanism's best-case efficiency.

In a second stream of research, we apply our theory to a variety of mechanisms. We study channel-based mechanisms, which subsume most combinatorial auctions, multi-attribute mechanisms, and the Vickrey-Clarke-Groves scheme. When applied to this class, our general results yield the interesting implication that any (channel-based) multi-item auction that does not allow rich combinatorial bids can be arbitrarily inefficient-unless agents have no private information. We also examine the cost of inexpressiveness in advertisement auctions. Using simulated advertiser preferences, we find that, in some settings, slightly increasing the expressiveness of existing ad auction mechanisms leads to significant improvements in their best-case efficiency.

In conducting these two streams of research, we have begun to develop a methodology for understanding how the expressiveness of a mechanism impacts its outcome. In addition to the above (already completed) research, we discuss how the theory and methodology can be further developed and used to study two additional domains. The first is the domain of privacy preference elicitation. We propose to conduct at least one human subjects study to determine which forms of expressiveness are most appropriate in this domain. The second is the domain catalog pricing. We propose to develop algorithms which can be used to make traditional catalog pricing mechanisms more expressive by adding bundle offerings. Our algorithms will automatically identify promising bundles of items and suggest prices for selling those bundles.

Download PDF of proposal [1.2 Mb]       Download PDF of proposal slides [6.5 Mb]