AFTD Auto-Formalizing Theoretical Domains

round_robin_two_mul_add_one_deviation_certificate

theoremverified

Round-Robin with n agents and 2n+1 goods, any reports, agent i ≠ 0: for some good g of agent 0's bundle B_0 (its first pick a1), either some deviation r of agent i alone gets i all of B_0 ∖ {g}, or two deviations r1, r2 of agent i give bundles D1, D2 that together cover B_i + (B_0 ∖ {g}) with multiplicity (every good counted in B_i and in B_0 ∖ {g} is counted at least as often in D1 and D2). A valuation-free certificate for EF1 of i towards agent 0 at an equilibrium.

Statement

theorem round_robin_two_mul_add_one_deviation_certificate (n : ℕ) [NeZero n]
    (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (hi : i ≠ 0) :
    ∃ g ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0,
      (∃ r : Fin (2 * n + 1) ≃ Fin (2 * n + 1),
        picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g} ⊆
          picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
            (Function.update rank i r) i) ∨
      (∃ r₁ r₂ : Fin (2 * n + 1) ≃ Fin (2 * n + 1), ∀ x : Fin (2 * n + 1),
        (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i then 1 else 0) +
          (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g}
            then 1 else 0) ≤
        (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
            (Function.update rank i r₁) i then 1 else 0) +
          (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
            (Function.update rank i r₂) i then 1 else 0 : ℕ))
Source
step for round_robin_pne_envy_zero_ef1_of_two_mul_add_one (research thread RT-3, the threshold question from arXiv:2610.23686 Proposition 1)
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 13
Used by 1

The proof, explained

