AFTD Auto-Formalizing Theoretical Domains

efx_anchor_family_perturbation_exists

theoremverified

There are binary exponent permutations in which each original agent’s own r anchors receive higher exponents than all other anchors.

Statement

theorem efx_anchor_family_perturbation_exists (r s : ℕ) (hr : 0 < r) (hs : 2 ≤ s) :
  ∃ p : Fin 4 → Fin ((7+(r+r+r))+s) → ℕ,
    (∀ i, Function.Injective (p i)) ∧
    (∀ i g, p i g < (7+(r+r+r))+s) ∧
    (∀ (i : Fin 3) (a b : Fin (r+r+r)),
      efx_anchor_family_start r s (Fin.castAdd s (Fin.natAdd 7 a)) = i.castSucc.castSucc →
      efx_anchor_family_start r s (Fin.castAdd s (Fin.natAdd 7 b)) ≠ i.castSucc.castSucc →
      p i.castSucc (Fin.castAdd s (Fin.natAdd 7 b)) < p i.castSucc (Fin.castAdd s (Fin.natAdd 7 a)))
Source
Nondegenerate arbitrary-size OP-7 Pareto obstruction, binary perturbation and experiment 11514.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • efx_anchor_family_startKeep the original seven-good partial allocation, assign r anchors to each original agent in order, and give all s locked goods to agent 3;…

The proof, explained

