Collusion-Resistant, Approximately Efficient Cost-Sharing Mechanisms

Tim Roughgarden
Department of Computer Science
Stanford University


Wednesday, May 3, 2006
4:30 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

A cost-sharing mechanism is a protocol that collects bids from a set of players, selects a subset of the players to receive a service (incurring a subset-dependent cost), and determines a price to charge each of these players. Three standard requirements for cost-sharing mechanisms are incentive-compatibility, which states that players are motivated to bid their true valuation for the service; budget-balance, meaning that the prices charged should recover the cost incurred; and efficiency, which states that the cost incurred and the valuations of the players served should be traded off in an optimal way. These three goals have been known to be mutually incompatible for thirty years. As a result, nearly all work on cost-sharing mechanisms in the economics and theoretical computer science literatures has focused on achieving two of these goals while completely ignoring the third.

We show that, for a natural penalty-minimization formulation of efficiency and for a wide range of cost functions, the goals of incentive-compatibility, budget-balance, and approximate efficiency are simultaneously achievable. Our techniques apply to all submodular cost functions, as well as to several cost functions corresponding to well-known NP-hard optimization problems. We also prove a generic, quantifiable trade-off between efficiency and budget-balance in cost-sharing mechanisms.

Joint work with Mukund Sundararajan.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html