The proof establishes a valuation-free certificate of envy-freeness up to one good (EF1) for agent i against agent 0 by designating agent 0's initial pick a1 as the good to drop, leaving B_0 ∖ {a1} = {a2, a3}. It invokes a structural dichotomy (round_robin_two_mul_add_one_cover_pairs) showing that agent i can either obtain both {a2, a3} with a single deviation, or cover {a2, a3, b1, b2} across two deviations. In the single-deviation case, the remaining bundle B_0 ∖ {a1} is directly covered. In the two-deviation case, because agent i and agent 0 have disjoint bundles, every good in B_i ∪ (B_0 ∖ {a1}) has multiplicity 1, so covering their union pointwise implies covering them with multiplicity via a boolean indicator inequality.

  1. For mutually disjoint propositions P and Q, if P ∨ Q implies R ∨ S, then the sum of their indicator functions is at most the sum of the indicator functions of R and S. automation

    By case-splitting on the truth values of P, Q, R, and S, if neither P nor Q holds, the left-hand side is 0 ≤ RHS. If one of P or Q holds (both cannot hold as ¬(P ∧ Q)), the left-hand side is 1; then P ∨ Q holds, which implies R ∨ S, ensuring at least one of R or S holds and the right-hand side is at least 1. Exhaustive truth-table checking via simp_all closes all cases.

    lines 1–6

    private lemma indicator_cover (P Q R S : Prop) [Decidable P] [Decidable Q]
        [Decidable R] [Decidable S] (hd : ¬(P ∧ Q)) (hc : P ∨ Q → R ∨ S) :
        (if P then 1 else 0) + (if Q then 1 else 0) ≤
          (if R then 1 else 0) + (if S then 1 else 0 : ℕ) := by
      by_cases hP : P <;> by_cases hQ : Q <;> by_cases hR : R <;> by_cases hS : S <;>
        simp_all
  2. Agent 0 receives three distinct goods {a1, a2, a3} and agent i receives two distinct goods {b1, b2}.

    Applying round_robin_two_mul_add_one_outcome_structure establishes that agent 0's bundle consists of its first pick a1 = rank(0)(0), round-2 pick a2, and round-3 pick a3, while agent i (i ≠ 0) receives two picks b1 and b2.

    lines 23–26

    uses round_robin_two_mul_add_one_outcome_structure

      classical
      obtain ⟨a2,a3,b1,b2,hf2,hm2,hf3,hm3,hB0,hBi,h02,h03,h23,h12,_,_⟩ :=
        round_robin_two_mul_add_one_outcome_structure n rank i hi
      let a1 := rank 0 ⟨0,by omega⟩
  3. Removing agent 0's first pick a1 from its bundle leaves exactly the remaining two goods {a2, a3}. automation

    Substituting B_0 = {a1, a2, a3} and taking the set difference with {a1} yields {a2, a3}, since a1 is distinct from a2 and a3. Aesop completes the set-theoretic equivalence.

    lines 27–33

    uses Finset.mem_sdiff, Finset.mem_insert, Finset.mem_singleton

      have hremove : picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1} =
          {a2,a3} := by
        rw [hB0]
        ext x
        simp only [Finset.mem_sdiff,Finset.mem_insert,Finset.mem_singleton]
        dsimp only [a1]
        aesop
  4. The first pick a1 belongs to agent 0's bundle and serves as the witness good g.

    We instantiate the existential quantifier for the removed good g with a1, and verify that a1 ∈ B_0 = {a1, a2, a3} by membership in an inserted set.

    lines 34–36

    uses Finset.mem_insert_self

      refine ⟨a1,?_,?_⟩
      · rw [hB0]
        exact Finset.mem_insert_self _ _
  5. If agent i can secure both {a2, a3} in a single deviation, the first alternative of the certificate holds.

    By round_robin_two_mul_add_one_cover_pairs, agent i either has a single deviation r securing {a2, a3}, or two deviations covering all four goods {a2, a3, b1, b2}. In the former case, because B_0 ∖ {a1} = {a2, a3}, deviation r secures all of B_0 ∖ {a1}.

    lines 37–39

    uses round_robin_two_mul_add_one_cover_pairs, Or.inl

      rcases round_robin_two_mul_add_one_cover_pairs n rank i hi a1 a2 a3 b1 b2 rfl ⟨hf2,hm2⟩ ⟨hf3,hm3⟩
        hB0 hBi ⟨h02,h03,h23⟩ with ⟨r,hr⟩ | ⟨r₁,r₂,hr⟩
      · exact Or.inl ⟨r,by rw [hremove]; exact hr⟩
  6. In the two-deviation case, the union of the two deviated bundles covers B_i ∪ (B_0 ∖ {a1}).

    From the second alternative of round_robin_two_mul_add_one_cover_pairs, deviations r1 and r2 satisfy {a2, a3, b1, b2} ⊆ D1 ∪ D2. Since B_i = {b1, b2} and B_0 ∖ {a1} = {a2, a3}, every element of B_i ∪ (B_0 ∖ {a1}) belongs to D1 ∪ D2.

    lines 40–49

    uses Or.inr, Finset.mem_union, Finset.mem_insert, Finset.mem_singleton

      · refine Or.inr ⟨r₁,r₂,?_⟩
        have hcov : picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∪
            (picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1}) ⊆
            picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₁) i ∪
            picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₂) i := by
          rw [hBi,hremove]
          intro x hx
          apply hr
          simp only [Finset.mem_union,Finset.mem_insert,Finset.mem_singleton] at hx ⊢
          tauto
  7. For every good x, the multiplicity of x in B_i plus B_0 ∖ {a1} is at most its multiplicity in D1 plus D2.

    Because i ≠ 0, picking_sequence_outcome_pairwise_disjoint ensures B_i and B_0 are disjoint, so no good belongs to both B_i and B_0 ∖ {a1}. Together with the union coverage B_i ∪ (B_0 ∖ {a1}) ⊆ D1 ∪ D2, indicator_cover applied pointwise to each good x yields the indicator inequality (multiplicity bound).

    lines 50–61

    uses picking_sequence_outcome_pairwise_disjoint, Finset.disjoint_left.mp, Finset.mem_sdiff.mp, Finset.mem_union.mp, Finset.mem_union.mpr, indicator_cover

        have hd := picking_sequence_outcome_pairwise_disjoint (round_robin_sequence n (2*n+1)) rank hi
        intro x
        have hdis : ¬(x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∧
            x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1}) := by
          rintro ⟨hxi,hx0⟩
          exact Finset.disjoint_left.mp hd hxi (Finset.mem_sdiff.mp hx0).1
        have hc : x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∨
            x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1} →
            x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₁) i ∨
            x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₂) i :=
          fun hh => Finset.mem_union.mp (hcov (Finset.mem_union.mpr hh))
        exact indicator_cover _ _ _ _ hdis hc
