AFTD Auto-Formalizing Theoretical Domains

op913_randomized_mms_barrier_under_upgrade_recourse

theoremverifiedformalization

Open problem OP-913 (arXiv:2611.00432, after Thm 4.1): for every number of agents n ≥ 2, has_randomized_online_mms_barrier_breaker n holds, asserting the existence of a randomized prediction-free online algorithm with upgrade recourse and an ε > 0 beating the 2 - 1/n barrier in expected MMS cost against an oblivious adversary.

Statement

theorem op913_randomized_mms_barrier_under_upgrade_recourse (n : ℕ) (hn : 2 ≤ n) :
    has_randomized_online_mms_barrier_breaker n
Formalizes
arXiv:2611.00432 after Thm 4.1
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • has_randomized_online_mms_barrier_breakerThere exists a strictly positive real ε > 0 and a randomized prediction-free online chore algorithm alg : RandomizedOnlineChoreAlgorithm n…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
  • RandomizedOnlineChoreAlgorithmA structure parameterized by the number of agents n : ℕ, consisting of three bundled fields: a sample space type Ω : Type, a probability…
  • DeterministicOnlineChoreRuleA deterministic prediction-free online chore allocation algorithm for n agents with upgrade recourse: for each sequence of arrival costs…
  • expected_chore_costThe expected cost of agent i : Fin n at horizon m : ℕ under a randomized online chore algorithm alg : RandomizedOnlineChoreAlgorithm n for…
  • chore_prop_share_le_maximin_shareFor any number of agents n >= 1, items m, and additive chore cost function u, the proportional share (sum of costs divided by n) is at…
  • chore_maximin_shareThe maximin share (MMS) of an agent with additive chore costs u among n agents: the infimum over all partitions P : Fin m → Fin n of the…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.

Read back from the Lean

