AFTD Auto-Formalizing Theoretical Domains

is_envy_free_with_subsidy_perm_le

theoremverified

If (σ, p) is envy-free with subsidies, then for every permutation π of agents, ∑_i v_i(A_{π(i)}) ≤ ∑_i v_i(A_i).

Statement

theorem is_envy_free_with_subsidy_perm_le {m n : ℕ}
    (v : Fin n → Finset (Fin m) → ℝ) (σ : Fin m → Fin n) (p : Fin n → ℝ)
    (hef : is_envy_free_with_subsidy v σ p) (π : Equiv.Perm (Fin n)) :
    ∑ i, v i (bundle_of σ (π i)) ≤ ∑ i, v i (bundle_of σ i)
Source
step towards scaled_common_ratio_bivalued_efx_fpo_envyfreeable
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
  • is_envy_free_with_subsidyAn allocation with nonnegative payments p is envy-free if v_i(A_i) + p_i ≥ v_i(A_j) + p_j for all agents i, j.

The proof, explained

By the definition of envy-freeness with subsidies, each agent weakly prefers their own allocated bundle and subsidy to those of any other agent; in particular, agent $i$ prefers their bundle to agent $\pi(i)$'s bundle. Summing this preference inequality over all agents yields a comparison between the total valuation plus subsidy under the permutation $\pi$ and under the identity. Since $\pi$ is a permutation of the agents, the total subsidies on both sides are identical ($\sum_i p(\pi(i)) = \sum_i p(i)$), and cancelling them leaves the desired inequality on valuations.

  1. $\sum_i v_i(\text{bundle\_of } \sigma (\pi(i))) + \sum_i p(\pi(i)) \le \sum_i v_i(\text{bundle\_of } \sigma (i)) + \sum_i p(i)$

    By envy-freeness with subsidies (`hef.2`), each agent $i$ weakly prefers their allocated bundle and subsidy to those of agent $\pi(i)$: $v_i(\text{bundle\_of } \sigma (\pi(i))) + p(\pi(i)) \le v_i(\text{bundle\_of } \sigma (i)) + p(i)$. Summing these inequalities over all agents via `Finset.sum_le_sum` and splitting the sums over addition with `Finset.sum_add_distrib` yields the inequality with valuations and subsidies separated.

    lines 6–7

    uses Finset.sum_le_sum, Finset.sum_add_distrib

      have h := Finset.sum_le_sum (fun i (_ : i ∈ Finset.univ) => hef.2 i (π i))
      simp only [Finset.sum_add_distrib] at h
  2. $\sum_i v_i(\text{bundle\_of } \sigma (\pi(i))) \le \sum_i v_i(\text{bundle\_of } \sigma (i))$

    Because $\pi$ is a permutation of the finite set of agents, reindexing the subsidy sum via `Equiv.sum_comp` shows that $\sum_i p(\pi(i)) = \sum_i p(i)$. Since the subsidy sum is identical on both sides of the inequality, subtracting it cancels the subsidies and finishes the proof via linear arithmetic (`linarith`).

    lines 8–9

    uses Equiv.sum_comp

      rw [Equiv.sum_comp π p] at h
      linarith
Finset.sum_le_sum
If $f(i) \le g(i)$ for all $i \in s$, then $\sum_{i \in s} f(i) \le \sum_{i \in s} g(i)$.
Finset.sum_add_distrib
The sum of a pointwise sum of functions equals the sum of the individual sums: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
Equiv.sum_comp
Summing a function over a finite type is invariant under precomposition with an equivalence (permutation): $\sum_i g(e(i)) = \sum_i g(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

/-- If an allocation is envy-free with subsidies, then for every permutation of the agents, the sum of values for the permuted bundles is at most the sum of values for their own bundles. -/theorem is_envy_free_with_subsidy_perm_le {m n : ℕ}    (v : Fin n → Finset (Fin m) → ℝ) (σ : Fin m → Fin n) (p : Fin n → ℝ)    (hef : is_envy_free_with_subsidy v σ p) (π : Equiv.Perm (Fin n)) :    ∑ i, v i (bundle_of σ (π i)) ≤ ∑ i, v i (bundle_of σ i) := by  have h := Finset.sum_le_sum (fun i (_ : i ∈ Finset.univ) => hef.2 i (π i))  simp only [Finset.sum_add_distrib] at h  rw [Equiv.sum_comp π p] at h  linarith
See it in the graphDiscuss this resultChallenge it