Topic：Designing Networks With Good Equilibria

Date&Time：2015/4/17(五) 14:20

Speaker：陳和麟 教授 (台大電機系)

Location：清華大學台達館 R216

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.