AFTD Auto-Formalizing Theoretical Domains

two_agent_envy_freeable_iff

theoremverified

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

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.

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

    lines 8–12

      constructor
      · rintro ⟨p, hp_nonneg, hp_ef⟩
        have h01 := hp_ef 0 1
        have h10 := hp_ef 1 0
        linarith
  2. 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.

    lines 13–15

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

    lines 16–21

        · use ![0, x]
          constructor
          · intro i
            fin_cases i <;> simp [hx]
          · intro i j
            fin_cases i <;> fin_cases j <;> (simp; try linarith)
  4. 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.

    lines 22–27

        · 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

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