Thursday, November 9, 2006
4:15 pm
B17 Upson Hall

Computer Science
Fall 2006

Michael Kearns
Computer and Information Science
University of Pennsylvania


Two Economic Models of Network Formation

We describe results in two different models of economic or game-theoretic network formation. In such models players are vertices in a network, and there are generally two competing components to the payoffs: players must decide which edges to purchase from themselves to others, but then gain utility via their "participation" in the resulting collective network. One can then ask which networks are equilibria of such a network formation game.

The first model we examine is an economic version of a stochastic network formation model studied by Kleinberg. Players are initially connected in a grid structure that is provided "for free", and then may optionally purchase edges to players at distance d at a cost of d^a for some a > 0. Players wish to minimize the sum of their shortest path distances to all other players (the participation component), and their edge expenditures. We show a striking threshold phenomenon: for a < 2 all Nash equilibria have constant diameter (independent of the number of players n), while for a > 2 all equilibria have diameter growing as a root of n.

In the second model, players form a bipartite network between buyers and sellers by purchasing edges representing trading opportunities. Players wish to maximize their (exchange equilibrium) wealth in the resulting network (the participation component), minus their edge expenditures. Here we provide a complete characterization of all the Nash equilibria of this formation game, which in turn implies strong limits on the price variation that can occur.