First, a preliminary lemma identifies the initial assignment of each anchor item directly from its index. Then, the theorem is proved by explicitly constructing a family of permutations p_i of the 7 + 3r + s items for each agent i. For each of the first three agents i ∈ {0, 1, 2}, the permutation p_i leaves goods preceding agent i's anchors unchanged, shifts agent i's own r anchors to the highest positions [7 + 2r + s, 7 + 3r + s), and shifts all subsequent goods down by r. For agent 3, p_3 is the identity. Injectivity, bounds, and the condition that each agent's own anchors receive strictly higher values than all other anchors are verified by splitting on the piecewise intervals and applying linear integer arithmetic.

  1. In the auxiliary lemma `efx_anchor_family_perturbation_exists_start_anchor`, the initial assignment of each anchor item a is computed in terms of whether a < r, r ≤ a < 2r, or 2r ≤ a.

    Unfolding `efx_anchor_family_start` expresses the initial allocation as nested `Fin.addCases`. Because anchor items are injected into the domain via `Fin.castAdd s` followed by `Fin.natAdd 7 a`, rewriting with `Fin.addCases_left` and `Fin.addCases_right` simplifies the nested structure, yielding the explicit piecewise case split over the index of anchor a.

    lines 11–12

    uses efx_anchor_family_start, Fin.addCases_left, Fin.addCases_right

      dsimp [efx_anchor_family_start]
      rw [Fin.addCases_left, Fin.addCases_right]
  2. The candidate permutation family p is supplied, reducing the theorem to injectivity, bounds, and the anchor priority condition.

    We witness the existential quantifier using the explicit piecewise function `efx_anchor_family_perturbation_exists_p r s`. Using `refine`, this reduces the goal to three subgoals: showing that each p i is injective, that every image value is strictly bounded by 7 + 3r + s, and that each original agent i ∈ Fin 3 ranks their own anchors higher than anchors belonging to other agents.

    line 22

    uses efx_anchor_family_perturbation_exists_p

      refine ⟨fun i g => efx_anchor_family_perturbation_exists_p r s i g, ?_, ?_, ?_⟩
  3. For each agent i, the map p i is injective.

    Fixing an agent i and two item indices x and y with p i x = p i y, injectivity reduces by `Fin.ext` to proving x = y as natural numbers. We case split on the four agents i ∈ Fin 4. For agents 0, 1, and 2, unfolding the piecewise definition partitions the items into three intervals whose image ranges are mutually disjoint, and on each interval the map is strictly increasing; linear integer arithmetic (`omega`) closes all branches after splitting on the `if` conditions. For agent 3, p 3 is the identity map, so x = y is immediate.

    lines 23–29

    uses Fin.ext, efx_anchor_family_perturbation_exists_p

      · intro i ⟨x, hx⟩ ⟨y, hy⟩ h
        apply Fin.ext
        fin_cases i
        · dsimp [efx_anchor_family_perturbation_exists_p] at h ⊢; split_ifs at h <;> omega
        · dsimp [efx_anchor_family_perturbation_exists_p] at h ⊢; split_ifs at h <;> omega
        · dsimp [efx_anchor_family_perturbation_exists_p] at h ⊢; split_ifs at h <;> omega
        · dsimp [efx_anchor_family_perturbation_exists_p] at h ⊢; exact h
  4. For every agent i and item g, the value p i g is strictly less than 7 + 3r + s.

    Fixing an agent i and item index g < 7 + 3r + s, we case split on i. For agents 0, 1, and 2, unfolding `efx_anchor_family_perturbation_exists_p` and branching on the interval containing g, linear arithmetic (`omega`) verifies that each piecewise expression evaluates to a number strictly less than 7 + 3r + s (using r > 0 and 2 ≤ s). For agent 3, p 3(g) = g is strictly bounded by hypothesis.

    lines 30–35

    uses efx_anchor_family_perturbation_exists_p

      · intro i ⟨g, hg⟩
        fin_cases i
        · dsimp [efx_anchor_family_perturbation_exists_p]; split_ifs <;> omega
        · dsimp [efx_anchor_family_perturbation_exists_p]; split_ifs <;> omega
        · dsimp [efx_anchor_family_perturbation_exists_p]; split_ifs <;> omega
        · dsimp [efx_anchor_family_perturbation_exists_p]; omega
  5. The starting agent assignment of anchors a and b is rewritten into bounds on their numerical indices.

    We introduce agent i ∈ Fin 3 and anchors a, b < 3r, where anchor a initially belongs to agent i and anchor b does not. Rewriting with `efx_anchor_family_perturbation_exists_start_anchor` translates the initial allocations into conditions on whether the indices a and b lie in [0, r), [r, 2r), or [2r, 3r), while extracting the inequalities a < 3r and b < 3r from the type bounds of Fin.

    lines 36–39

    uses efx_anchor_family_perturbation_exists_start_anchor

      · intro i a b ha hb
        rw [efx_anchor_family_perturbation_exists_start_anchor] at ha hb
        have h_a_lt := a.isLt
        have h_b_lt := b.isLt
  6. For each agent i ∈ Fin 3, any anchor a belonging to agent i satisfies p i b < p i a for any anchor b belonging to another agent.

    We perform a case split on the agent i ∈ Fin 3. For each agent, unfolding p i shows that agent i's own r anchors (at indices 7 + i · r through 7 + (i + 1) · r - 1) are shifted to the very top interval [7 + 2r + s, 7 + 3r + s), whereas any anchor b belonging to a different agent is mapped to a value strictly below 7 + 2r + s. Case analysis on the intervals (`split_ifs`) and linear arithmetic (`omega`) resolve all branches for agents 0, 1, and 2.

    lines 40–49

    uses efx_anchor_family_perturbation_exists_p

        fin_cases i
        · dsimp at ha hb
          dsimp [efx_anchor_family_perturbation_exists_p]
          split_ifs at ha hb ⊢ <;> omega
        · dsimp at ha hb
          dsimp [efx_anchor_family_perturbation_exists_p]
          split_ifs at ha hb ⊢ <;> omega
        · dsimp at ha hb
          dsimp [efx_anchor_family_perturbation_exists_p]
          split_ifs at ha hb ⊢ <;> omega
efx_anchor_family_start
the initial assignment mapping the first 7 goods to [1, 0, 0, 0, 1, 2, 4], the 3r anchors in three blocks of size r to agents 0, 1, and 2 respectively, and the remaining s goods to agent 3
Fin.addCases_left
evaluating `Fin.addCases left right` on an element injected from the left summand via `Fin.castAdd` reduces to evaluating `left` on that element
Fin.addCases_right
evaluating `Fin.addCases left right` on an element injected from the right summand via `Fin.natAdd` reduces to evaluating `right` on that element
efx_anchor_family_perturbation_exists_p
the piecewise definition of the permutation function for given parameters r and s, agent index i ∈ Fin 4, and item index g
Fin.ext
two elements of Fin n are equal if their underlying natural numbers are equal
efx_anchor_family_perturbation_exists_start_anchor
in the initial allocation, an anchor item a < 3r is assigned to agent 0 if a < r, agent 1 if r ≤ a < 2r, and agent 2 otherwise

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

