The Effect of Network Topology on Equilibria in Markets and Evolutionary Games



Sid Suri

Postdoctoral Associate

Monday  Feb. 12, 2007
4:00 PM, 5130 Upson Hall


Abstract: The central question that this work begins to address is: if players are interacting strategically with their local neighborhood in a network, how does the topology of that network affect the structure of the equilibria?

First, we study a natural extension of classical evolutionary game theory to a setting in which pairwise interactions are restricted to the edges of an undirected network. We generalize the definition of an evolutionary stable strategy (ESS) to this setting, and show a pair of complementary results that exhibit the power of randomization in our setting. The first result shows that subject to degree or edge density conditions, the classical ESS of any game are preserved when the graph is chosen randomly and the mutation set is chosen adversarially. The second shows that classical ESS are preserved when the graph is chosen adversarially and the mutation set is chosen randomly.

Second, we answer this question in the setting of market based games.

We introduce a graphical version of the Fisher model which consists of a bipartite graph or network, with buyers on one side and sellers on the other. At market clearing equilibrium, we characterize precisely when different sellers of the same good can command different prices from one another. Then, we consider bipartite graphs from generative models inspired by social network theory. Our results relate price variation to statistical properties of these graphs. Finally, I will briefly outline results of a related market based game where the players first have to buy edges to other players, and then trade according the graph that has been purchased.