Quantifying inefficiency in cost-sharing mechanisms
Abstract
In a cost-sharing problem, several participants with unknown preferences vie to receive some good or service, and each possible outcome has a known cost. A cost-sharing mechanism is a protocol that decides which participants are allocated a good and at what prices. Three desirable properties of a cost-sharing mechanism are: incentive-compatibility, meaning that participants are motivated to bid their true private value for receiving the good; budget-balance, meaning that the mechanism recovers its incurred cost with the prices charged; and economic efficiency, meaning that the cost incurred and the value to the participants are traded off in an optimal way. These three goals have been known to be mutually incompatible for thirty years. Nearly all the work on cost-sharing mechanism design by the economics and computer science communities has focused on achieving two of these goals while completely ignoring the third.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 01, 2009
- Source ID
- 10.1145/1538902.1538907
Entities
People
- Mukund Sundararajan
- Tim Roughgarden
Organizations
- Defense Advanced Research Projects Agency
- Office of Naval Research
- Stanford University