OpenFrontiers
Join
← Back to the index
OP-0699OpenMathematical economics and game theory

Potential functions and the inefficiency of equilibria · 2006-econ-7

Evolutionary Games, Learning and Congestion Games · ICM 2006: Potential functions and the inefficiency of equilibria

MSC 91B · Mathematical economics

Inferred from the community field; finer classification has not been reviewed.

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Let G\mathcal G be a class of noncooperative games. For each G∈GG\in\mathcal G, fix an outcome space XGX_G, an equilibrium set EG⊆XGE_G\subseteq X_G for a specified equilibrium concept, and a nonnegative social objective FG:XG→R≥0F_G:X_G\to\mathbb R_{\ge 0} to be minimized or maximized. For a minimization objective, define the worst-equilibrium inefficiency by

I(G)=sup⁡x∈EGFG(x)inf⁡y∈XGFG(y), I(G)=\sup_{x\in E_G}\frac{F_G(x)}{\inf_{y\in X_G}F_G(y)},

and, for a maximization objective, reverse the ratio. A potential-function characterization of the equilibria is a real-valued function ΦG:XG→R\Phi_G:X_G\to\mathbb R whose local optima, with respect to the relevant topology or unilateral-deviation neighborhood structure, are precisely the equilibria in EGE_G.

Determine conditions on the games, the equilibrium concept, and the social objective under which an upper bound on I(G)I(G), or a uniform upper bound on I(G)I(G) over G∈GG\in\mathcal G, implies the existence of such a potential function or of a suitably generalized potential function. Characterize how strong a converse to the potential-function method can hold and what quantitative relation, if any, can be guaranteed between the inefficiency bound, the potential function, and the social objective.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗
Remaining questions in this record

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

Let NN be a finite set of agents and RR a finite set of resources. Agent ii chooses an action aia_i from a prescribed family Ai⊆2RA_i\subseteq 2^R. For an action profile aa, write Sr(a)={i∈N:r∈ai}S_r(a)=\{i\in N:r\in a_i\}. Each resource rr has a local welfare function Wr:2N→RW_r:2^N\to\mathbb R and a distribution rule fWr:N×2N→Rf^{W_r}:N\times 2^N\to\mathbb R, where fWr(i,S)=0f^{W_r}(i,S)=0 for i∉Si\notin S; the utility of agent ii is

Ui(a)=∑r∈aifWr(i,Sr(a)). U_i(a)=\sum_{r\in a_i} f^{W_r}(i,S_r(a)).

A generalized weighted Shapley rule is obtained by choosing positive player weights and an ordered partition of NN, and assigning to each user a weighted average of that user's marginal contribution to a ground welfare function over arrival orders consistent with the ordered partition. Such rules induce generalized weighted potential games.

Characterize the tuples of action families (Ai)i∈N(A_i)_{i\in N} for which the following necessity statement holds: for every choice of resources and local welfare functions, any collection of distribution rules that guarantees the existence of a pure Nash equilibrium in every resulting separable welfare-sharing game must be equivalent, possibly on ground welfare functions different from the given WrW_r, to generalized weighted Shapley rules, and hence must induce generalized weighted potential games.

Source reference: Ragavendran Gopalakrishnan, Jason R. Marden, and Adam Wierman, "Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games," Mathematics of Operations Research 39(4) (2014), 1252-1296, Section 4.3 ("Limitations and extensions"), DOI: https://doi.org/10.1287/moor.2014.0651; arXiv:1402.3610, https://arxiv.org/abs/1402.3610.

Question 2

