Contribution
Teaching slides on potential games for a course on strategic games. They give the definitions after Monderer and Shapley, the theorem linking generalized ordinal potentials with the finite improvement property, Rosenthal’s theorem that congestion games are potential games, worked traffic examples, the Braess paradox, and bounds on the price of stability. Nothing in them is new; their value here is a clear second statement of the definitions and the theorem THEORY-896 attributes to Monderer and Shapley.
Key insight
A potential is a single function on joint strategies that every player’s improving move climbs. Asking only that it climb, not that it track the size or even the exact sign pattern of payoff changes, gives exactly the games in which improvement cannot go round in circles.
Assumptions
- A game G = (S₁, …, S_n, p₁, …, p_n) with payoff functions p_i on S = S₁ × ⋯ × S_n (slide 3). Cost functions are payoffs negated (slide 16).
- Finite strategy sets for the theorem (slide 15) and for the termination of best-response dynamics (slide 9).
Key results
- Best-response dynamics (slides 3–5). Repeatedly let a player not playing a best response switch to one. With strictly dominant strategies it ends within n steps. It can fail to find an equilibrium: a matching-pennies game with a third strategy E has the equilibrium (E, E), which the dynamics can miss.
- Exact potential (slide 6), “Monderer and Shapley ‘96”. P : S → ℝ with p_i(s_i, s_−i) − p_i(s′i, s−i) = P(s_i, s_−i) − P(s′i, s−i) for all i, s_−i, s_i, s′_i. The prisoner’s dilemma has one that counts the defectors (slides 7–8).
- Termination (slide 9). “For finite potential games all best response dynamics terminate”, since the potential strictly increases along each best-response path.
- Ordinal potential (slide 10). p_i(s_i, s_−i) − p_i(s′i, s−i) > 0 iff P(s_i, s_−i) − P(s′i, s−i) > 0. A modified prisoner’s dilemma has an ordinal potential and no exact one (slide 11).
- FIP (slide 12). s′i is a better response given s if p_i(s′i, s−i) > p_i(s_i, s−i). A path is a sequence of joint strategies each differing from the last in one player’s strategy; it is an improvement path “if it is maximal and for all k > 1, p_i(s^{k+1}) > p_i(s^k), where i deviated from s^k”. “G has the finite improvement property (FIP), if every improvement path is finite.” “If G has the FIP, then it has a Nash equilibrium.”
- FIP without an ordinal potential (slide 13). The game with rows T, B, columns L, R and payoffs (T, L) = (1, 0), (T, R) = (2, 0), (B, L) = (2, 0), (B, R) = (0, 1) has the FIP. An ordinal potential would need P(T, L) < P(B, L) < P(B, R) < P(T, R), “but p₂(T, L) = p₂(T, R), so P(T, L) = P(T, R)”.
- Generalized ordinal potential (slide 14). p_i(s_i, s_−i) − p_i(s′i, s−i) > 0 implies P(s_i, s_−i) − P(s′i, s−i) > 0. The same game has one: P(T, L) = 0, P(T, R) = 3, P(B, L) = 1, P(B, R) = 2. (The potential table is labelled C, D, carried over from the prisoner’s dilemma slides; checked, each strict improvement raises it.)
- The theorem (slide 15). “Theorem (Monderer and Shapley ‘96) Every finite game has a generalized ordinal potential iff it has the FIP.” (⇒) “The generalized ordinal potential increases along every improvement path.” (⇐, sketch) “An improvement sequence: a prefix of an improvement path. Assign to each joint strategy s the number of improvement sequences that terminate in it. Because the game has the FIP this number is finite. This defines a generalized ordinal potential.”
- Congestion games (slides 17–26). Rosenthal (1973): every congestion game is a potential game, with P(s) = Σ_j Σ_{k=1}^{x_j(s)} d_j(k), so every congestion game has a Nash equilibrium. Fair cost sharing is the case d_j(k) = c_j/k (slide 27).
- Braess paradox and price of stability (slides 34–47). Adding a zero-cost link raises everyone’s travel time from 65 to 80; price of stability at most 4/3 for linear delays (Roughgarden and Tardos) and at most H(n) for fair cost sharing (Anshelevich et al.), both stated.
Claims
| id | claim | strength | support |
|---|---|---|---|
| C1 | A finite game has a generalized ordinal potential iff it has the FIP | moderate as presented | slide 15: (⇒) proved in a line; (⇐) sketched; credited to Monderer and Shapley 1996 without lemma number or page |
| C2 | A game can have the FIP and no ordinal potential | strong | slide 13, a checked two-by-two counterexample |
| C3 | In a finite potential game every best-response path terminates, so a pure equilibrium exists | strong | slide 9, potential strictly rises |
| C4 | Every congestion game is an (exact) potential game | moderate | slide 26, Rosenthal’s potential stated; general proof referred to Tijs’s notes |
| C5 | Price of stability ≤ 4/3 for linear congestion games and ≤ H(n) for fair cost sharing | weak here | stated, slides 43 and 47, with citations |
Concepts
- Better response — a strictly payoff-improving change of one’s own strategy (slide 12).
- Improvement path — a maximal path of better responses; the FIP says every one is finite.
- Improvement sequence — a prefix of an improvement path (slide 15).
- Exact, ordinal and generalized ordinal potential — as above; each is weaker than the one before.
Connections
Monderer and Shapley (1996, LIT-1462) is the source the slides cite and the record cannot read. Candogan et al. (LIT-1442) restate the exact definition. THEORY-896 states the same equivalence and proves it in the record with a different potential, the length of the longest improvement path ending at a profile, where the slides count the improvement sequences ending there. Both are finite for the same reason: with the FIP there is no cycle, and a finite game has finitely many profiles, so every improvement sequence has fewer than |S| steps.
Bearing on the record
- THEORY-896: partly. Its promote_when asks for Monderer and Shapley
read first-hand: the lemma’s wording, number and page, the paper’s
definitions of the FIP and of generalized ordinal potential, and
agreement with the record’s proof. These slides do not meet that: they
are not the paper, and they give no lemma number or page. What they do
give:
- The class. THEORY-896 notes that its two restatements disagree on whether the equivalence is with generalized ordinal or with ordinal potentials. Apt states it for generalized ordinal potentials, as Duersch, Oechssler and Schipper do, and slide 13 shows a finite game with the FIP and no ordinal potential, so an equivalence with ordinal potentials is false. Biggar and Shames’s weaker sentence, that ordinal potential games have the FIP, is consistent with this.
- The definitions of the FIP and of generalized ordinal potential agree with THEORY-896’s, except that Apt’s improvement paths are maximal; finiteness of every path is the same condition either way.
- The proof. Apt’s sketch and the record’s proof differ only in the potential chosen, and both work. So the mathematics and the class are corroborated by a second source; the attribution’s exact form still waits on LIT-1462.
- No instruction for machine-learning practice; nothing for the anthology.
Limitations
- Second-hand attribution. “Monderer and Shapley ‘96” with no lemma, page or wording.
- The converse is a sketch. “Because the game has the FIP this number is finite” needs the finiteness of the game as well: without cycles and with finitely many profiles each sequence is bounded in length. That a step s → t raises the count is left to the reader (every sequence ending at s extends to one ending at t, and t alone is one more).
- Slide slips. The generalized ordinal potential table on slide 14 is labelled C, D for a game with rows T, B and columns L, R; slide 44 writes the harmonic number as Σ 1/n for Σ 1/i.
Open questions
- Monderer and Shapley’s own statement: whether it is their Lemma 2.5, and what they say for infinite games.