adversary_forces_ratio
Given ratio r, factor α, and horizon H, an adversary forces factor α by prefix H on two agents if for every online allocator on H chores, there exists a cost profile assigning values in {1, r} to each agent and chore (not necessarily identical between the two agents) such that the resulting allocation fails to be α-MMS after every prefix.
Statement
def adversary_forces_ratio (r α : ℝ) (H : ℕ) : Prop
- Related work
- arXiv:2505.24321
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 2
- is_prefix_alpha_mms_choresAn allocation σ of m chores between two agents is α-MMS after every prefix if for every k with 1 ≤ k ≤ m, the restriction of σ to the…
- is_online_allocatorAn allocation algorithm on m goods for n agents is online if the allocation of each arriving good t depends only on the valuation vectors…
Read back from the Lean
Given real numbers r and α and a natural number H, adversary_forces_ratio r α H asserts that for every algorithm alg : (Fin 2 → Fin H → ℝ) → (Fin H → Fin 2), if alg is an online allocator for 2 agents and H chores (meaning that for any two cost profiles v and v' and any chore t : Fin H, if v and v' agree on all agents and all chores s ≤ t, then alg v t = alg v' t), then there exists a cost profile c : Fin 2 → Fin H → ℝ such that:
1. For every agent i : Fin 2 and every chore g : Fin H, c(i, g) = 1 or c(i, g) = r; and
2. The allocation σ = alg(c) does not satisfy the prefix α-MMS chores condition for horizon H, ratio α, and cost profile c (i.e., at some prefix length k with 1 ≤ k ≤ H, some agent receives a bundle of chores whose total cost strictly exceeds α times that agent's chore maximin share among the first k chores).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- An adversary forces factor alpha by horizon H if every online allocator on H chores fails to maintain alpha-MMS after every prefix on some instance with costs in {1, r}. -/ def adversary_forces_ratio (r α : ℝ) (H : ℕ) : Prop := ∀ alg, is_online_allocator 2 H alg → ∃ c : Fin 2 → Fin H → ℝ, (∀ i g, c i g = 1 ∨ c i g = r) ∧ ¬ is_prefix_alpha_mms_chores H α c (alg c)