Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Exact and Approximate Equilibria for Optimal Group Network Formation

 

Bugra Caskurlu
Ph.D. Candidate
Computer Science Department
Rensselaer Polytechnic Institute (RPI)
Troy, New York

As opposed to the classical networking literature, many modern computer networks, including the Internet itself, are constructed and maintained by self-interested agents. In such networks, the global performance of the system may not be as good as in the case where a central authority can simply dictate a solution; rather, we need to understand the quality of solutions that are consistent with self-interested behavior. We define a network game, Group Network Formation Game, which represents the scenario when strategic agents are building a network together. In our game, agents can have extremely varied connectivity requirements, and attempt to satisfy those requirements by purchasing links in the network. We show a variety of results about equilibrium properties in such games, including the fact that the price of stability is 1 when all nodes in the network are owned by players, and that doubling the number of players creates an equilibrium as good as the optimum centralized solution. For the general case, we show the existence of a 2-approximate Nash equilibrium that is as good as the centralized optimum solution, as well as how to compute good approximate equilibria in polynomial time. Our results essentially imply that for a variety of connectivity requirements, giving agents more freedom can paradoxically result in more efficient outcomes.

 

DATE: 2 November, 2009, Monday @ 14:40
PLACE: EA 409