two_agent_converse_theorem
For 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 allocations, then for every coordinatewise positive vector c = (c₁, c₂) in ℝ_{>0}², there exists an allocation in the support of q that is envy-freeable at the rescaled profile c ⊙ v; furthermore, for any scale-free allocation property P, an ex-ante envy-free and ex-post P lottery exists if and only if every positive rescaling c ⊙ v admits an allocation that is simultaneously P and envy-freeable.
Statement
theorem two_agent_converse_theorem {M : Type*} [Fintype M] [DecidableEq M] (v : Fin 2 → Finset M → ℝ) : (∀ (q : (M → Fin 2) → ℝ) (hq_nonneg : ∀ A, 0 ≤ q A) (hq_sum : ∑ A, q A = 1) (hef : ∀ i j, ∑ A, q A * v i (allocation_bundle A j) ≤ ∑ A, q A * v i (allocation_bundle A i)) (c : Fin 2 → ℝ) (hc : ∀ i, 0 < c i), ∃ A : M → Fin 2, 0 < q A ∧ allocation_is_envy_freeable (fun i S => c i * v i S) A) ∧ (∀ (P : (Fin 2 → Finset M → ℝ) → (M → Fin 2) → Prop) (hP : ∀ (v' : Fin 2 → Finset M → ℝ) (c : Fin 2 → ℝ), (∀ i, 0 < c i) → ∀ A, P (fun i S => c i * v' i S) A ↔ P v' A), (∃ q : (M → Fin 2) → ℝ, (∀ A, 0 ≤ q A) ∧ ∑ A, q A = 1 ∧ (∀ i j, ∑ A, q A * v i (allocation_bundle A j) ≤ ∑ A, q A * v i (allocation_bundle A i)) ∧ (∀ A, 0 < q A → P v A)) ↔ (∀ c : Fin 2 → ℝ, (∀ i, 0 < c i) → ∃ A : M → Fin 2, P (fun i S => c i * v i S) A ∧ allocation_is_envy_freeable (fun i S => c i * v i S) A))
- Formalizes
- arXiv:2610.14994 Theorem 4.1
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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…
- 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…
Read back from the Lean
Let $M$ be a finite type with decidable equality (representing items), and let $v : \text{Fin } 2 \to \text{Finset } M \to \mathbb{R}$ be a valuation function for two agents. The theorem asserts the conjunction of two statements: 1. For every probability distribution $q$ on allocations $A : M \to \text{Fin } 2$ (that is, $q(A) \ge 0$ for all $A$, and $\sum_A q(A) = 1$) such that the randomized allocation is envy-free under $v$ (that is, for all $i, j \in \text{Fin } 2$, $\sum_A q(A) v(i, A^{-1}(j)) \le \sum_A q(A) v(i, A^{-1}(i))$), and for every vector of strictly positive weights $c : \text{Fin } 2 \to \mathbb{R}$ ($c(i) > 0$ for all $i$), there exists an allocation $A : M \to \text{Fin } 2$ in the support of $q$ ($q(A) > 0$) such that $A$ is envy-freeable under the scaled valuations $(i, S) \mapsto c(i) v(i, S)$. 2. For every property $P$ of valuations and allocations ($P : (\text{Fin } 2 \to \text{Finset } M \to \mathbb{R}) \to (M \to \text{Fin } 2) \to \text{Prop}$) that is invariant under positive scalar multiplication of each agent's valuation (that is, for all valuation profiles $v'$, all $c : \text{Fin } 2 \to \mathbb{R}$ with $c(i) > 0$ for all $i$, and all allocations $A$, $P((i, S) \mapsto c(i) v'(i, S), A) \iff P(v', A)$): There exists a probability distribution $q$ on allocations $A : M \to \text{Fin } 2$ ($q(A) \ge 0$ for all $A$, and $\sum_A q(A) = 1$) that is envy-free in expectation under $v$ (for all $i, j \in \text{Fin } 2$, $\sum_A q(A) v(i, A^{-1}(j)) \le \sum_A q(A) v(i, A^{-1}(i))$) and whose support only contains allocations satisfying $P(v, \cdot)$ (for all $A$, $q(A) > 0 \implies P(v, A)$) if and only if for every vector of strictly positive weights $c : \text{Fin } 2 \to \mathbb{R}$ ($c(i) > 0$ for all $i$), there exists an allocation $A : M \to \text{Fin } 2$ such that $A$ satisfies $P$ under the scaled valuations $(i, S) \mapsto c(i) v(i, S)$ and $A$ is envy-freeable under the scaled valuations $(i, S) \mapsto c(i) v(i, S)$.
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 theorem is proved by combining two core results for two-agent fair division. First, any ex-ante envy-free lottery is shown to contain an envy-freeable allocation under every positive rescaling by applying two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling. Second, the characterization for any scale-free property P is established as an equivalence: the forward direction uses the support result to find an allocation and transfers property P via scale invariance, while the reverse direction applies two_agent_scale_free_lottery_of_envy_freeable_rescalings to construct the lottery from the family of rescaled allocations.
Every ex-ante envy-free lottery contains in its support an allocation that is envy-freeable under any coordinatewise positive rescaling of the valuation profile.
We split the conjunction into its two main claims. To prove the first claim, we fix an ex-ante envy-free lottery q and a coordinatewise positive rescaling vector c. The result follows immediately from the lemma two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling, which guarantees that some allocation A in the support of q is envy-freeable under the rescaled profile c ⊙ v.
uses
two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescalingconstructor · intro q hq_nonneg hq_sum hef c hc exact two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling v q hq_nonneg hq_sum hef c hc
If an ex-ante envy-free lottery supported on allocations with scale-free property P exists, then every positive rescaling admits an allocation that is simultaneously envy-freeable and satisfies P.
We consider an arbitrary scale-free allocation property P and split the equivalence into both directions. For the forward implication, suppose q is an ex-ante envy-free lottery whose support is contained in the set of P-allocations, and let c be any positive rescaling vector. Applying two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling to q and c yields an allocation A with q(A) > 0 that is envy-freeable under c ⊙ v. Since q(A) > 0, A satisfies P under the original valuations v. Because P is scale-free, this implies A also satisfies P under the rescaled profile c ⊙ v, providing the required allocation.
uses
two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling· intro P hP constructor · rintro ⟨q, hnn, hsum, hef, hPq⟩ c hc obtain ⟨A, hqA, hEF⟩ := two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling v q hnn hsum hef c hc exact ⟨A, (hP v c hc A).2 (hPq A hqA), hEF⟩
Conversely, if every positive rescaling admits an envy-freeable allocation satisfying P, then an ex-ante envy-free lottery supported on P-allocations exists.
For the backward direction, we assume that every positive rescaling c ⊙ v admits an allocation that is envy-freeable and satisfies P. The lemma two_agent_scale_free_lottery_of_envy_freeable_rescalings directly constructs an ex-ante envy-free lottery q supported entirely on allocations satisfying P under the original profile v.
uses
two_agent_scale_free_lottery_of_envy_freeable_rescalings· intro h exact two_agent_scale_free_lottery_of_envy_freeable_rescalings v P hP h
two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling- For two agents, any ex-ante envy-free lottery contains in its support an allocation that is envy-freeable under any coordinatewise positive rescaling of the valuations.
two_agent_scale_free_lottery_of_envy_freeable_rescalings- For two agents and any scale-invariant property P, if every coordinatewise positive rescaling admits an allocation that is both envy-freeable and satisfies P, then there exists an ex-ante envy-free lottery supported entirely on allocations satisfying P.
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.
/-- Theorem 4.1 of arXiv:2610.14994: for two agents, ex-ante envy-freeness guarantees existence of an envy-freeable allocation under every positive rescaling, and an ex-ante envy-free lottery with scale-free property P exists if and only if every positive rescaling admits an envy-freeable P-allocation. -/theorem two_agent_converse_theorem {M : Type*} [Fintype M] [DecidableEq M] (v : Fin 2 → Finset M → ℝ) : (∀ (q : (M → Fin 2) → ℝ) (hq_nonneg : ∀ A, 0 ≤ q A) (hq_sum : ∑ A, q A = 1) (hef : ∀ i j, ∑ A, q A * v i (allocation_bundle A j) ≤ ∑ A, q A * v i (allocation_bundle A i)) (c : Fin 2 → ℝ) (hc : ∀ i, 0 < c i), ∃ A : M → Fin 2, 0 < q A ∧ allocation_is_envy_freeable (fun i S => c i * v i S) A) ∧ (∀ (P : (Fin 2 → Finset M → ℝ) → (M → Fin 2) → Prop) (hP : ∀ (v' : Fin 2 → Finset M → ℝ) (c : Fin 2 → ℝ), (∀ i, 0 < c i) → ∀ A, P (fun i S => c i * v' i S) A ↔ P v' A), (∃ q : (M → Fin 2) → ℝ, (∀ A, 0 ≤ q A) ∧ ∑ A, q A = 1 ∧ (∀ i j, ∑ A, q A * v i (allocation_bundle A j) ≤ ∑ A, q A * v i (allocation_bundle A i)) ∧ (∀ A, 0 < q A → P v A)) ↔ (∀ c : Fin 2 → ℝ, (∀ i, 0 < c i) → ∃ A : M → Fin 2, P (fun i S => c i * v i S) A ∧ allocation_is_envy_freeable (fun i S => c i * v i S) A)) := by constructor · intro q hq_nonneg hq_sum hef c hc exact two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling v q hq_nonneg hq_sum hef c hc · intro P hP constructor · rintro ⟨q, hnn, hsum, hef, hPq⟩ c hc obtain ⟨A, hqA, hEF⟩ := two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling v q hnn hsum hef c hc exact ⟨A, (hP v c hc A).2 (hPq A hqA), hEF⟩ · intro h exact two_agent_scale_free_lottery_of_envy_freeable_rescalings v P hP h