AFTD Auto-Formalizing Theoretical Domains

finite_unenvied_permutation

theoremverified

Every finite nonempty matrix of real bundle values admits a permutation that weakly improves each diagonal value and has an unenvied column in the permuted assignment.

Statement

theorem finite_unenvied_permutation {α : Type*} [Fintype α] [Nonempty α]
    (w : α → α → ℝ) :
    ∃ p : Equiv.Perm α, (∀ i, w i i ≤ w i (p i)) ∧
      ∃ s, ∀ i, w i (p s) ≤ w i (p i)
Source
Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01. Standard cycle elimination and ordered insertion, arXiv:1707.04769v3 Lemma 6.1 and Appendix B; no novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • finite_envy_cycle_improvementFor a finite nonempty matrix of real bundle values, if every bundle is strictly envied by an agent relative to her own bundle, some bundle…
Used by 2
  • is_efx_goods_exists_unenviedFor a positive number of agents, any EFX allocation of nonnegative additive goods can be changed to another EFX allocation that weakly…
  • 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…

The proof, explained

We consider the set S of all permutations that weakly improve every diagonal valuation w(i, i) ≤ w(i, p(i)), which is finite and nonempty because it contains the identity. We choose a permutation p in S that maximizes the total valuation sum ∑ i, w(i, p(i)). If no column were unenvied under p, every bundle would be envied by someone, so an envy-cycle improvement lemma would produce a trading permutation q that weakly improves everyone and strictly improves at least one agent. Composing q with p would yield a new permutation in S with a strictly higher total sum, contradicting the maximality of p.

  1. The set S of permutations weakly improving every diagonal entry is well-defined and nonempty.

    We define S to be the finite set of all permutations p of α that satisfy w(i, i) ≤ w(i, p(i)) for every agent i. The identity permutation `Equiv.refl α` trivially preserves every value, so S is nonempty.

    lines 7–9

      classical
      let S : Finset (Equiv.Perm α) := Finset.univ.filter (fun p => ∀ i, w i i ≤ w i (p i))
      have hS : S.Nonempty := ⟨Equiv.refl α, by simp [S]⟩
  2. There exists a permutation p in S maximizing the total valuation sum, which satisfies the first condition of the theorem.

    Because S is finite and nonempty, the objective function p ↦ ∑ i, w(i, p(i)) achieves its maximum at some p ∈ S by `Finset.exists_max_image`. By definition of S, extracted via `Finset.mem_filter.mp`, p weakly improves every agent's diagonal value, satisfying the first conjunct. It remains to show that some column is unenvied under p.

    lines 10–11

    uses Finset.exists_max_image, Finset.mem_filter.mp

      obtain ⟨p, hp, hmax⟩ := Finset.exists_max_image S (fun p => ∑ i, w i (p i)) hS
      refine ⟨p, (Finset.mem_filter.mp hp).2, ?_⟩
  3. Assuming for contradiction that every column is envied under p, there exists a trading permutation q that weakly improves every agent and strictly improves at least one.

    Suppose, for contradiction, that no column under p is unenvied. Pushing the negation inward, this means that for every bundle s, some agent i strictly prefers p(s) over their assigned bundle p(i), i.e., w(i, p(i)) < w(i, p(s)). Applying `finite_envy_cycle_improvement` to the reindexed matrix (i, k) ↦ w(i, p(k)), we obtain a permutation q of α and an agent j such that w(i, p(i)) ≤ w(i, p(q(i))) for all i, with strict inequality w(j, p(j)) < w(j, p(q(j))) at j.

    lines 12–14

    uses finite_envy_cycle_improvement

      by_contra hn
      push Not at hn
      obtain ⟨q, hq, j, hj⟩ := finite_envy_cycle_improvement (fun i k => w i (p k)) hn
  4. The composed permutation q ∘ p also belongs to S.

    Unfolding membership in S using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, we must verify that w(i, i) ≤ w(i, p(q(i))) for all i. Since p ∈ S, we have w(i, i) ≤ w(i, p(i)) by `Finset.mem_filter.mp`, and from q we have w(i, p(i)) ≤ w(i, p(q(i))). By transitivity of ≤, w(i, i) ≤ w(i, p(q(i))), so the composite permutation `q.trans p` belongs to S.

    lines 15–18

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_filter.mp

      have hnew : q.trans p ∈ S := by
        simp only [S, Finset.mem_filter, Finset.mem_univ, true_and]
        intro i
        exact ((Finset.mem_filter.mp hp).2 i).trans (hq i)
  5. The total sum of valuations under q ∘ p is strictly greater than under p.

    Since w(i, p(i)) ≤ w(i, p(q(i))) for all i ∈ Finset.univ and the inequality is strictly satisfied at index j (via `Finset.mem_univ`), `Finset.sum_lt_sum` implies that ∑ i, w(i, p(i)) < ∑ i, w(i, p(q(i))).

    lines 19–20

    uses Finset.sum_lt_sum, Finset.mem_univ

      have hlt : (∑ i, w i (p i)) < ∑ i, w i ((q.trans p) i) := by
        exact Finset.sum_lt_sum (fun i _ => hq i) ⟨j, Finset.mem_univ _, hj⟩
  6. The existence of q ∘ p contradicts the maximality of p in S, completing the proof.

    Since q ∘ p ∈ S, the maximality of p implies ∑ i, w(i, p(q(i))) ≤ ∑ i, w(i, p(i)). By `not_lt_of_ge`, this directly contradicts the strict inequality ∑ i, w(i, p(i)) < ∑ i, w(i, p(q(i))).

    line 21

    uses not_lt_of_ge

      exact (not_lt_of_ge (hmax (q.trans p) hnew)) hlt
