AFTD Auto-Formalizing Theoretical Domains

maxcut_single_vertex_gluing_abstract

theoremverified

For an additively separable game whose player sets cover all players and intersect only at a shared player, stability on each piece implies stability of the combined payoff: whenever any player changes, a changing player fails to improve the sum of its two piece payoffs. Each piece payoff vanishes outside its own player set.

Statement

theorem maxcut_single_vertex_gluing_abstract
    {V C : Type} (σ : V → C) (A B : Set V) (o : V)
    (hA : o ∈ A) (hB : o ∈ B)
    (hcover : ∀ v, v ∈ A ∨ v ∈ B)
    (hinter : ∀ v, v ∈ A → v ∈ B → v = o)
    (a b : (V → C) → V → ℕ)
    (ha0 : ∀ p v, v ∉ A → a p v = 0)
    (hb0 : ∀ p v, v ∉ B → b p v = 0)
    (hstableA : ∀ τ, (∃ v, v ∈ A ∧ τ v ≠ σ v) →
      ∃ v, v ∈ A ∧ τ v ≠ σ v ∧ a τ v ≤ a σ v)
    (hstableB : ∀ τ, (∃ v, v ∈ B ∧ τ v ≠ σ v) →
      ∃ v, v ∈ B ∧ τ v ≠ σ v ∧ b τ v ≤ b σ v) :
    ∀ τ, (∃ v, τ v ≠ σ v) →
      ∃ v, τ v ≠ σ v ∧ a τ v + b τ v ≤ a σ v + b σ v
