§3.2, pp. 13–14, proof of Theorem 3.7 — tight instance: agent 2’s best deviation value is 2 − ε_1 − ε_2, attained by g_3 > g_4 > g_1 > g_2 > g_5
ProvedRoundRobinEq.SubmodularBluff.tight_deviationbluff-profilefair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1round-robintight-example
Consider the tight instance of Theorem 3.7 with , and let agent 1 report the bluff order . Then (i) whatever ranking agent 2 reports, the bundle she receives from Round-Robin satisfies
and (ii) this maximum is attained: if agent 2 reports
which is a ranking, then Round-Robin gives her the goods and .
Since in the bluff run, agent 2 improves her value by a factor , which tends to as the 's vanish.
Formalization Note. The page assumes ; here "" is read as . Some such quantitative reading is needed for the maximum: agent 2’s best deviation value is , so the maximum claim fails when (e.g. ), and rules this out. The dummy good is the paper's device for (p. 7).
Preamble
import Mathlib import Definitions.Def_RoundRobinEq_SubmodularBluff_Setting import Definitions.Def_RoundRobinEq_SubmodularBluff_Bluff import Definitions.Def_RoundRobinEq_SubmodularBluff_TightInstance
Formal statement
namespace RoundRobinEq.SubmodularBluff
theorem tight_deviation (ε₁ ε₂ ε₃ : ℝ) (h₁ : 0 < ε₁) (h₁₂ : ε₁ < ε₂) (h₂₃ : ε₂ < ε₃)
(h₃ : ε₃ ≤ 1 / 2) :
(∀ τ : List (Fin 6), RoundRobinEq.CancelableBluff.IsRanking τ →
tightVal ε₁ ε₂ ε₃ 1 (RoundRobinEq.CancelableBluff.roundRobin (Function.update (bluff tightBluffOrder : Fin 2 → List (Fin 6)) 1 τ) 1) ≤ 2 - ε₁ - ε₂) ∧
RoundRobinEq.CancelableBluff.IsRanking tightDeviation ∧
RoundRobinEq.CancelableBluff.roundRobin (Function.update (bluff tightBluffOrder : Fin 2 → List (Fin 6)) 1 tightDeviation) 1 = {2, 3, 5} ∧
tightVal ε₁ ε₂ ε₃ 1 {2, 3, 5} = 2 - ε₁ - ε₂ := by sorry
end RoundRobinEq.SubmodularBluff
Source
Amanatidis et al., Round-Robin Beyond Additive Agents, arXiv:2301.13652v1, pp. 13–14, proof of Theorem 3.7 (tight instance, agent 2's deviation)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.