The networked common goods game

DOI10.1007/978-3-642-17461-2_26zbMATH Open1310.91047arXiv1004.1578OpenAlexW2190751627MaRDI QIDQ3066468FDOQ3066468

Authors: Jinsong Tan 

Publication date: 10 January 2011

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Abstract: We introduce a new class of games called the networked common goods game (NCGG), which generalizes the well-known common goods game. We focus on a fairly general subclass of the game where each agent's utility functions are the same across all goods the agent is entitled to and satisfy certain natural properties (diminishing return and smoothness). We give a comprehensive set of technical results listed as follows. * We show the optimization problem faced by a single agent can be solved efficiently in this subclass. The discrete version of the problem is however NP-hard but admits an fully polynomial time approximation scheme (FPTAS). * We show uniqueness results of pure strategy Nash equilibrium of NCGG, and that the equilibrium is fully characterized by the structure of the network and independent of the choices and combinations of agent utility functions. * We show NCGG is a potential game, and give an implementation of best/better response Nash dynamics that lead to fast convergence to an $epsilon$-approximate pure strategy Nash equilibrium. * Lastly, we show the price of anarchy of NCGG can be as large as $Omega(n^{1-epsilon})$ (for any $epsilon>0$), which means selfish behavior in NCGG can lead to extremely inefficient social outcomes.

Full work available at URL: https://arxiv.org/abs/1004.1578

Recommendations

• Incentive-based search for efficient equilibria of the public goods game
• Public goods games in directed networks
• Near-optimal network design with selfish agents
• Near-optimal network design with selfish agents
• Equilibria and efficiency loss in games on networks

Mathematics Subject Classification ID

Games involving graphs (91A43)

Cited In (5)

• Decentralized incentives for general well-being in networked public goods game
• Networks of common property resources
• Contribution games in networks
• Incentive-based search for efficient equilibria of the public goods game
• Public good provision games on networks with resource pooling

This page was built for publication: The networked common goods game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3066468)