Using Expressiveness to Increase Efficiency in Social and Economic Mechanisms
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
Mechanisms for facilitating peoples interactions with businesses, their governments, and each other are ubiquitous in todays 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 Googles 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. Todays 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 mechanisms 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.
- Information Science
- Economics and Cost Analysis