Proof of Theorem 3.1, (⇐) — every Nash equilibrium of is a satisfying assignment with all clauses on (corrected: every clause nonempty)
ProvedPureNashHard.theorem_3_1_ne_shapecomputational-complexitygame-theorynash-equilibriumnp-completenessp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a CNF formula with no empty clause and a pure Nash equilibrium of . Then
- every player plays or ;
- every clause player plays and gets payoff ;
- the truth assignment of satisfies .
This is the "if" direction of the correspondence between satisfying assignments and Nash equilibria, obtained from properties P1–P4.
Differences from the source:
- correction: every 3SAT formula Φ → every clause of φ is nonempty; reason: for Φ = (∅) ∧ (X_1), X_1 = t, c_0 = u, c_1 = t is a pure Nash equilibrium of G_Φ (the empty clause player gets 2 by rule (ii) and 1 by any deviation), so P2 and the claim fail; proved in the sanity file
- encoding: a CNF formula Φ = c_1 ∧ … ∧ c_m over X_1, …, X_n → CookLevin.Formula (a list of clauses, variables natural numbers); the variable players are the distinct variables occurring in φ, the clause players the list positions of φ; reason: Lean convention of the published framework; a variable occurring in no clause has no role in the game
- encoding: actions t, f, u → indices 0, 1, 2 (actT, actF, actU); reason: Lean convention
Preamble
import Definitions.Def_PureNashHard_redGame import Definitions.Def_PureNashHard_IsPNE set_option autoImplicit false
Formal statement
namespace PureNashHard
/-- **Shape of the Nash equilibria of `G_Φ` (corrected: every clause nonempty).** Gottlob, Greco, Scarcello, *Pure Nash Equilibria: Hard and Easy Games*, JAIR 24 (2005), proof of
Theorem 3.1, p.371: "every Nash equilibrium of G should be a strategy where all players play
either t or f and all players corresponding to clauses must play t and get payoff 3, as they
are all made true by the truth assignment of their neighbors."
If no clause of `φ` is empty, then in every pure Nash equilibrium `σ` of `G_φ`:
1. every player plays `t` or `f`;
2. every clause player plays `t` and gets payoff 3;
3. the induced assignment satisfies `φ`. -/
theorem theorem_3_1_ne_shape (φ : CookLevin.Formula) (hφ : ∀ c ∈ φ, c ≠ [])
(σ : (redGame φ).Profile) (hσ : IsPNE (redGame φ) σ) :
(∀ p : Fin (redGame φ).N, (σ p).val ≠ actU) ∧
(∀ p : Fin (redGame φ).N, nVars φ ≤ p.val →
(σ p).val = actT ∧ (redGame φ).utility p σ = 3) ∧
CookLevin.Satisfies (assignOf φ σ) φ := by sorry
end PureNashHard
Source
Gottlob, Greco, Scarcello, Pure Nash Equilibria: Hard and Easy Games, JAIR 24 (2005), doi:10.1613/jair.1683, proof of Theorem 3.1, (⇐), p.371 (PDF p.15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.