AFTD Auto-Formalizing Theoretical Domains

maxcut_welfare

def

The social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.

Statement

def maxcut_welfare {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : ℕ
Defined in
arXiv:2610.04948 (Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games), Sec. 1
Verified
06 Oct 2026
Axioms
none listed
Built on 1
  • maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
Used by 24

Lean source view module on GitHub

/-- Social welfare of a coloring in the unweighted Max-k-Cut game: the sum of the players' utilities, which is twice the number of bichromatic edges. -/
def maxcut_welfare {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : ℕ :=
  ∑ v, maxcut_utility G σ v
See it in the graphDiscuss this resultChallenge it