Theorem 3.7 — for submodular valuations the bluff profile is a 1/2-approximate PNE of Round-Robin, and 1/2 is tight
ProvedRoundRobinEq.SubmodularBluff.theorem_3_7Bound. Let agents have submodular valuation functions (normalized and non-decreasing) over goods, and let be an output of Algorithm 2. Then the bluff profile is a -approximate pure Nash equilibrium of Mechanism 1 (Round-Robin): for every agent and every ranking ,
Tightness. For every there is an instance with submodular valuations (and ) in which the bluff profile is not a -approximate PNE.
This is the main result of §3.2: for submodular agents exact equilibria may fail to exist (Proposition 3.4), but the bluff profile is always within a factor of a best response, and no better factor holds for it in general.
Formalization Note. The bound is stated for every greedy order h (IsGreedyOrder v h), that is, for every tie-breaking of Algorithm 2; the paper's lexicographic bluff profile is one of them. The standing simplification (p. 7) is a hypothesis; the paper calls it without loss of generality by adding dummy goods, a reduction this statement does not formalize. In the tightness part the instance is existentially quantified with agents Fin n and goods Fin m, , and it must admit a greedy order; the conclusion holds for every greedy order of the instance. The paper's instance has goods for agents and needs a dummy sixth good to satisfy .
import Mathlib import Definitions.Def_RoundRobinEq_SubmodularBluff_Setting import Definitions.Def_RoundRobinEq_SubmodularBluff_Bluff
namespace RoundRobinEq.SubmodularBluff
theorem theorem_3_7 :
(∀ {n : ℕ} [NeZero n] {M : Type} [Fintype M] [DecidableEq M] (k : ℕ),
Fintype.card M = k * n →
∀ v : Fin n → Finset M → ℝ, (∀ i, RoundRobinEq.CancelableBluff.IsValuation (v i) ∧ IsSubmodular (v i)) →
∀ h : List M, IsGreedyOrder v h → RoundRobinEq.CancelableBluff.IsApproxPNE (1 / 2) v (bluff h)) ∧
(∀ ε : ℝ, 0 < ε →
∃ (n m k : ℕ) (_ : NeZero n) (_ : m = k * n) (v : Fin n → Finset (Fin m) → ℝ),
(∀ i, RoundRobinEq.CancelableBluff.IsValuation (v i) ∧ IsSubmodular (v i)) ∧
(∃ h : List (Fin m), IsGreedyOrder v h) ∧
∀ h : List (Fin m), IsGreedyOrder v h → ¬ RoundRobinEq.CancelableBluff.IsApproxPNE (1 / 2 + ε) v (bluff h)) := by sorry
end RoundRobinEq.SubmodularBluff
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.