Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games

Gopalakrishnan, Ragavendran; Marden, Jason R.; Wierman, Adam
November 2014
Mathematics of Operations Research;Nov2014, Vol. 39 Issue 4, p1252
Academic Journal
We consider the problem of designing distribution rules to share "welfare" (cost or revenue) among individually strategic agents. There are many known distribution rules that guarantee the existence of a (pure) Nash equilibrium in this setting, e.g., the Shapley value and its weighted variants; however, a characterization of the space of distribution rules that guarantees the existence of a Nash equilibrium is unknown. Our work provides an exact characterization of this space for a specific class of scalable and separable games that includes a variety of applications such as facility location, routing, network formation, and coverage games. Given arbitrary local welfare functions W, we prove that a distribution rule guarantees equilibrium existence for all games (i.e., all possible sets of resources, agent action sets, etc.) if and only if it is equivalent to a generalized weighted Shapley value on some "ground" welfare functions W', which can be distinct from W. However, if budget-balance is required in addition to the existence of a Nash equilibrium, then W' must be the same as W. We also provide an alternate characterization of this space in terms of "generalized" marginal contributions, which is more appealing from the point of view of computational tractability. A possibly surprising consequence of our result is that, in order to guarantee equilibrium existence in all games with any fixed local welfare functions, it is necessary to work within the class of potential games.


Related Articles

  • Research on combinatorial auction. Liu Xin-ming // Proceedings of the International Symposium on Electronic Commerc;Jun2010, p288 

    Since the mid-20th century, with the Nash equilibrium theory formulation and development, game theory has gradually become a new subject. It involves economics, management, computer science, sociology and other fields, which has played a significant role in promoting the development of society....

  • Perfect foresight dynamics in games with linear incentives and time symmetry. Takahashi, Satoru // International Journal of Game Theory;2008, Vol. 37 Issue 1, p15 

    This paper investigates absorption and global accessibility under perfect foresight dynamics in games with linear incentives. An action distribution in the society is absorbing if there is no equilibrium path escaping from the distribution, and globally accessible if, from every initial...

  • Efficiency in the trust game: an experimental study of precommitment. Bracht, Juergen; Feltovich, Nick // International Journal of Game Theory;2008, Vol. 37 Issue 1, p39 

    We experimentally test a precommitment mechanism for the trust game. Before the investor’s decision, the allocator places an amount into escrow, to be forfeited if he keeps the proceeds of investment for himself. We vary the available escrow amounts—in particular, whether there is...

  • Polymatrix games and optimization problems. Strekalovskii, A.; Enkhbat, R. // Automation & Remote Control;Apr2014, Vol. 75 Issue 4, p632 

    Consideration was given to the properties of the polymatrix game, a finite noncooperative game of N players ( N ⩾ 3). A theorem of reduction of the search for Nash equilibria to an optimization problem was proved. This clears the way to the numerical search of equilibria. Additionally, a...

  • Nondominated equilibrium solutions of a multiobjective two-person nonzero-sum game in extensive form and corresponding mathematical programming problem. Ichiro Nishizaki; Takuma Notsu // Journal of Global Optimization;Oct2008, Vol. 42 Issue 2, p201 

    Abstract  In most of studies on multiobjective noncooperative games, games are represented in normal form and a solution concept of Pareto equilibrium solutions which is an extension of Nash equilibrium solutions has been focused on. However, for analyzing economic situations and modeling...

  • An application of optimization theory to the study of equilibria for games: a survey. Mallozzi, Lina // Central European Journal of Operations Research;Sep2013, Vol. 21 Issue 3, p523 

    This contribution is a survey about potential games and their applications. In a potential game the information that is sufficient to determine Nash equilibria can be summarized in a single function on the strategy space: the potential function. We show that the potential function enable the...

  • Equilibria of the Games in Choice Form. Stefanescu, Anton; Ferrara, Massimiliano; Stefanescu, Maria // Journal of Optimization Theory & Applications;Dec2012, Vol. 155 Issue 3, p1060 

    Equilibrium in choice is a solution-concept for noncooperative games defined in a general framework-the game in choice form. There are two leading ideas of the new definition. One is that the players' preferences need not be explicitly represented, but earlier accepted solution concepts should...

  • Order-Driven Markets are Almost Competitive. RITZBERGER, KLAUS // Review of Economic Studies;Jan2016, Vol. 83 Issue 1, p338 

    This article studies a market game under uncertainty in which agents may submit multiple limit and market orders. When agents know their preferences at all states, the competitive equilibrium can be supported as a Nash equilibrium of the market game, that is, agents behave as if they were price...

  • Network Design with Weighted Players. Ho-Lin Chen; Roughgarden, Tim // Theory of Computing Systems;Aug2009, Vol. 45 Issue 2, p302 

    We consider a model of game-theoretic network design initially studied by Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, ), where selfish players select paths in a network to minimize their cost, which is prescribed by...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics