AFTD Auto-Formalizing Theoretical Domains

adversary_forces_ratio

deforiginal

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)
See it in the graphDiscuss this resultChallenge it