finite_envy_cycle_improvement
For a finite nonempty matrix of real bundle values, if every bundle is strictly envied by an agent relative to her own bundle, some bundle permutation weakly improves every diagonal value and strictly improves at least one.
Statement
theorem finite_envy_cycle_improvement {α : Type*} [Fintype α] [Nonempty α] (w : α → α → ℝ) (h : ∀ j, ∃ i, w i i < w i j) : ∃ p : Equiv.Perm α, (∀ i, w i i ≤ w i (p i)) ∧ ∃ i, w i i < 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_function_exists_positive_periodEvery endomorphism of a finite nonempty type has a periodic point with a strictly positive period.
- Used by 3
- finite_column_switch_improvementIn a finite nonempty real matrix w, suppose each column other than s is strictly envied relative to diagonal values, and some agent other…
- finite_unenvied_permutationEvery finite nonempty matrix of real bundle values admits a permutation that weakly improves each diagonal value and has an unenvied…
- 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
By the assumption that every bundle is envied, we can select a function f assigning each bundle j to an agent f(j) who strictly prefers j to her own bundle. On a finite nonempty set, f must have a periodic cycle of positive length k. Restricting f to its periodic points yields a permutation of that cycle, which extends to a permutation q of the whole set by fixing all other points. Allocating bundles via the inverse permutation p = q⁻¹ ensures that agents receiving a bundle from the cycle strictly improve while all other agents keep their own bundles, guaranteeing weak improvement for everyone and strict improvement for the periodic agents.
There exists a selection function f sending each bundle to an agent who envies it, and f admits a periodic point x of positive period k.
Using choice on the envy hypothesis h, we select a function f : α → α such that for every bundle j, agent f(j) strictly prefers j to her own bundle f(j). Since α is finite and nonempty, any self-map has a periodic orbit, so finite_function_exists_positive_period yields an integer k > 0 and a point x of period k under f.
uses
finite_function_exists_positive_periodclassical choose f hf using h obtain ⟨k, hk, x, hx⟩ := finite_function_exists_positive_period fThe restriction of f to its k-periodic points extends to a permutation q of α that acts as the identity outside the periodic set.
Let C be the set of points of period k under f. Since k > 0, f acts bijectively on C by Function.bijOn_ptsOfPeriod, which gives a permutation e of C via Equiv.ofBijective. We then extend e to a permutation q of all of α using Equiv.Perm.ofSubtype.
uses
Function.bijOn_ptsOfPeriod,Equiv.ofBijective,Equiv.Perm.ofSubtypelet C := Function.ptsOfPeriod f k let e : Equiv.Perm C := Equiv.ofBijective ((Function.bijOn_ptsOfPeriod f hk).mapsTo.restrict f C C) (Function.bijOn_ptsOfPeriod f hk).bijective let q : Equiv.Perm α := Equiv.Perm.ofSubtype e
The permutation q agrees with f on C and fixes every element outside C.
By Equiv.Perm.ofSubtype_apply_of_mem, q(j) = f(j) for any j ∈ C. Conversely, by Equiv.Perm.ofSubtype_apply_of_not_mem, q(j) = j for any j ∉ C.
uses
Equiv.Perm.ofSubtype_apply_of_mem,Equiv.Perm.ofSubtype_apply_of_not_memhave hq (j : α) (hj : j ∈ C) : q j = f j := by exact Equiv.Perm.ofSubtype_apply_of_mem e hj have hfix (j : α) (hj : j ∉ C) : q j = j := by exact Equiv.Perm.ofSubtype_apply_of_not_mem e hj
It suffices to show that the inverse permutation p = q⁻¹ weakly improves every agent's bundle valuation and strictly improves at least one.
We supply q.symm as the candidate permutation, splitting the goal into the universal weak improvement condition and the existential strict improvement condition.
refine ⟨q.symm, ?_, ?_⟩Any agent i whose assigned bundle q⁻¹(i) lies in C strictly improves (hence weakly improves) her valuation.
Assume q⁻¹(i) ∈ C. Then q(q⁻¹(i)) = f(q⁻¹(i)). Using q.apply_symm_apply to simplify q(q⁻¹(i)) to i, we have f(q⁻¹(i)) = i. By definition of f, agent i strictly prefers bundle q⁻¹(i) to i, giving w(i, i) < w(i, q⁻¹(i)), which implies w(i, i) ≤ w(i, q⁻¹(i)).
uses
q.apply_symm_apply· intro i by_cases hi : q.symm i ∈ C · have hh := hf (q.symm i) rw [← hq (q.symm i) hi, q.apply_symm_apply] at hh exact hh.le
Any agent i whose assigned bundle q⁻¹(i) lies outside C keeps her original bundle, so w(i, i) ≤ w(i, q⁻¹(i)).
If q⁻¹(i) ∉ C, then q fixes q⁻¹(i), so q(q⁻¹(i)) = q⁻¹(i). Since q(q⁻¹(i)) = i by q.apply_symm_apply, we have i = q⁻¹(i). Replacing q⁻¹(i) with i yields w(i, i) ≤ w(i, i), which holds reflexively.
uses
q.apply_symm_apply· have hh := hfix (q.symm i) hi rw [q.apply_symm_apply] at hh rw [← hh]
Agent q(x) strictly improves her valuation under q⁻¹.
We instantiate the existential witness with agent i = q(x). Applying the inverse permutation gives bundle q⁻¹(q(x)) = x by q.symm_apply_apply. Because x has period k, x ∈ C and thus q(x) = f(x). The inequality simplifies to w(f(x), f(x)) < w(f(x), x), which holds by the construction of f.
uses
q.symm_apply_apply· refine ⟨q x, ?_⟩ rw [q.symm_apply_apply, hq x hx] exact hf x
finite_function_exists_positive_period- Every self-map on a finite nonempty type has a periodic point of positive period k > 0.
Equiv.Perm.ofSubtype_apply_of_mem- The restriction of a permutation of a subtype to elements of that subtype evaluates to the permutation's value on that element.
Equiv.Perm.ofSubtype_apply_of_not_mem- The extension of a subtype permutation to the ambient type fixes any element not in the subtype.
Function.bijOn_ptsOfPeriod- A map restricts to a bijection on the set of its points of period n, for any n > 0.
Equiv.ofBijective- A bijective function between types induces an equivalence between them.
Equiv.Perm.ofSubtype- A permutation of a subtype extends to a permutation of the whole type by acting as the identity outside the subtype.
q.apply_symm_apply- Applying an equivalence after its inverse is the identity: q (q.symm y) = y.
q.symm_apply_apply- Applying the inverse of an equivalence after the equivalence is the identity: q.symm (q y) = y.
- The inequality w(i, i) ≤ w(i, i) in line 26 is closed automatically by reflexivity during the rewrite (`rw`).
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_envy_cycle_improvement {α : Type*} [Fintype α] [Nonempty α] (w : α → α → ℝ) (h : ∀ j, ∃ i, w i i < w i j) : ∃ p : Equiv.Perm α, (∀ i, w i i ≤ w i (p i)) ∧ ∃ i, w i i < w i (p i) := by classical choose f hf using h obtain ⟨k, hk, x, hx⟩ := finite_function_exists_positive_period f let C := Function.ptsOfPeriod f k let e : Equiv.Perm C := Equiv.ofBijective ((Function.bijOn_ptsOfPeriod f hk).mapsTo.restrict f C C) (Function.bijOn_ptsOfPeriod f hk).bijective let q : Equiv.Perm α := Equiv.Perm.ofSubtype e have hq (j : α) (hj : j ∈ C) : q j = f j := by exact Equiv.Perm.ofSubtype_apply_of_mem e hj have hfix (j : α) (hj : j ∉ C) : q j = j := by exact Equiv.Perm.ofSubtype_apply_of_not_mem e hj refine ⟨q.symm, ?_, ?_⟩ · intro i by_cases hi : q.symm i ∈ C · have hh := hf (q.symm i) rw [← hq (q.symm i) hi, q.apply_symm_apply] at hh exact hh.le · have hh := hfix (q.symm i) hi rw [q.apply_symm_apply] at hh rw [← hh] · refine ⟨q x, ?_⟩ rw [q.symm_apply_apply, hq x hx] exact hf x