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:
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. |
 | |
|
|
