finite_unenvied_permutation
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.
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.
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]⟩
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.
uses
Finset.exists_max_image,Finset.mem_filter.mpobtain ⟨p, hp, hmax⟩ := Finset.exists_max_image S (fun p => ∑ i, w i (p i)) hS refine ⟨p, (Finset.mem_filter.mp hp).2, ?_⟩
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.
uses
finite_envy_cycle_improvementby_contra hn push Not at hn obtain ⟨q, hq, j, hj⟩ := finite_envy_cycle_improvement (fun i k => w i (p k)) hn
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_filter.mphave 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)
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))).
uses
Finset.sum_lt_sum,Finset.mem_univhave 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⟩
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))).
uses
not_lt_of_geexact (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.
- In Lean, permutation composition `q.trans p` applies `q` first and then `p`, so `(q.trans p) i = p (q i)`.
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_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