|
||||||||||||||||
|
Ph.D. ThesesExact and Approximate Equilibria for Network Formation and Cut Games
By Bugra Caskurlu
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 first define the survivable version of the game-theoretical network formation game, which is usually referred as the Connection Game and prove the existence of cheap exact and approximate Nash equilibrium solutions. Next, we define a new 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. We also introduce the Network Cutting Game, a dual approach to network formation games. In the Network Cutting Game each player wants to cut apart certain parts of a given network instead of connecting them. We consider the strategic version of several standard cut problems, i.e., s-t cut, multiway cut and multicut, and give efficient algorithms to compute cheap exact and approximate Nash equilibrium.
|
||||||||||||||||
Research
