Tim Roughgarden

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.

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.