Using Expressiveness to Increase Efficiency in Social and Economic Mechanisms

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2011
Accession Number
ADA556940

Entities

People

  • Michael Benisch

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Weapons Technologies

DTIC Thesaurus Topics

  • Commerce
  • Computer Programming
  • Computer Science
  • Computers
  • Data Mining
  • Information Science
  • Internet
  • Mobile Phones
  • Network Science
  • Operating Systems
  • Probability Distributions
  • Retail
  • Social Media
  • Social Networking Services
  • Social Networks
  • Standards
  • Trees (Data Structures)

Readers

  • Agent-Based Social Robotics and Mobile-Assisted Learning in Virtual Environments.
  • Mathematical Modeling and Probability Theory.
  • Theoretical Analysis.