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.

The first model and results are joint work with Eyal Even-Dar,
and the second with Eyal Even-Dar and Siddharth Suri.