finite_two_bonus_ordered_assignment
For any finite nonempty real matrix w and two nonnegative agent-dependent bonuses a and b, there is a permutation of the old columns, a recipient r of a, and a recipient s of b, possibly equal, which weakly improves each original diagonal. Removing a from column r or b from column s leaves no foreign envy toward that column relative to the final own values.
Statement
theorem finite_two_bonus_ordered_assignment {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] (w : α → α → ℝ) (a b : α → ℝ) (ha : ∀ i, 0 ≤ a i) (hb : ∀ i, 0 ≤ b i) : ∃ (p : Equiv.Perm α) (r s : α), (∀ i, w i i ≤ w i (p i) + (if i = r then a i else 0) + (if i = s then b i else 0)) ∧ (∀ i, i ≠ r → w i (p r) + (if r = s then b i else 0) ≤ w i (p i) + (if i = r then a i else 0) + (if i = s then b i else 0)) ∧ (∀ i, i ≠ s → w i (p s) + (if s = r then a i else 0) ≤ w i (p i) + (if i = r then a i else 0) + (if i = s then b i else 0))
- Source
- Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- finite_two_bonus_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonus values g(false), g(true), there is a permutation of the…
- Used by 1
- efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values…
The proof, explained
The theorem is proved by reducing it to `finite_two_bonus_assignment`, which establishes the result for an unordered pair of bonuses. We encode the bonuses $a$ and $b$ as a boolean-indexed family $g$, with $g(\text{false}) = a$ and $g(\text{true}) = b$. Applying the unordered assignment theorem yields a permutation, two recipients, and a boolean flag indicating which bonus was assigned to which recipient. A case split on the boolean flag completes the proof: if $a$ was assigned to the first recipient, we keep the recipients as given; otherwise, we swap the two recipients.
The bonuses $a$ and $b$ are packaged as a nonnegative boolean-indexed family $g$.
We define $g : \text{Bool} \to \alpha \to \mathbb{R}$ by $g(\text{true}) = b$ and $g(\text{false}) = a$. A case split on the boolean input $t$ verifies that $0 \le g(t)(i)$ for all $i \in \alpha$, reducing immediately to the assumptions $0 \le a(i)$ and $0 \le b(i)$.
let g : Bool → α → ℝ := fun t => if t then b else a have hg (t : Bool) (i : α) : 0 ≤ g t i := by cases t <;> simp [g, ha, hb]
There exist a permutation $p$, recipients $r, s \in \alpha$, and a boolean flag $t$ satisfying the assignment conditions for bonus $g(t)$ at $r$ and bonus $g(\neg t)$ at $s$.
Applying the unordered two-bonus theorem `finite_two_bonus_assignment` to the matrix $w$ and the family $g$ yields a permutation $p$, recipients $r$ and $s$, and a boolean $t$ such that every diagonal entry weakly improves and foreign envy toward column $r$ (without $g(t)$) or column $s$ (without $g(\neg t)$) is eliminated.
uses
finite_two_bonus_assignmentobtain ⟨p, r, s, t, hI, hA, hB⟩ := finite_two_bonus_assignment w g hgWhen $t = \text{false}$, the triple $(p, r, s)$ directly satisfies the ordered bonus conditions, with $r$ receiving $a$ and $s$ receiving $b$.
We split on the boolean $t$. When $t = \text{false}$, recipient $r$ receives $g(\text{false}) = a$ and recipient $s$ receives $g(\neg \text{false}) = g(\text{true}) = b$. Evaluating $g$ simplifies the three hypotheses directly into the required goals for $(p, r, s)$.
cases t · exact ⟨p, r, s, by simpa [g] using hI, by simpa [g] using hA, by simpa [g] using hB⟩
When $t = \text{true}$, swapping the recipients to $(s, r)$ satisfies the ordered bonus conditions, with $s$ receiving $a$ and $r$ receiving $b$.
When $t = \text{true}$, the assignment gave $g(\text{true}) = b$ to $r$ and $g(\neg \text{true}) = a$ to $s$. We provide $(p, s, r)$ as the witness, so that $s$ receives $a$ and $r$ receives $b$. The three required bounds follow from the hypotheses by simplifying $g$ and reordering the additions using associativity and commutativity (`add_comm`, `add_left_comm`, `add_assoc`).
uses
add_comm,add_left_comm,add_assoc· refine ⟨p, s, r, ?_, ?_, ?_⟩ · simpa [g, add_comm, add_left_comm, add_assoc] using hI · simpa [g, add_comm, add_left_comm, add_assoc] using hB · simpa [g, add_comm, add_left_comm, add_assoc] using hA
finite_two_bonus_assignment- Given a real matrix and two nonnegative bonuses indexed by booleans, there exist a permutation, two recipient columns, and a boolean flag assigning the bonuses such that all diagonal entries weakly improve and foreign envy toward each recipient's column is eliminated when that column's bonus is removed.
add_comm- Addition is commutative: $a + b = b + a$.
add_left_comm- The first two summands in a nested sum can be swapped: $a + (b + c) = b + (a + c)$.
add_assoc- Addition is associative: $(a + b) + c = a + (b + c)$.
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.
open Function Finsettheorem finite_two_bonus_ordered_assignment {α : Type*} [Fintype α] [Nonempty α] [DecidableEq α] (w : α → α → ℝ) (a b : α → ℝ) (ha : ∀ i, 0 ≤ a i) (hb : ∀ i, 0 ≤ b i) : ∃ (p : Equiv.Perm α) (r s : α), (∀ i, w i i ≤ w i (p i) + (if i = r then a i else 0) + (if i = s then b i else 0)) ∧ (∀ i, i ≠ r → w i (p r) + (if r = s then b i else 0) ≤ w i (p i) + (if i = r then a i else 0) + (if i = s then b i else 0)) ∧ (∀ i, i ≠ s → w i (p s) + (if s = r then a i else 0) ≤ w i (p i) + (if i = r then a i else 0) + (if i = s then b i else 0)) := by let g : Bool → α → ℝ := fun t => if t then b else a have hg (t : Bool) (i : α) : 0 ≤ g t i := by cases t <;> simp [g, ha, hb] obtain ⟨p, r, s, t, hI, hA, hB⟩ := finite_two_bonus_assignment w g hg cases t · exact ⟨p, r, s, by simpa [g] using hI, by simpa [g] using hA, by simpa [g] using hB⟩ · refine ⟨p, s, r, ?_, ?_, ?_⟩ · simpa [g, add_comm, add_left_comm, add_assoc] using hI · simpa [g, add_comm, add_left_comm, add_assoc] using hB · simpa [g, add_comm, add_left_comm, add_assoc] using hA