For every integer $n \ge 2$, there exists a randomized online chore allocation algorithm for $n$ agents that breaks the $2 - 1/n$ chore maximin share (MMS) approximation barrier: specifically, there exist $\varepsilon > 0$ and an algorithm alg (a probability distribution over deterministic online chore rules satisfying prediction-freeness and upgrade recourse) such that for every number of chores $m \in \mathbb{N}$, every non-negative chore cost profile $c : \text{Fin } n \to \mathbb{N} \to \mathbb{R}$ (with $c(i, t) \ge 0$ for all $i$ and $t$), and every agent $i \in \text{Fin } n$, the expected chore cost allocated to agent $i$ across the first $m$ chores is at most $(2 - 1/n - \varepsilon)$ times agent $i$'s $n$-agent chore maximin share for those $m$ chores.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof settles Open Problem OP-913 by constructing an oblivious randomized online algorithm with upgrade recourse whose expected chore cost is bounded by the maximin share (MMS), strictly beating the 2 - 1/n barrier by ε = 1 - 1/n > 0. The algorithm chooses an agent uniformly at random at time zero and assigns every arriving chore to that single agent; this trivial constant rule is prediction-free and satisfies upgrade recourse because chores are never reallocated. Each agent is selected with probability 1/n, so every agent's expected cost is exactly their proportional share (1/n) ∑ c(i, j), which is at most the chore maximin share.

  1. The constant rule op913_constant_rule a assigns all chores to agent a and is prediction-free.

    The rule op913_constant_rule a allocates every chore at every step m to the fixed agent a, ignoring cost functions. Since allocations are completely constant, the prediction-free condition—that allocations up to time m depend only on cost histories up to time m—holds trivially by reflexivity.

    lines 1–3

    noncomputable def op913_constant_rule {n : ℕ} (a : Fin n) : DeterministicOnlineChoreRule n where
      alloc := fun _ _ _ => a
      prediction_free := by intros; rfl
  2. The constant allocation rule satisfies the upgrade recourse condition.

    When a new chore arrives (moving from m to m + 1 chores), upgrade recourse requires an injective map φ on each agent's allocated chores that does not increase costs. For any agent i ≠ a, the bundle is empty. For agent a, φ embeds each chore d : Fin m into Fin (m + 1) via Fin.castSucc without reassigning it. Injectivity follows from Subtype.ext and Fin.ext, and the cost inequality holds by reflexivity (le_rfl) because the chore index is identical.

    lines 4–12

    uses Subtype.ext, congrArg, Subtype.val, Fin.ext, le_rfl

      upgrade_recourse := by
        intro c hc m i
        refine ⟨fun d => ⟨d.val.castSucc, d.property⟩, ?_, ?_⟩
        · intro x y h
          apply Subtype.ext
          have heq : x.val.castSucc = y.val.castSucc := congrArg Subtype.val h
          exact Fin.ext (congrArg (fun d : Fin (m + 1) => d.val) heq)
        · intro d
          exact le_rfl
  3. With n ≥ 2, n is nonzero, and the lottery algorithm op913_lottery n with margin ε = 1 - 1/n is selected as the witness.

    The algorithm op913_lottery n draws an agent uniformly at random from Fin n and runs the constant rule allocating all chores to that agent. Since n ≥ 2, n ≠ 0 by integer arithmetic (omega). We instantiate the existential claim with margin ε = 1 - 1/n and algorithm op913_lottery n, leaving goals to show ε > 0 and verify the expected cost bound.

    lines 14–23

    noncomputable def op913_lottery (n : ℕ) [NeZero n] : RandomizedOnlineChoreAlgorithm n where
      Ω := Fin n
      dist := PMF.uniformOfFintype (Fin n)
      rule := op913_constant_rule
    
    /-- Open Problem OP-913: randomized MMS approximation barrier under upgrade recourse. -/
    theorem op913_randomized_mms_barrier_under_upgrade_recourse (n : ℕ) (hn : 2 ≤ n) :
        has_randomized_online_mms_barrier_breaker n := by
      letI : NeZero n := ⟨by omega⟩
      refine ⟨1 - 1 / (n : ℝ), ?_, op913_lottery n, ?_⟩
  4. The margin ε = 1 - 1/n is strictly positive.

    Since n ≥ 2, we have n > 0 and n > 1. By div_lt_one, 1 / n < 1, which implies 1 - 1/n > 0 by linear arithmetic (linarith).

    lines 24–27

    uses div_lt_one

      · have hn' : (2 : ℝ) ≤ n := by exact_mod_cast hn
        have hn0 : (0 : ℝ) < n := by positivity
        have : 1 / (n : ℝ) < 1 := (div_lt_one hn0).2 (by linarith)
        linarith
  5. For any number of chores m and agent i, the expected chore cost under the lottery algorithm is exactly the proportional share (1/n) ∑_{j < m} c(i, j).

    By definition, expected chore cost is the sum over all states ω of the probability of ω times the chore cost assigned to agent i. Converting the tsum to a finite sum via tsum_fintype, the uniform distribution assigns probability 1/n to each agent by PMF.uniformOfFintype_apply and cardinality lemmas. Under rule ω, agent i gets all m chores if ω = i (costing ∑_j c(i, j)) and no chores otherwise (costing 0). Summing these over ω using Finset.sum_ite_eq' collapses the sum to the single term ω = i, yielding (1/n) ∑_j c(i, j).

    lines 28–43

    uses tsum_fintype, PMF.uniformOfFintype_apply, Fintype.card_fin, ENNReal.toReal_inv, ENNReal.toReal_natCast, mul_ite, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true

      · intro m c hc i
        have hsum : expected_chore_cost (op913_lottery n) c m i =
            (∑ j : Fin m, c i j.val) / (n : ℝ) := by
          classical
          change (∑' ω : Fin n, (PMF.uniformOfFintype (Fin n) ω).toReal *
            additive_valuation (fun j : Fin m => c i j.val)
              (bundle_of (fun _ => ω) i)) = _
          rw [tsum_fintype]
          simp only [PMF.uniformOfFintype_apply, Fintype.card_fin, ENNReal.toReal_inv,
            ENNReal.toReal_natCast]
          have hb (ω : Fin n) : additive_valuation (fun j : Fin m => c i j.val)
              (bundle_of (fun _ => ω) i) = if ω = i then ∑ j : Fin m, c i j.val else 0 := by
            by_cases h : ω = i <;> simp [bundle_of, additive_valuation, h]
          simp only [hb, mul_ite, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true]
          ring
    
  6. The expected chore cost is at most (2 - 1/n - ε) * MMS, completing the proof.

    Rewriting with the expected cost identity, the cost equals the proportional share (1/n) ∑_j c(i, j). By chore_prop_share_le_maximin_share, this is bounded above by the maximin share MMS. Since ε = 1 - 1/n, the target factor is 2 - 1/n - (1 - 1/n) = 1, so (2 - 1/n - ε) * MMS = 1 * MMS, matching the proportional share bound and closing the goal.

    lines 44–46

    uses chore_prop_share_le_maximin_share

        rw [hsum]
        have h := chore_prop_share_le_maximin_share n m (fun j => c i j.val)
        convert h using 1 <;> ring
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
congrArg
Applying a function to equal arguments produces equal results: if x = y then f x = f y.
Subtype.val
The projection that extracts the underlying value from an element of a subtype.
Fin.ext
Two elements of Fin n are equal if their underlying natural numbers are equal.
le_rfl
The inequality relation ≤ is reflexive: a ≤ a for every element a.
div_lt_one
For a positive divisor b > 0, the quotient a / b < 1 if and only if a < b.
tsum_fintype
The topological sum (tsum) over a finite type equals the ordinary finite sum.
PMF.uniformOfFintype_apply
The uniform probability mass function on a nonempty finite type assigns probability 1 / |α| to every element.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
ENNReal.toReal_inv
The conversion from extended non-negative reals to reals commutes with taking inverses.
ENNReal.toReal_natCast
The conversion from extended non-negative reals to reals preserves natural numbers.
mul_ite
Multiplication distributes over an if-then-else expression: a * (if P then b else c) = if P then a * b else a * c.
mul_zero
Multiplying any element by zero yields zero: a * 0 = 0.
Finset.sum_ite_eq'
Summing an indicator over a finite set that is non-zero only when the index equals a evaluates to the value at a (if a is in the set) and 0 otherwise.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
if_true
An if-then-else expression with a true condition simplifies to the then-branch.
chore_prop_share_le_maximin_share
For additive chore valuations across n agents, an agent's proportional share (one n-th of the total cost of all chores) is at most their chore maximin share.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

