AFTD Auto-Formalizing Theoretical Domains

finite_envy_cycle_improvement

theoremverified

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

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

    lines 6–8

    uses finite_function_exists_positive_period

      classical
      choose f hf using h
      obtain ⟨k, hk, x, hx⟩ := finite_function_exists_positive_period f
  2. The 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.

    lines 9–13

    uses Function.bijOn_ptsOfPeriod, Equiv.ofBijective, Equiv.Perm.ofSubtype

      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
  3. 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.

    lines 14–17

    uses Equiv.Perm.ofSubtype_apply_of_mem, Equiv.Perm.ofSubtype_apply_of_not_mem

      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
  4. 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.

    line 18

      refine ⟨q.symm, ?_, ?_⟩
  5. 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)).

    lines 19–23

    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
  6. 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.

    lines 24–26

    uses q.apply_symm_apply

        · have hh := hfix (q.symm i) hi
          rw [q.apply_symm_apply] at hh
          rw [← hh]
  7. 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.

    lines 27–29

    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.

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