Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.2 — closest potential game Πmφ+(I−Πm)um\Pi_m\varphi + (I-\Pi_m)u^mΠm​φ+(I−Πm​)um and closest harmonic game um−Πmφu^m - \Pi_m\varphium−Πm​φ

Proved
HarmonicGames.Projection.theorem_6_2

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

game-theoryharmonic-gameslinear-algebrap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-games

Throughout, M\mathcal MM is a finite set of players and each player mmm has a nonempty finite strategy set EmE^mEm with hm=∣Em∣h_m = |E^m|hm​=∣Em∣ strategies; a game is given by utilities um:E→Ru^m : E \to \mathbb Rum:E→R on the profiles E=∏mEmE = \prod_m E^mE=∏m​Em. Let DDD be the operator (21), δ0\delta_0δ0​ the combinatorial gradient of the game graph, Πm=Dm†Dm\Pi_m = D_m^\dagger D_mΠm​=Dm†​Dm​, and ∥⋅∥M,E\|\cdot\|_{M,E}∥⋅∥M,E​ the norm (56). For a game GGG with utilities {um}m\{u^m\}_m{um}m​ put

φ=δ0†Du∈C0.\varphi = \delta_0^\dagger D u \in C_0 .φ=δ0†​Du∈C0​.

Theorem 6.2. With respect to the norm (56):

  1. the closest potential game to GGG has utilities Πmφ+(I−Πm)um\Pi_m \varphi + (I - \Pi_m) u^mΠm​φ+(I−Πm​)um for all m∈Mm \in \mathcal Mm∈M;
  2. the closest harmonic game to GGG has utilities um−Πmφu^m - \Pi_m \varphium−Πm​φ for all m∈Mm \in \mathcal Mm∈M.

Each item is stated as a characterization: a game G^\hat GG^ is a closest potential game to GGG (a potential game minimizing ∥G−G^∥M,E\|G - \hat G\|_{M,E}∥G−G^∥M,E​ over all potential games) if and only if u^m=Πmφ+(I−Πm)um\hat u^m = \Pi_m \varphi + (I - \Pi_m) u^mu^m=Πm​φ+(I−Πm​)um for every mmm; likewise for harmonic games (games in H⊕N\mathcal H \oplus \mathcal NH⊕N). This gives at once that the closest game exists, is unique, and is given by the formula. Note that Πm\Pi_mΠm​ is applied to the same function φ\varphiφ for every player.

The closed forms show that the closest potential game keeps the nonstrategic part (I−Πm)um(I - \Pi_m) u^m(I−Πm​)um of the game and replaces its strategic part by the preferences induced by the potential φ\varphiφ.

Formalization Note δ0†\delta_0^\daggerδ0†​ and Dm†D_m^\daggerDm†​ are Moore–Penrose pseudoinverses for the unweighted inner products of Sections 3–4; "closest" refers to the weighted norm (56). The definite article in "the closest potential game" is rendered by the "if and only if".

Preamble
import Mathlib
import Definitions.Def_HarmonicGames_Projection_Closest
Formal statement
namespace HarmonicGames.Projection

/-- **Theorem 6.2** (p. 36). Let `u` be a game and `φ = δ0† D u`. With respect to the norm (56):
1. the closest potential game to `u` is unique and has utilities `Π_m φ + (I - Π_m) u^m`;
2. the closest harmonic game to `u` is unique and has utilities `u^m - Π_m φ`. -/
theorem theorem_6_2 {ι : Type} [Fintype ι] [DecidableEq ι] (E : ι → Type)
    [∀ m, Fintype (E m)] [∀ m, DecidableEq (E m)] [∀ m, Nonempty (E m)]
    (u : ι → (∀ m, E m) → ℝ) (φ : HarmonicGames.Decomposition.Util E) (hφ : φ = HarmonicGames.Decomposition.potentialFunction E (toGames E u)) :
    (∀ û : ι → (∀ m, E m) → ℝ, IsClosestPotential E u û ↔
        û = fun m p => HarmonicGames.Decomposition.Pim E m φ p + (u m p - HarmonicGames.Decomposition.Pim E m (WithLp.toLp 2 (u m)) p)) ∧
      (∀ û : ι → (∀ m, E m) → ℝ, IsClosestHarmonic E u û ↔
        û = fun m p => u m p - HarmonicGames.Decomposition.Pim E m φ p) := by sorry

end HarmonicGames.Projection
Source
Candogan, Menache, Ozdaglar, Parrilo, Flows and Decompositions of Games: Harmonic and Potential Games, arXiv:1005.2405v2, p. 36, Theorem 6.2
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me