Let GG be a finite cost-minimization game with action-profile set AA, individual cost functions Ci:A→RC_i:A\to\mathbb R, and nonnegative social cost C:A→R≥0C:A\to\mathbb R_{\ge 0}, where min⁡x∈AC(x)>0\min_{x\in A}C(x)>0. An ordinal potential is a function Φ:A→R\Phi:A\to\mathbb R such that, for every unilateral deviation from aa to (ai′,a−i)(a_i',a_{-i}),

Ci(ai′,a−i)<Ci(a)⟺Φ(ai′,a−i)<Φ(a). C_i(a_i',a_{-i})<C_i(a)\quad\Longleftrightarrow\quad \Phi(a_i',a_{-i})<\Phi(a).

For each ordinal potential Φ\Phi, define the inefficiency guarantee of its global minimizers by

R(Φ)=sup⁡a∈argmin⁡x∈AΦ(x)C(a)min⁡x∈AC(x). R(\Phi)=\sup_{a\in\operatorname*{argmin}_{x\in A}\Phi(x)} \frac{C(a)}{\min_{x\in A}C(x)}.

Determine how R(Φ)R(\Phi) depends on the choice of ordinal potential for the same game. In particular, characterize or bound the possible values of R(Φ)R(\Phi) over all ordinal potentials of GG in terms of structural properties of the game and the social cost.

Source reference: Pieter Kleer and Guido Schäfer, "Computation and Efficiency of Potential Function Minimizers of Combinatorial Congestion Games," Mathematical Programming 190(1-2) (2021), 523-560, Section 7 ("Concluding remarks"), DOI: https://doi.org/10.1007/s10107-020-01546-6.

Progress & source assessment

Source-reported assessment from the ICM catalogue snapshot. This is not an independent review by Frontier Science.

The problem is unresolved. No general necessary-and-sufficient conditions are known under which a bound on equilibrium inefficiency forces a potential-function characterization, and no general quantitative relation between such a bound, a potential, and the social objective has been established.

A bound on inefficiency cannot by itself imply potential structure: the social objective is additional data and does not determine the players' unilateral payoff differences, whereas potentiality is a condition on precisely those differences. This obstruction also occurs in natural models. Abshoff, Cord-Landwehr, Jung, and Skopalik prove explicit price-of-anarchy bounds throughout their SUM and MAX multilevel network games, including constant bounds in parameter regimes, while also proving that both game families are not potential games (and that the SUM game is not even weakly acyclic). Thus an unconditional converse is false, but this does not classify the additional hypotheses under which some converse might hold.

Established partial progress is as follows.

  • Dov Monderer and Lloyd S. Shapley, “Potential Games,” Games and Economic Behavior 14(1), 1996, 124–143, DOI 10.1006/game.1996.0044. They characterize finite exact potential games by closed-path (equivalently, four-cycle) conditions on unilateral payoff differences and characterize generalized ordinal potentials through improvement-path behavior. These are complete tests for particular notions of potential, but they do not derive potentiality from an inefficiency bound or involve a social objective.

  • Sebastian Abshoff, Andreas Cord-Landwehr, Daniel Jung, and Alexander Skopalik, “Multilevel Network Games,” Proceedings of the 10th International Conference on Web and Internet Economics (WINE), LNCS 8877, 2014, 435–440, DOI 10.1007/978-3-319-13129-0_36, arXiv 1409.5383. Their simultaneous inefficiency bounds and non-potentiality results give a substantive counterexample to any converse based on a price-of-anarchy bound alone.

  • Farhad Farokhi, Walid Krichene, Alexandre M. Bayen, and Karl H. Johansson, “A Necessary and Sufficient Condition for the Existence of Potential Functions for Heterogeneous Routing Games,” 2014, arXiv 1312.1075. Theorem 4.4 gives a necessary-and-sufficient cross-derivative condition for a twice continuously differentiable potential in two-type nonatomic heterogeneous routing games. Under stronger convexity and affine-cost assumptions, their price-of-anarchy analysis gives an upper bound of 2. This links potential existence and inefficiency within one restricted model, but the implication remains from structural conditions and a potential to an efficiency bound; it is not the requested converse, and the potential characterization is not extended to arbitrary numbers of types.

  • Uri Nadav and Tim Roughgarden, “The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds,” Proceedings of WINE 2010, LNCS 6484, 319–326, DOI 10.1007/978-3-642-17572-5_26. Their primal-dual result associates every equilibrium concept described by homogeneous linear inequalities with a dual proof framework capable of tight price-of-anarchy bounds; Theorem 1 identifies the exact distributional scope of ordinary smoothness certificates. This is a converse/completeness theorem for proof certificates, not an implication to a potential function.

  • Tim Roughgarden, “Intrinsic Robustness of the Price of Anarchy,” Journal of the ACM 62(5), 2015, Article 32, DOI 10.1145/2806883. The completeness theorem for congestion games shows that smoothness arguments recover the optimal worst-case price-of-anarchy bound for every nonempty set of positive nondecreasing cost functions. This is strong progress toward understanding which analytic structure accompanies an inefficiency bound in a major class, but the resulting structure is a smoothness inequality, not a potential inferred from the bound; congestion games already possess their standard potential for independent reasons.

  • Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A. Parrilo, “Flows and Decompositions of Games: Harmonic and Potential Games,” Mathematics of Operations Research 36(3), 2011, 474–503, DOI 10.1287/moor.1110.0500. They give a canonical decomposition of every finite game into potential, harmonic, and nonstrategic components and explicit projections onto the potential subspace. This supplies a rigorous generalized/approximate notion of potential structure, but it does not show that bounded equilibrium inefficiency controls the harmonic component or distance to a potential game.

What remains open is a nontrivial classification of additional hypotheses tying the equilibrium incentives to the social objective strongly enough that an inefficiency guarantee forces an exact, ordinal, approximate, or other useful potential, together with any quantitative correspondence between the guarantee and that potential. The cited special-case characterizations and certificate-completeness results do not exhaust the game classes, equilibrium concepts, objectives, or potential notions in the stated problem.

References
  1. [1]ICM Conjectures · 2006-econ-7 link
  2. [2]ICM 2006: Potential functions and the inefficiency of equilibria link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.