Nash Equilibria in Network Formation Games

ABOUT THE PROJECT

I spent summer 2008 participating in RIPS, the outstanding Research in Industrial Projects for Students program run by the Institute for Pure and Applied Math at UCLA.  At RIPS, I worked on a team project with three other undergraduates, including two Chinese students.  Our project was sponsored by Microsoft Research Asia.

COLLABORATORS

Sarah McBride (now McBride-Luo),   now a PhD student in mathematics at BYU
Xiao Fu, of Salem College in NC
Xiaohui Bei, now a PhD student in computer science at Tsinghua University in Beijing

Faculty Mentor:  Gunes Ercal-Ozkaya, Asst. Prof. of Computer Science, U. Kansas
Industry Mentor:  Wei Chen,  Lead Researcher, Theory Group, Microsoft Research Asia

BACKGROUND

Our study focused on determining what characterizes the equilibrium states achieved in a network formed by selfish agents when each agent seeks to be a conduit of the most network traffic possible (a metric known as betweenness centrality) but only has a limited budget to build connections to other agents.  The process of network formation is considered as a game played on a graph, so we drew from both game theory and graph theory.

A practical application of this network building scenario might be in computer networking, where server owners can charge money for the amount of traffic that passes through their machines or webmasters can gain search engine priority or advertising money based on how many links they have to other sites in the network.  Thus, each agent (server owner or webmaster) seeks a network where its own connections are as heavily used as possible.

In our work, we leveraged computer simulations and analytical proofs to determine several key proofs:
  • in an undirected network, networks that achieve Nash equilibrium in our game must be connected.
  • in a directed network, networks that achieve Nash equilibrium in our game must be weakly connected. 
We also conjecture, among other things, that:
  • in a directed network, networks that achieve Nash equilibrium in our game must be strongly connected.
Essentially, these results indicate that once agents arrive at an equilibrium in which no one individual can alter his connections to better his share of traffic flow, we can guarantee that every agent still has a path to every other agent in the network.

We submitted this work to the SAGT '09 conference, but unfortunately did not make the cut at this highly competitive, very theoretically oriented conference.

You can see the abstract and full text of our submission, "On Pure and Approximate Nash Equilibria in Betweenness Centrality Games", below.


ABSTRACT

In this paper, we study a network formation game in which each node in the network attempts to maximize its betweenness centrality, a game originally proposed by Chen et al. [4]. We prove connectivity properties of pure Nash equilibria for both directed and undirected versions of the game. We conduct extensive simulations to explore various properties of stable graphs, such as connectivity, symmetry, and fairness. We also study types of graphs that provide good approximation ratios to pure Nash equilibria. Our results provide better understanding of the stable structures that can arise when selfish agents each attempt to maximize their own share of traffic flow in a social or computer network.

FULL TEXT

Available below in PDF form below.
Ċ
Mike Hughes,
Mar 3, 2009, 9:44 AM
Comments