The Networked Common Goods Game

Computer Science – Computer Science and Game Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

The Networked Common Goods Game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Networked Common Goods Game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Networked Common Goods Game will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-221453

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.