Mechanisms for facilitating people's interactions with businesses, their governments, and each other are ubiquitous in today's society. One emerging trend over the past decade, along with increasing computational power and bandwidth, has been a demand for higher levels of expressiveness in such mechanisms. This trend has already manifested itself in combinatorial auctions and generalizations thereof. It is also reflected in the richness of preference expressions allowed by businesses as diverse as consumer sites, like Amazon and Netflix, and services like Google's AdSense.

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 establish the foundation 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 develop a domain independent theory of expressiveness for mechanisms. We show that the efficiency of an optimally designed mechanism in equilibrium increases strictly as more expressiveness is allowed. We also show that in some cases a small increase in expressiveness can yield an arbitrarily large increase in a mechanism's efficiency.

In a second stream of research, we operationalize our theory by applying it to a variety of domains. We first study a general class of mechanisms, called channel-based mechanisms, which subsume most combinatorial auctions. We show that without full expressiveness such mechanisms can be arbitrarily inefficient. Next, we focus on the domain of advertisement markets, where we show that the standard mechanism used for sponsored search is inefficient in the practical setting where some advertisers prefer lower-traffic positions (but this inefficiency can be largely eliminated by making the mechanism only slightly more expressive). We also consider the domain of privacy preferences for information sharing with oneās social network, where we conduct an extensive human subject study to determine which forms of expressiveness are most appropriate in the context of a location-sharing application. We conclude by developing and studying a framework for automatically suggesting high-profit prices in more expressive catalog pricing mechanisms (that allow sellers to offer discounts on bundles in addition to pricing individual items). We use our framework to demonstrate several conditions under which offering discounts on bundles can benefit the seller, the buyer, and the economy as a whole.

212 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu