efx_anchor_family_perturbation_exists
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.
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.
uses
efx_anchor_family_start,Fin.addCases_left,Fin.addCases_rightdsimp [efx_anchor_family_start] rw [Fin.addCases_left, Fin.addCases_right]
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.
uses
efx_anchor_family_perturbation_exists_prefine ⟨fun i g => efx_anchor_family_perturbation_exists_p r s i g, ?_, ?_, ?_⟩
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.
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
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.
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
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.
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
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.
uses
efx_anchor_family_perturbation_exists_pfin_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
- The case analyses for injectivity, bounds, and anchor priority rely extensively on `omega` after `split_ifs`, which automatically verifies dozens of linear integer arithmetic constraints arising from the piecewise boundaries of the permutation.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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