Finset.exists_max_image
Every nonempty finite set has an element that maximizes a given function into a linear order.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mp
If an element belongs to a filtered finite set, then it satisfies the filtering predicate (the forward direction of `Finset.mem_filter`).
Finset.mem_univ
Every element of a finite type belongs to the universal finite set `Finset.univ`.
Finset.sum_lt_sum
If f(i) ≤ g(i) for all elements of a finite set and the inequality is strict for at least one element, then the sum of f is strictly less than the sum of g.
not_lt_of_ge
If a ≤ b in a preorder, then b < a cannot hold.
true_and
The proposition `True ∧ p` is equivalent to `p`.
finite_envy_cycle_improvement
In a finite nonempty valuation matrix where every column is strictly envied by some agent, there is a permutation weakly improving every agent and strictly improving at least one.

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_unenvied_permutation {α : Type*} [Fintype α] [Nonempty α]    (w : α → α → ℝ) :    ∃ p : Equiv.Perm α, (∀ i, w i i ≤ w i (p i)) ∧      ∃ s, ∀ i, w i (p s) ≤ w i (p i) := by  classical  let S : Finset (Equiv.Perm α) := Finset.univ.filter (fun p => ∀ i, w i i ≤ w i (p i))  have hS : S.Nonempty := ⟨Equiv.refl α, by simp [S]⟩  obtain ⟨p, hp, hmax⟩ := Finset.exists_max_image S (fun p => ∑ i, w i (p i)) hS  refine ⟨p, (Finset.mem_filter.mp hp).2, ?_⟩  by_contra hn  push Not at hn  obtain ⟨q, hq, j, hj⟩ := finite_envy_cycle_improvement (fun i k => w i (p k)) hn  have hnew : q.trans p ∈ S := by    simp only [S, Finset.mem_filter, Finset.mem_univ, true_and]    intro i    exact ((Finset.mem_filter.mp hp).2 i).trans (hq i)  have hlt : (∑ i, w i (p i)) < ∑ i, w i ((q.trans p) i) := by    exact Finset.sum_lt_sum (fun i _ => hq i) ⟨j, Finset.mem_univ _, hj⟩  exact (not_lt_of_ge (hmax (q.trans p) hnew)) hlt
See it in the graphDiscuss this resultChallenge it