A Game of Public Facilities on Networks

Fata Elaheh1, Soroush Hosseini Alamdari2

  • 1Massachusetts Institute of Technology
  • 2Cornell University

Details

10:00 - 10:20 | Mon 17 Dec | Glimmer 1 | MoA09.1

Session: Game Theory I

Abstract

In this paper we take on the challenge of characterizing the effect of network structure on the economy of public goods by studying a natural model of public facilities with cascading utility. In this game of public facilities, each node of the network is a strategic agent that has the choice to either open a public facility at its location for a certain purchase-cost or take advantage of a public facility opened by another node. It is assumed that using a facility at another node has a cost relative to its distance from the agent. We study the behavior of agents in this game and show that there always exists a pure Nash equilibrium for the game. Moreover, best-response dynamics converges to a pure Nash equilibrium in finitely many steps. We also explore a set of related optimization problems including finding a social optimum for the game and also present a simple algorithm for finding a Nash equilibrium. We then compare the social welfare of the Nash equilibria to that of the social optima using standard game theoretic measures. We show that the price of anarchy is upper-bounded by the diameter of the network and the universal purchase-cost.