Lemma A.1 — the sum of over a set of profiles is minus the flow leaving the set
ProvedHarmonicGames.UniformMixed.lemma_A_1game-theorygraph-flowsharmonic-gamesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the game graph of a finite game (nodes: strategy profiles; adjacent iff they differ in exactly one player's strategy), the space of edge flows on it with the inner product , and the adjoint of the combinatorial gradient . For every edge flow and every set of strategy profiles , with complement ,
The identity expresses the total divergence over a set of nodes as the net flow across its boundary; in the paper it turns the harmonic condition into the payoff identity of Lemma 5.2.
Formalization Note is Mathlib's LinearMap.adjoint for the inner products (7), including the factor ; without it the left side would be off by a factor . is a Finset of profiles.
Preamble
import Mathlib import Definitions.Def_HarmonicGames_Decomposition_Games import Definitions.Def_HarmonicGames_GenericPure_Games
Formal statement
namespace HarmonicGames.UniformMixed
/-- **Lemma A.1** (p. 43): for every edge flow `X̂ ∈ C1` on the game graph and every set of
strategy profiles `Ŝ ⊂ E`, `∑_{p ∈ Ŝ} (δ0* X̂)(p) = -∑_{p ∈ Ŝ} ∑_{q ∈ Ŝᶜ} X̂(p,q)`, where
`δ0*` is the adjoint of the combinatorial gradient for the inner products (7). -/
theorem lemma_A_1 {ι : Type} [Fintype ι] [DecidableEq ι] (E : ι → Type) [∀ m, Fintype (E m)]
[∀ m, DecidableEq (E m)]
(X : HarmonicGames.Decomposition.Flow E) (S : Finset (∀ k, E k)) :
∑ p ∈ S, (LinearMap.adjoint (HarmonicGames.Decomposition.delta0 (HarmonicGames.Decomposition.gameGraph E)) X) p = -∑ p ∈ S, ∑ q ∈ Sᶜ, X p q := by sorry
end HarmonicGames.UniformMixed
Source
Candogan, Menache, Ozdaglar, Parrilo, Flows and Decompositions of Games: Harmonic and Potential Games, arXiv:1005.2405v2, p. 43, Appendix A, Lemma A.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.