Source
General gluing mechanism for the Max-k-Cut strong-equilibrium existence problem OP-85.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by contradiction: suppose there is a deviation $\tau \ne \sigma$ under which every changing player strictly increases their combined payoff $a(\tau, v) + b(\tau, v) > a(\sigma, v) + b(\sigma, v)$. Because each piece payoff vanishes outside its own player set, any player in $A \setminus \{o\}$ or $B \setminus \{o\}$ depends on only one payoff; thus any non-improving player guaranteed by piece stability must be the unique shared player $o$. Applying this to the initial deviation forces $o$ itself to have changed. Finally, applying the stability of both pieces to $o$ reveals that $o$ cannot strictly improve under either $a$ or $b$, so its combined payoff cannot strictly increase, contradicting the assumption.

  1. Under the assumption that no changing player fails to improve their combined payoff, every player who changes strategy must strictly increase their total payoff.

    Assuming classical logic, we introduce a modified strategy profile $\tau$ with at least one changed player (`hchanged`). To argue by contradiction, we suppose (`hbad`) that no changing player has a non-increasing combined payoff $a(\tau, v) + b(\tau, v) \le a(\sigma, v) + b(\sigma, v)$. It follows directly (`hgain`) that every changing player $v$ must strictly improve their total payoff: $a(\sigma, v) + b(\sigma, v) < a(\tau, v) + b(\tau, v)$.

    lines 15–21

      classical
      intro τ hchanged
      by_contra hbad
      have hgain : ∀ v, τ v ≠ σ v → a σ v + b σ v < a τ v + b τ v := by
        intro v hv
        by_contra hn
        exact hbad ⟨v, hv, by omega⟩
  2. Any changing player in $A$ whose payoff $a$ does not strictly increase must be the shared player $o$.

    Suppose $v \in A$ changes strategy and satisfies $a(\tau, v) \le a(\sigma, v)$. If $v \ne o$, then since the intersection $A \cap B$ contains only $o$ (`hinter`), $v \notin B$. The payoff function $b$ vanishes outside $B$ (`hb0`), so $b(\tau, v) = b(\sigma, v) = 0$. The strict gain inequality for $v$ then reduces to $a(\sigma, v) < a(\tau, v)$, contradicting $a(\tau, v) \le a(\sigma, v)$.

    lines 22–28

      have left_root : ∀ v, v ∈ A → τ v ≠ σ v → a τ v ≤ a σ v → v = o := by
        intro v hv hdiff hle
        by_contra hne
        have hnot : v ∉ B := fun hmem => hne (hinter v hv hmem)
        have hg := hgain v hdiff
        rw [hb0 τ v hnot, hb0 σ v hnot] at hg
        omega
  3. Any changing player in $B$ whose payoff $b$ does not strictly increase must be the shared player $o$.

    Symmetrically, suppose $v \in B$ changes strategy and satisfies $b(\tau, v) \le b(\sigma, v)$. If $v \ne o$, then $v \notin A$ by `hinter`. Since the payoff function $a$ vanishes outside $A$ (`ha0`), $a(\tau, v) = a(\sigma, v) = 0$. The strict gain inequality reduces to $b(\sigma, v) < b(\tau, v)$, contradicting $b(\tau, v) \le b(\sigma, v)$.

    lines 29–35

      have right_root : ∀ v, v ∈ B → τ v ≠ σ v → b τ v ≤ b σ v → v = o := by
        intro v hv hdiff hle
        by_contra hne
        have hnot : v ∉ A := fun hmem => hne (hinter v hmem hv)
        have hg := hgain v hdiff
        rw [ha0 τ v hnot, ha0 σ v hnot] at hg
        omega
  4. The shared player $o$ must have changed strategy ($\tau(o) \ne \sigma(o)$).

    By assumption, some player $v$ changed strategy. Because $A$ and $B$ cover all players (`hcover`), $v$ belongs to either $A$ or $B$. If $v \in A$, stability on piece $A$ (`hstableA`) provides a changing player $w \in A$ with $a(\tau, w) \le a(\sigma, w)$. By `left_root`, $w = o$, so $\tau(o) \ne \sigma(o)$. If instead $v \in B$, stability on piece $B$ (`hstableB`) similarly produces a changing player in $B$ with non-increasing payoff $b$, which by `right_root` must be $o$. Thus in either case, $\tau(o) \ne \sigma(o)$.

    lines 36–44

      have horoot : τ o ≠ σ o := by
        obtain ⟨v, hv⟩ := hchanged
        rcases hcover v with hvA | hvB
        · obtain ⟨w, hwA, hwd, hwle⟩ := hstableA τ ⟨v, hvA, hv⟩
          have : w = o := left_root w hwA hwd hwle
          simpa [this] using hwd
        · obtain ⟨w, hwB, hwd, hwle⟩ := hstableB τ ⟨v, hvB, hv⟩
          have : w = o := right_root w hwB hwd hwle
          simpa [this] using hwd
  5. The combined payoff of the shared player cannot strictly increase, yielding a contradiction.

    Because $o$ changed strategy and belongs to both $A$ and $B$ (`hA`, `hB`), we apply piece stability on $A$ to obtain a changing player $x \in A$ with $a(\tau, x) \le a(\sigma, x)$, and on $B$ to obtain $y \in B$ with $b(\tau, y) \le b(\sigma, y)$. By `left_root` and `right_root`, both $x$ and $y$ must be $o$, giving $a(\tau, o) \le a(\sigma, o)$ and $b(\tau, o) \le b(\sigma, o)$. Summing these two inequalities yields $a(\tau, o) + b(\tau, o) \le a(\sigma, o) + b(\sigma, o)$, which contradicts the strict gain inequality (`hgain`) for $o$. Linear arithmetic (`omega`) closes the goal.

    lines 45–52

      obtain ⟨x, hxA, hxd, hxle⟩ := hstableA τ ⟨o, hA, horoot⟩
      obtain ⟨y, hyB, hyd, hyle⟩ := hstableB τ ⟨o, hB, horoot⟩
      have hx : x = o := left_root x hxA hxd hxle
      have hy : y = o := right_root y hyB hyd hyle
      subst x
      subst y
      have hg := hgain o horoot
      omega

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem maxcut_single_vertex_gluing_abstract    {V C : Type} (σ : V → C) (A B : Set V) (o : V)    (hA : o ∈ A) (hB : o ∈ B)    (hcover : ∀ v, v ∈ A ∨ v ∈ B)    (hinter : ∀ v, v ∈ A → v ∈ B → v = o)    (a b : (V → C) → V → ℕ)    (ha0 : ∀ p v, v ∉ A → a p v = 0)    (hb0 : ∀ p v, v ∉ B → b p v = 0)    (hstableA : ∀ τ, (∃ v, v ∈ A ∧ τ v ≠ σ v) →      ∃ v, v ∈ A ∧ τ v ≠ σ v ∧ a τ v ≤ a σ v)    (hstableB : ∀ τ, (∃ v, v ∈ B ∧ τ v ≠ σ v) →      ∃ v, v ∈ B ∧ τ v ≠ σ v ∧ b τ v ≤ b σ v) :    ∀ τ, (∃ v, τ v ≠ σ v) →      ∃ v, τ v ≠ σ v ∧ a τ v + b τ v ≤ a σ v + b σ v := by  classical  intro τ hchanged  by_contra hbad  have hgain : ∀ v, τ v ≠ σ v → a σ v + b σ v < a τ v + b τ v := by    intro v hv    by_contra hn    exact hbad ⟨v, hv, by omega⟩  have left_root : ∀ v, v ∈ A → τ v ≠ σ v → a τ v ≤ a σ v → v = o := by    intro v hv hdiff hle    by_contra hne    have hnot : v ∉ B := fun hmem => hne (hinter v hv hmem)    have hg := hgain v hdiff    rw [hb0 τ v hnot, hb0 σ v hnot] at hg    omega  have right_root : ∀ v, v ∈ B → τ v ≠ σ v → b τ v ≤ b σ v → v = o := by    intro v hv hdiff hle    by_contra hne    have hnot : v ∉ A := fun hmem => hne (hinter v hmem hv)    have hg := hgain v hdiff    rw [ha0 τ v hnot, ha0 σ v hnot] at hg    omega  have horoot : τ o ≠ σ o := by    obtain ⟨v, hv⟩ := hchanged    rcases hcover v with hvA | hvB    · obtain ⟨w, hwA, hwd, hwle⟩ := hstableA τ ⟨v, hvA, hv⟩      have : w = o := left_root w hwA hwd hwle      simpa [this] using hwd    · obtain ⟨w, hwB, hwd, hwle⟩ := hstableB τ ⟨v, hvB, hv⟩      have : w = o := right_root w hwB hwd hwle      simpa [this] using hwd  obtain ⟨x, hxA, hxd, hxle⟩ := hstableA τ ⟨o, hA, horoot⟩  obtain ⟨y, hyB, hyd, hyle⟩ := hstableB τ ⟨o, hB, horoot⟩  have hx : x = o := left_root x hxA hxd hxle  have hy : y = o := right_root y hyB hyd hyle  subst x  subst y  have hg := hgain o horoot  omega
See it in the graphDiscuss this resultChallenge it