Abstract:

In a network with selfish users, designing and deploying a protocol
determines the rules of the game by which end users interact with
each other and with the network. We study the problem of designing
a protocol to optimize the equilibrium behavior of the induced
network game. We consider network cost-sharing games, where the
set of Nash equilibria depends fundamentally on the choice of an
edge cost-sharing protocol. Previous research focused on the 
Shapley protocol, in which the cost of each edge is shared equally
among its users.

In this talk, we will describe he design of optimal cost-sharing
protocols for undirected and directed graphs, single-sink and
multicommodity networks, different classes of cost-sharing
methods, and different measures of the inefficiency of equilibria.
One of our main technical tools is a complete characterization of
the uniform cost-sharing protocols---protocols that are designed
without foreknowledge of or assumptions on the network in which
they will be deployed. We use this characterization result to 
identify the optimal uniform protocol in several scenarios. We also 
provide several matching upper and lower bounds on the 
best-possible performance of non-uniform cost-sharing protocols.

This is a joint work with Tim Roughgarden and Gregory Valiant


Biography:

Ho-Lin Chen is a postdoctoral researcher in Center for Mathematics
of Information at California Institute of Technology. He received
bachelor's degree in electrical engineering and mathematics from 
National Taiwan University in 2000, and Ph.D. degree from computer 
science from Stanford University in 2007. His research interests 
are algorithms with application to control natural systems and 
algorithmic game theory.