def efx_anchor_family_perturbation_exists_p (r s : ℕ) (i : Fin 4) (g : ℕ) : ℕ :=  match i with  | 0 => if g < 7 then g else if g < 7 + r then 7 + r + r + s + (g - 7) else g - r  | 1 => if g < 7 + r then g else if g < 7 + r + r then 7 + r + r + s + (g - (7 + r)) else g - r  | 2 => if g < 7 + r + r then g else if g < 7 + r + r + r then 7 + r + r + s + (g - (7 + r + r)) else g - r  | 3 => glemma efx_anchor_family_perturbation_exists_start_anchor (r s : ℕ) (a : Fin (r+r+r)) :    efx_anchor_family_start r s (Fin.castAdd s (Fin.natAdd 7 a)) =      if (a : ℕ) < r then 0 else if (a : ℕ) < r+r then 1 else 2 := by  dsimp [efx_anchor_family_start]  rw [Fin.addCases_left, Fin.addCases_right]theorem efx_anchor_family_perturbation_exists (r s : ℕ) (hr : 0 < r) (hs : 2 ≤ s) :  ∃ p : Fin 4 → Fin ((7+(r+r+r))+s) → ℕ,    (∀ i, Function.Injective (p i)) ∧    (∀ i g, p i g < (7+(r+r+r))+s) ∧    (∀ (i : Fin 3) (a b : Fin (r+r+r)),      efx_anchor_family_start r s (Fin.castAdd s (Fin.natAdd 7 a)) = i.castSucc.castSucc →      efx_anchor_family_start r s (Fin.castAdd s (Fin.natAdd 7 b)) ≠ i.castSucc.castSucc →      p i.castSucc (Fin.castAdd s (Fin.natAdd 7 b)) < p i.castSucc (Fin.castAdd s (Fin.natAdd 7 a))) := by  refine ⟨fun i g => efx_anchor_family_perturbation_exists_p r s i g, ?_, ?_, ?_⟩  · intro i ⟨x, hx⟩ ⟨y, hy⟩ h    apply Fin.ext    fin_cases i    · dsimp [efx_anchor_family_perturbation_exists_p] at h ⊢; split_ifs at h <;> omega    · dsimp [efx_anchor_family_perturbation_exists_p] at h ⊢; split_ifs at h <;> omega    · dsimp [efx_anchor_family_perturbation_exists_p] at h ⊢; split_ifs at h <;> omega    · dsimp [efx_anchor_family_perturbation_exists_p] at h ⊢; exact h  · intro i ⟨g, hg⟩    fin_cases i    · dsimp [efx_anchor_family_perturbation_exists_p]; split_ifs <;> omega    · dsimp [efx_anchor_family_perturbation_exists_p]; split_ifs <;> omega    · dsimp [efx_anchor_family_perturbation_exists_p]; split_ifs <;> omega    · dsimp [efx_anchor_family_perturbation_exists_p]; omega  · intro i a b ha hb    rw [efx_anchor_family_perturbation_exists_start_anchor] at ha hb    have h_a_lt := a.isLt    have h_b_lt := b.isLt    fin_cases i    · dsimp at ha hb      dsimp [efx_anchor_family_perturbation_exists_p]      split_ifs at ha hb ⊢ <;> omega    · dsimp at ha hb      dsimp [efx_anchor_family_perturbation_exists_p]      split_ifs at ha hb ⊢ <;> omega    · dsimp at ha hb      dsimp [efx_anchor_family_perturbation_exists_p]      split_ifs at ha hb ⊢ <;> omega
See it in the graphDiscuss this resultChallenge it