Game Theory for Networks. 2nd International ICST Conference, GAMENETS 2011, Shanghai, China, April 16-18, 2011, Revised Selected Papers

Research Article

Local Public Good Provision in Networks: A Nash Implementation Mechanism

Download
382 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-30373-9_3,
        author={Shrutivandana Sharma and Demosthenis Teneketzis},
        title={Local Public Good Provision in Networks: A Nash Implementation Mechanism},
        proceedings={Game Theory for Networks. 2nd International ICST Conference, GAMENETS 2011, Shanghai, China, April 16-18, 2011, Revised Selected Papers},
        proceedings_a={GAMENETS},
        year={2012},
        month={10},
        keywords={network local public good decentralized resource allocation mechanism design Nash implementation budget balance individual rationality},
        doi={10.1007/978-3-642-30373-9_3}
    }
    
  • Shrutivandana Sharma
    Demosthenis Teneketzis
    Year: 2012
    Local Public Good Provision in Networks: A Nash Implementation Mechanism
    GAMENETS
    Springer
    DOI: 10.1007/978-3-642-30373-9_3
Shrutivandana Sharma1,*, Demosthenis Teneketzis1,*
  • 1: University of Michigan
*Contact email: svandana@umich.edu, teneket@eecs.umich.edu

Abstract

In this paper we study resource allocation in decentralized information local public good networks. A network is a local public good network if each user’s actions directly affect the utility of an arbitrary subset of network users. We consider networks where each user knows only that part of the network that either affects it or is affected by it. Furthermore, each user’s utility and action space are its private information, and each user is a self utility maximizer. This network model is motivated by several applications including social networking, online advertising and wireless communications. For this network model we formulate a decentralized resource allocation problem and develop a decentralized resource allocation mechanism (game form) that possesses the following properties: (i) All Nash equilibria of the game induced by the mechanism result in allocations that are optimal solutions of the corresponding centralized resource allocation problem (Nash implementation). (ii) All users voluntarily participate in the allocation process specified by the mechanism (individual rationality). (iii) The mechanism results in budget balance at all Nash equilibria and off equilibrium.