A Game Theoretic Approach to Network Formation

Open Access
Lichter, Shaun Matthew
Graduate Program:
Industrial Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
Committee Members:
  • Terry Lee Friesz, Dissertation Advisor
  • Dr Paul Griffin, Committee Chair
  • Tao Yao, Committee Member
  • Ling Rothrock, Committee Member
  • George Kesidis, Committee Member
  • Christopher H Griffin, Special Member
  • Network Formation
  • Network Game
  • Game Theory
  • Network Science
  • Optimization
  • Graph Generation
As an alternative view to the graph formation models in the statistical physics community, we introduce graph formation models using \textit{network formation} through selfish competition as an approach to modeling graphs with particular topologies. We introduce a model with nonlinear payoffs that results in a pairwise stable graph with an arbitrary degree sequence. Further, we introduce a model with link bias that also shows how networks with arbitrary degree sequences may be formed as a result of selfish competition where agents have a preference for linking with one player over another. For each of these models, we present an optimization model for calculating the price of anarchy, which measures the price of decentralized link decisions by players vs centralized link decisions. We introduced coercion into the model, by considering general network constraints that may be enforced by a player that is in the game. This model also enables the modeler to analyze the effect of removing a player from the game. We further investigate a specific application of our results to collaborative oligopolies. We extend the results of Goyal and Joshi (S. Goyal and S. Joshi. Networks of collaboration in oligopoly. Games and Economic behavior, 43(1):57-85, 2003), who first considered the problem of collaboration networks of oligopolies and showed that under certain linear assumptions network collaboration produced a stable complete graph through selfish competition. We show with nonlinear cost functions and player payoff alteration that stable collaboration graphs with an arbitrary degree sequence can result. We then show conditions under which these results can be applied to spatial collaborative oligopolies.