indicator_cover
If P and Q are mutually exclusive propositions (¬(P ∧ Q)) and P ∨ Q implies R ∨ S, then the sum of indicators of P and Q is at most the sum of indicators of R and S.
round_robin_two_mul_add_one_outcome_structure
In a round-robin picking sequence with n agents and 2n+1 goods, agent 0 receives three distinct goods {a1, a2, a3} and any agent i ≠ 0 receives two distinct goods {b1, b2}.
Finset.mem_sdiff
An element belongs to the set difference s ∖ t if and only if it belongs to s and does not belong to t.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.mem_insert_self
An element a belongs to insert a s.
round_robin_two_mul_add_one_cover_pairs
In round-robin with 2n+1 goods, either agent i has a deviation securing both {a2, a3}, or two deviations whose combined bundles cover {a2, a3, b1, b2}.
Or.inl
From a proof of A, infer the disjunction A ∨ B.
Or.inr
From a proof of B, infer the disjunction A ∨ B.
Finset.mem_union
An element belongs to the union s ∪ t if and only if it belongs to s or to t.
picking_sequence_outcome_pairwise_disjoint
In any picking sequence, the bundles allocated to distinct agents are disjoint.
Finset.disjoint_left.mp
If two sets are disjoint, any element in the first set is not in the second set.
Finset.mem_sdiff.mp
If an element belongs to s ∖ t, it belongs to s and not to t.
Finset.mem_union.mp
If an element belongs to s ∪ t, it belongs to s or to t.
Finset.mem_union.mpr
If an element belongs to s or to t, it belongs to s ∪ t.

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

private lemma indicator_cover (P Q R S : Prop) [Decidable P] [Decidable Q]    [Decidable R] [Decidable S] (hd : ¬(P ∧ Q)) (hc : P ∨ Q → R ∨ S) :    (if P then 1 else 0) + (if Q then 1 else 0) ≤      (if R then 1 else 0) + (if S then 1 else 0 : ℕ) := by  by_cases hP : P <;> by_cases hQ : Q <;> by_cases hR : R <;> by_cases hS : S <;>    simp_alltheorem round_robin_two_mul_add_one_deviation_certificate (n : ℕ) [NeZero n]    (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (hi : i ≠ 0) :    ∃ g ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0,      (∃ r : Fin (2 * n + 1) ≃ Fin (2 * n + 1),        picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g} ⊆          picking_sequence_outcome (round_robin_sequence n (2 * n + 1))            (Function.update rank i r) i) ∨      (∃ r₁ r₂ : Fin (2 * n + 1) ≃ Fin (2 * n + 1), ∀ x : Fin (2 * n + 1),        (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i then 1 else 0) +          (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 \ {g}            then 1 else 0) ≤        (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1))            (Function.update rank i r₁) i then 1 else 0) +          (if x ∈ picking_sequence_outcome (round_robin_sequence n (2 * n + 1))            (Function.update rank i r₂) i then 1 else 0 : ℕ)) := by  classical  obtain ⟨a2,a3,b1,b2,hf2,hm2,hf3,hm3,hB0,hBi,h02,h03,h23,h12,_,_⟩ :=    round_robin_two_mul_add_one_outcome_structure n rank i hi  let a1 := rank 0 ⟨0,by omega⟩  have hremove : picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1} =      {a2,a3} := by    rw [hB0]    ext x    simp only [Finset.mem_sdiff,Finset.mem_insert,Finset.mem_singleton]    dsimp only [a1]    aesop  refine ⟨a1,?_,?_⟩  · rw [hB0]    exact Finset.mem_insert_self _ _  rcases round_robin_two_mul_add_one_cover_pairs n rank i hi a1 a2 a3 b1 b2 rfl ⟨hf2,hm2⟩ ⟨hf3,hm3⟩    hB0 hBi ⟨h02,h03,h23⟩ with ⟨r,hr⟩ | ⟨r₁,r₂,hr⟩  · exact Or.inl ⟨r,by rw [hremove]; exact hr⟩  · refine Or.inr ⟨r₁,r₂,?_⟩    have hcov : picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∪        (picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1}) ⊆        picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₁) i ∪        picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₂) i := by      rw [hBi,hremove]      intro x hx      apply hr      simp only [Finset.mem_union,Finset.mem_insert,Finset.mem_singleton] at hx ⊢      tauto    have hd := picking_sequence_outcome_pairwise_disjoint (round_robin_sequence n (2*n+1)) rank hi    intro x    have hdis : ¬(x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∧        x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1}) := by      rintro ⟨hxi,hx0⟩      exact Finset.disjoint_left.mp hd hxi (Finset.mem_sdiff.mp hx0).1    have hc : x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank i ∨        x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) rank 0 \ {a1} →        x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₁) i ∨        x ∈ picking_sequence_outcome (round_robin_sequence n (2*n+1)) (Function.update rank i r₂) i :=      fun hh => Finset.mem_union.mp (hcov (Finset.mem_union.mpr hh))    exact indicator_cover _ _ _ _ hdis hc
See it in the graphDiscuss this resultChallenge it