Economic Models of Network FormationBackground and MotivationExample: A Centrality GameComments and ClarificationsNash NetworksProperties of EquilibriaKleinberg’s ModelAn Economic Variation on KleinbergWhat About Navigation?Economic Formation + Economic DynamicsSlide 11(Statistical) Structure and OutcomeSlide 13Price Variation?Network StructureEconomic Models ofNetwork FormationNetworked LifeCIS 112Spring 2008Prof. Michael KearnsBackground and Motivation•First half of course:–common or “universal” structural properties of “natural” networks•small diameter, high clustering, heavy-tailed degree distributions,…–development of statistical models of network formation•Watt’s “Caveman/Solaria”, alpha model, pref. att., Kleinberg’s model…–analyzed simple “transmission” dynamics•disease/fad spread, forest fires, PageRank,…•Second half of course:–examination of “rational” dynamics in networks•interdependent security games, exchange economies,…–interaction of rational dynamics with statistical formation models•e.g. when network is formed via pref. att., what will price variation be?•This lecture: let network formation be “rational” as well•A very recent topicExample: A Centrality Game•Let’s consider a simply stated network formation game•Have N players, consider them vertices in the network•Each player has to decide which edges to build or buy•Assume a fixed cost c to build an edge•Player’s goal: be as “central” in the network as possible•Cost to player i: –cost(i) = j distance(i,j) + c x (# edges bought by i)–distance (i,j) = shortest-path distance between i and j in the network jointly formed by all the players’ edge purchases–players want to minimize their own cost–so need to balance edge costs vs. centrality–will shortly examine a variant of this cost functionComments and Clarifications•Formalizing as a one-shot game–contrast with “gradual” or incremental statistical formation models–could imagine multi-round or stage game; more complex•Each player has a huge choice of actions–action for player i: any subset S_i of all the N-1 edges i could buy–number of choices for S_i = 2^(N-1)–cost of choosing S_i = c|S_i|•Are assuming that if i buys edge to j, j (and all others) can “use” or benefit from this edge (“unilateral” edge formation)•Joint action for all N players:–choice of edge sets for all players: S_1, S_2, …, S_N•Let G = G(S_1,S_2,…,S_N) be the resulting overall graph/NWNash Networks•Q: How can we view this game a NW formation model?•A: View the NWs generated as being the Nash equilibria•More precisely: say that G can be “formed” by the game if:–G = G(S_1,S_2,…,S_N) for some choices for the S_i–S_1,S_2,…,S_N form a Nash equilibrium of the shortest-paths game–so, no player i can improve cost(i) by unilaterally:•dropping an edge they bought and saving the cost c•adding an edge they didn’t buy and paying the cost c•Contrast:–stochastic formation models (Erdos Renyi, pref. att., etc.)•examine the “likely” structural properties of random networks–game-theoretic formation models•examine the structural properties of equilibrium networksProperties of Equilibria•Questions we might ask in NW Life:–what are the diameters of the equilibrium graphs?–what do their degree distributions look like?–what are their clustering coefficients?–Etc. •Not much known precisely•We’ll examine two network formation games:–NW formation game based on Kleinberg’s model–NW formation game based on bipartite Milk-Wheat marketKleinberg’s Model•Similar in spirit to the  -model•Start with an n by n grid of vertices (so N = n^2)–add local connections: all vertices within grid distance p (e.g. 2)–add distant connections:•q additional connections•probability of connection at distance d: ~ 1/d^r–so full model given by choice of p, q and r–large r: heavy bias towards “more local” long-distance connections–small r: approach uniformly random•Kleinberg’s question:–what value of r permits effective search?•Assume parties know only:–grid address of target–addresses of their own direct links•Algorithm: pass message to neighbor closest to targetAn Economic Variation on Kleinberg•Again have N players/vertices, but arrange them in a grid•Grid connections provide free connectivity•Instead of variable probabilities for long-distance edges, introduce variable costs:–let cost to i to purchase edge to j = g(i,j)^a–g(i,j) = grid or “Manhattan” distance from i to j–a = some constant value–so cost grows with distance on grid, at a rate determined by value a–player’s overall cost function: •edge costs + sum of distances to others (centrality)•So now just have another centrality network formation game•Another striking “tipping point”:–for any a <= 2, all Nash equilibria have constant diameter•i.e. diameter does not grow with N!–for any a > 2, all Nash equilibria have unbounded diameter•i.e. diameter grows with N–Nash equilibria seem to be “regular”, but we don’t know much…What About Navigation?Economic Formation + Economic Dynamics•Recall our simple 2-good exchange economy model:–start with a bipartite network between “Milks” and “Wheats”–Milks start with 1 unit milk, but value only wheat–Wheats start with 1 unit wheat, but value only milk–prices = proposed rates of exchange–price p means party is willing to exchange their 1 unit for p of other–equilibrium prices: prices for each party such that•all parties behave “rationally” = trade only with “best price” neighbor(s)•everyone is able to trade away their initial endowment–at equilibrium, party charging p only trades with parties charging 1/p–equilibrium prices = equilibrium wealths•Before we examined wealth distribution for given networksPrice Variation vs.  and 12n = 250, scatter plotExponential decrease with rapid decrease with (Statistical) Structure and Outcome•Wealth distribution at equilibrium:–power law (heavy-tailed) in networks generated by preferential attachment –sharply peaked (Poisson) in random graphs•Price variation (max/min) at equilibrium: –grows as a root of n in preferential attachment–none in random graphs •Random graphs result in “socialist” outcomes–despite lack of centralized