two_agent_envy_freeable_iff
For two agents with arbitrary valuations over bundles of items, an allocation is envy-freeable if and only if the sum of agent 0's net value for bundle 0 over bundle 1 and agent 1's net value for bundle 1 over bundle 0 is non-negative.
Statement
theorem two_agent_envy_freeable_iff {M : Type*} [Fintype M] (v : Fin 2 → Finset M → ℝ) (A : M → Fin 2) : allocation_is_envy_freeable v A ↔ 0 ≤ (v 0 (allocation_bundle A 0) - v 0 (allocation_bundle A 1)) + (v 1 (allocation_bundle A 1) - v 1 (allocation_bundle A 0))
- Source
- arXiv:2610.14994, Theorem 2.1 (specialized to n=2)
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- allocation_bundleFor a complete allocation A of the goods M to the agents N (each good to one agent), the bundle of agent i is the set of goods A assigns…
- allocation_is_envy_freeableAn allocation is envy-freeable if there are nonnegative payments p such that every agent i weakly prefers its own bundle plus payment to…
- Used by 2
- two_agent_scale_free_lottery_of_envy_freeable_rescalingsFor two agents and any scale-free allocation property P, if every positive rescaling c ⊙ v admits an allocation that is simultaneously P…
- two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescalingFor two agents with arbitrary real valuations over subsets of a finite set of items, if q is an ex-ante envy-free lottery over complete…
Read back from the Lean
For any finite type $M$ of items, any valuation profile $v : \text{Fin } 2 \to \text{Finset } M \to \mathbb{R}$, and any allocation $A : M \to \text{Fin } 2$, the allocation $A$ is envy-freeable under $v$ if and only if $0 \le (v(0, A_0) - v(0, A_1)) + (v(1, A_1) - v(1, A_0))$, where $A_i = \{g \in M \mid A(g) = i\}$ is the bundle of items allocated to agent $i$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes equivalence by showing necessity and sufficiency separately. For necessity, the two envy-free conditions between the agents form a pair of linear inequalities whose sum cancels the subsidy vector, leaving the net value sum non-negative. For sufficiency, letting x be agent 0's net valuation of bundle 0 over bundle 1, we case split on the sign of x: if x ≥ 0 we subsidize agent 1 by x, and if x ≤ 0 we subsidize agent 0 by -x, which in both cases provides non-negative subsidies eliminating all envy.
If an allocation is envy-freeable, the sum of the agents' net values for their assigned bundles over each other's bundles is non-negative.
Splitting the iff into two directions, we first assume the allocation is envy-freeable, so there exists a non-negative subsidy vector p satisfying envy-freeness. In particular, agent 0 not envying agent 1 gives v 0 (A 1) + p 1 ≤ v 0 (A 0) + p 0, and agent 1 not envying agent 0 gives v 1 (A 0) + p 0 ≤ v 1 (A 1) + p 1. Adding these two inequalities cancels the subsidies p 0 and p 1, directly yielding 0 ≤ (v 0 (A 0) - v 0 (A 1)) + (v 1 (A 1) - v 1 (A 0)).
constructor · rintro ⟨p, hp_nonneg, hp_ef⟩ have h01 := hp_ef 0 1 have h10 := hp_ef 1 0 linarith
To show envy-freeability from the non-negative net value sum, it suffices to consider the cases x ≥ 0 and x ≤ 0, where x is agent 0's net valuation of bundle 0 over bundle 1.
Assuming 0 ≤ (v 0 (A 0) - v 0 (A 1)) + (v 1 (A 1) - v 1 (A 0)), we define x = v 0 (A 0) - v 0 (A 1). By totality of the ordering on the real numbers (le_total), either 0 ≤ x or x ≤ 0.
uses
le_total· intro h let x := v 0 (allocation_bundle A 0) - v 0 (allocation_bundle A 1) rcases le_total 0 x with hx | hx
When x ≥ 0, the allocation is envy-freeable with subsidy vector p = (0, x).
We choose subsidies p 0 = 0 and p 1 = x. Both subsidies are non-negative since 0 ≤ x. To verify envy-freeness, we examine all four agent pairs (i, j): the diagonal cases (0, 0) and (1, 1) are trivial identities; for agent 0 evaluating agent 1's bundle, v 0 (A 1) + x ≤ v 0 (A 0) holds with equality by the definition of x; and for agent 1 evaluating agent 0's bundle, v 1 (A 0) ≤ v 1 (A 1) + x is a linear rearrangement of the hypothesis 0 ≤ x + (v 1 (A 1) - v 1 (A 0)).
· use ![0, x] constructor · intro i fin_cases i <;> simp [hx] · intro i j fin_cases i <;> fin_cases j <;> (simp; try linarith)
When x ≤ 0, the allocation is envy-freeable with subsidy vector p = (-x, 0).
We choose subsidies p 0 = -x and p 1 = 0. Since x ≤ 0, the subsidy -x is non-negative. Checking all four pairs (i, j): the diagonal cases are trivial identities; for agent 0 evaluating agent 1's bundle, v 0 (A 1) ≤ v 0 (A 0) - x holds with equality by the definition of x; and for agent 1 evaluating agent 0's bundle, v 1 (A 0) - x ≤ v 1 (A 1) holds because x + (v 1 (A 1) - v 1 (A 0)) ≥ 0 by the hypothesis.
· use ![-x, 0] constructor · intro i fin_cases i <;> (simp; try linarith) · intro i j fin_cases i <;> fin_cases j <;> (simp; try linarith)
le_total- In any linear order, any two elements are comparable: either a ≤ b or b ≤ a.
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.
/-- Characterization of envy-freeability for two agents: an allocation is envy-freeable if and only if the sum of pairwise negative envies is non-negative. -/theorem two_agent_envy_freeable_iff {M : Type*} [Fintype M] (v : Fin 2 → Finset M → ℝ) (A : M → Fin 2) : allocation_is_envy_freeable v A ↔ 0 ≤ (v 0 (allocation_bundle A 0) - v 0 (allocation_bundle A 1)) + (v 1 (allocation_bundle A 1) - v 1 (allocation_bundle A 0)) := by constructor · rintro ⟨p, hp_nonneg, hp_ef⟩ have h01 := hp_ef 0 1 have h10 := hp_ef 1 0 linarith · intro h let x := v 0 (allocation_bundle A 0) - v 0 (allocation_bundle A 1) rcases le_total 0 x with hx | hx · use ![0, x] constructor · intro i fin_cases i <;> simp [hx] · intro i j fin_cases i <;> fin_cases j <;> (simp; try linarith) · use ![-x, 0] constructor · intro i fin_cases i <;> (simp; try linarith) · intro i j fin_cases i <;> fin_cases j <;> (simp; try linarith)