AFTD Auto-Formalizing Theoretical Domains

finite_two_bonus_ordered_assignment

theoremverified

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

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.

  1. 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)$.

    lines 11–12

      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]
  2. 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.

    line 13

    uses finite_two_bonus_assignment

      obtain ⟨p, r, s, t, hI, hA, hB⟩ := finite_two_bonus_assignment w g hg
  3. When $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)$.

    lines 14–15

      cases t
      · exact ⟨p, r, s, by simpa [g] using hI, by simpa [g] using hA, by simpa [g] using hB⟩
  4. 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`).

    lines 16–19

    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

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
See it in the graphDiscuss this resultChallenge it