Monday, August 27, 2007
4:15 PM
5130 Upson Hall
  Theory Seminar
Fall 2007
CS 789

Tim Roughgarden
Stanford University


Measures of Inefficiency and Optimal Protocol Design

We study how to design network protocols that minimize the worst-case efficiency loss caused by selfish end users. The goal is to identify the optimal procotol subject to natural implementation constraints. We illustrate this idea in the context of cost-sharing protocols for large networks. Our results build on a complete characterization of the budget-balanced protocols that always induce pure-strategy equilibria, which in turn is proved using a connection between potential games and the Shapley value.

Joint work with Ho-Lin Chen and Gregory Valiant.