AFTD Auto-Formalizing Theoretical Domains

two_agent_converse_theorem

theoremverifiedformalization

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

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.

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

    lines 20–22

    uses two_agent_ex_ante_ef_lottery_exists_envy_freeable_rescaling

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

    lines 23–28

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

    lines 29–30

    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

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