Theorem 4.1 — strict better responses in terminate, so a pure Nash equilibrium exists
ProvedCompDesign.theorem_4_1Throughout, is the set of agents, the budget, the private costs, and a value function satisfying Assumption 3.1: , monotone () and submodular ( whenever and ). The marginal-contribution payment is if and , and otherwise (8); agent 's utility is if and otherwise.
Theorem 4.1 (Existence of pure Nash equilibria). Let . In the game induced by the marginal contribution payment rule (8):
- every sequence of strict better responses terminates: there is no infinite sequence in which each is a strict better response from ;
- as a result, admits a pure Nash equilibrium.
This is the existence half of Main Result 2. It shows that simple best-response dynamics, run by the agents themselves, always settle.
Formalization Note A strict better response is CompDesign.IsStrictImprovement: one agent switches its participation and its own utility strictly rises.
Differences from the source:
- encoding: every sequence of strict better responses terminates → there is no f : ℕ → Finset (Fin n) with a strict better response from f t to f (t+1) for every t; reason: a sequence terminates iff it is not infinite; this is the standard well-foundedness formulation
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF import Definitions.Def_CompDesignBFM_IsPNE import Definitions.Def_CompDesign_IsStrictImprovement open CompDesignBFM
namespace CompDesign
/-- Theorem 4.1 (Existence of pure Nash equilibria), §4.1, p.17 (PDF 20) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…).
Let `max_{i∈N} c_i < B`. In the game `Γ^mc` induced by the marginal contribution payment rule (8),
every sequence of strict better responses terminates. As a result, `Γ^mc` admits a pure Nash
equilibrium.
**Formalization Note.** Assumption 3.1 (`v ∅ = 0`, monotone, submodular), `B > 0` and `c ≥ 0` are the
standing assumptions of §3.1. "Every sequence of strict better responses terminates" is stated as: there
is no infinite sequence `S₀, S₁, …` in which each `S_{t+1}` is a strict better response from `S_t`. -/
theorem theorem_4_1 {n : ℕ} (v : Finset (Fin n) → ℝ) (B : ℝ) (c : Fin n → ℝ) (hB : 0 < B)
(hv0 : v ∅ = 0) (hm : IsMonotoneSF v) (hs : IsSubmodularSF v) (hc : ∀ i, 0 ≤ c i)
(hcB : ∀ i, c i < B) :
(¬ ∃ f : ℕ → Finset (Fin n), ∀ t, IsStrictImprovement v B c (f t) (f (t + 1))) ∧
∃ S : Finset (Fin n), IsPNE v B c S := by sorry
end CompDesign
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.