§3.2, p. 13, proof of Theorem 3.7 — tight instance: the bluff order is g_1 > ⋯ > g_5 and the bluff run gives A_1 = {g_1, g_3, g_5}, A_2 = {g_2, g_4}
ProvedRoundRobinEq.SubmodularBluff.tight_bluff_runbluff-profilefair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1round-robintight-example
Consider the tight instance of Theorem 3.7 with (additive agent 1, OXS agent 2, and a dummy good ). Then:
- is an output of Algorithm 2, so the profile in which both agents report it is a bluff profile;
- Round-Robin on this profile gives agent 1 the bundle and agent 2 the bundle ;
Together with agent 2's deviation, this shows that the factor of Theorem 3.7 cannot be improved.
Formalization Note. Goods are ℓ - 1 : Fin 6 and agents 1, 2 are 0, 1 : Fin 2. The dummy good (value ) comes from the paper's standing convention (p. 7) and ends up in without changing any value. The order is the one Algorithm 2 produces with lexicographic tie-breaking (agent 2 is indifferent among at her second turn). The paper's "" is encoded as , under which all three claims hold.
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_bluff_run (ε₁ ε₂ ε₃ : ℝ) (h₁ : 0 < ε₁) (h₁₂ : ε₁ < ε₂) (h₂₃ : ε₂ < ε₃)
(h₃ : ε₃ < 1) :
IsGreedyOrder (tightVal ε₁ ε₂ ε₃) tightBluffOrder ∧
RoundRobinEq.CancelableBluff.roundRobin (bluff tightBluffOrder : Fin 2 → List (Fin 6)) 0 = {0, 2, 4} ∧
RoundRobinEq.CancelableBluff.roundRobin (bluff tightBluffOrder : Fin 2 → List (Fin 6)) 1 = {1, 3, 5} ∧
tightVal ε₁ ε₂ ε₃ 0 {0, 2, 4} = 4 - ε₁ - ε₃ ∧
tightVal ε₁ ε₂ ε₃ 1 {1, 3, 5} = 1 := by sorry
end RoundRobinEq.SubmodularBluff
Source
Amanatidis et al., Round-Robin Beyond Additive Agents, arXiv:2301.13652v1, p. 13, proof of Theorem 3.7 (tight instance, bluff run)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.