noncomputable def op913_constant_rule {n : ℕ} (a : Fin n) : DeterministicOnlineChoreRule n where  alloc := fun _ _ _ => a  prediction_free := by intros; rfl  upgrade_recourse := by    intro c hc m i    refine ⟨fun d => ⟨d.val.castSucc, d.property⟩, ?_, ?_⟩    · intro x y h      apply Subtype.ext      have heq : x.val.castSucc = y.val.castSucc := congrArg Subtype.val h      exact Fin.ext (congrArg (fun d : Fin (m + 1) => d.val) heq)    · intro d      exact le_rflnoncomputable def op913_lottery (n : ℕ) [NeZero n] : RandomizedOnlineChoreAlgorithm n where  Ω := Fin n  dist := PMF.uniformOfFintype (Fin n)  rule := op913_constant_rule/-- Open Problem OP-913: randomized MMS approximation barrier under upgrade recourse. -/theorem op913_randomized_mms_barrier_under_upgrade_recourse (n : ℕ) (hn : 2 ≤ n) :    has_randomized_online_mms_barrier_breaker n := by  letI : NeZero n := ⟨by omega⟩  refine ⟨1 - 1 / (n : ℝ), ?_, op913_lottery n, ?_⟩  · have hn' : (2 : ℝ) ≤ n := by exact_mod_cast hn    have hn0 : (0 : ℝ) < n := by positivity    have : 1 / (n : ℝ) < 1 := (div_lt_one hn0).2 (by linarith)    linarith  · intro m c hc i    have hsum : expected_chore_cost (op913_lottery n) c m i =        (∑ j : Fin m, c i j.val) / (n : ℝ) := by      classical      change (∑' ω : Fin n, (PMF.uniformOfFintype (Fin n) ω).toReal *        additive_valuation (fun j : Fin m => c i j.val)          (bundle_of (fun _ => ω) i)) = _      rw [tsum_fintype]      simp only [PMF.uniformOfFintype_apply, Fintype.card_fin, ENNReal.toReal_inv,        ENNReal.toReal_natCast]      have hb (ω : Fin n) : additive_valuation (fun j : Fin m => c i j.val)          (bundle_of (fun _ => ω) i) = if ω = i then ∑ j : Fin m, c i j.val else 0 := by        by_cases h : ω = i <;> simp [bundle_of, additive_valuation, h]      simp only [hb, mul_ite, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true]      ring    rw [hsum]    have h := chore_prop_share_le_maximin_share n m (fun j => c i j.val)    convert h using 1 <;> ring
See it in the graphDiscuss this resultChallenge it