Foundations and Trends® in Theoretical Computer Science > Vol 8 > Issue 3

Bayesian Mechanism Design

Jason D. Hartline, Northwestern University, USA, hartline@eecs.northwestern.edu
 
Suggested Citation
Jason D. Hartline (2013), "Bayesian Mechanism Design", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 8: No. 3, pp 143-263. http://dx.doi.org/10.1561/0400000045

Published: 13 Jun 2013
© 2013 J. D. Hartline
 
Subjects
Algorithmic game theory,  Design and analysis of algorithms,  Games (co-operative or not),  Economic theory
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Equilibrium
3. Optimal Mechanisms
4. Approximation Mechanisms
5. Multi-dimensional and Non-linear Preferences
6. Approximation for Multi-dimensional and Non-linear Preferences
7. Computation and Approximation Algorithms
A. Mathematical Reference
Acknowledgments
References

Abstract

Systems wherein strategic agents compete for limited resources are ubiquitous: the economy, computer networks, social networks, congestion networks, nature, etc. Assuming the agents' preferences are drawn from a distribution, which is a reasonable assumption for small mechanisms in a large system, Bayesian mechanism design governs the design and analysis of these systems.

This article surveys the classical economic theory of Bayesian mechanism design and recent advances from the perspective of algorithms and approximation. Classical economics gives simple characterizations of Bayes-Nash equilibrium and optimal mechanisms when the agents' preferences are linear and single-dimensional. The mechanisms it predicts are often complex and overly dependent on details of the model. Approximation complements this theory and suggests that simple and less-detail-dependent mechanisms can be nearly optimal. Furthermore, techniques from approximation and algorithms can be used to describe good mechanisms beyond the single-dimensional, linear model of agent preferences.

DOI:10.1561/0400000045
ISBN: 978-1-60198-670-2
134 pp. $90.00
Buy book
 
ISBN: 978-1-60198-671-9
134 pp. $115.00
Buy E-book
Table of contents:
1. Introduction
2. Equilibrium
3. Optimal Mechanisms
4. Approximation Mechanisms
5 Multi-dimensional and Non-linear Preferences
6. Approximation for Multi-dimensional and Non-linear Preferences
7. Computation and Approximation Algorithms
A. Mathematical Reference
Acknowledgments
References

Bayesian Mechanism Design

Systems wherein strategic agents compete for limited resources are ubiquitous. For example, the economy, computer networks, social networks, congestion networks, nature, and so on. Assuming the agents' preferences are drawn from a distribution, a reasonable assumption for small mechanisms in a large system, Bayesian mechanism design governs the design and analysis of these systems.

This monograph surveys the classical economic theory of Bayesian mechanism design and recent advances from the perspective of algorithms and approximation. Classical economics gives simple characterizations of Bayes-Nash equilibrium and optimal mechanisms when the agents' preferences are linear and single-dimensional. The mechanisms it predicts are often complex and overly dependent on details of the model. Approximation complements this theory and suggests that simple and less-detail-dependent mechanisms can be nearly optimal. Furthermore, techniques from approximation and algorithms can describe good mechanisms beyond the single-dimensional, linear model of agent preferences.

This text is an ideal reference for researchers and students working in the area as it presents over a decade of recent work on algorithmic aspects of mechanism design in the context of the classical economic theory of Bayesian mechanism design.

 
TCS-045