AFTD Auto-Formalizing Theoretical Domains

scaled_common_ratio_bivalued_efx_fpo_envyfreeable_zero_goods

theoremverified

When m = 0, the empty allocation Fin.elim0 and zero subsidy vector 0 satisfy EFX, envy-freeness with subsidies, and fractional Pareto optimality.

Statement

theorem scaled_common_ratio_bivalued_efx_fpo_envyfreeable_zero_goods
    (n : ℕ) (hn : 2 ≤ n)
    (r : ℝ) (hr : 1 < r)
    (a : Fin n → ℝ) (ha : ∀ i, 0 < a i)
    (v : Fin n → Fin 0 → ℝ) (hv : ∀ i g, v i g = a i ∨ v i g = r * a i) :
    ∃ (σ : Fin 0 → Fin n) (s : Fin n → ℝ),
      is_efx_goods v σ ∧
      is_envy_free_with_subsidy (fun i => additive_valuation (v i)) σ s ∧
      is_fractionally_pareto_optimal v σ
Source
step towards scaled_common_ratio_bivalued_efx_fpo_envyfreeable
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • is_fractionally_pareto_optimalAn allocation of goods σ is fractionally Pareto optimal for additive valuations u if no fractional assignment x weakly improves every…
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
  • is_fractionally_pareto_optimal_zero_goodsWhen there are no goods, every complete allocation is fractionally Pareto optimal.
  • 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.

The proof, explained

When there are zero goods to allocate, the theorem is witnessed by the empty allocation and the zero subsidy vector. EFX holds vacuously because no agent receives any goods to be eliminated. Envy-freeness with subsidies holds because every bundle has valuation zero and subsidies are zero, so no envy exists. Finally, fractional Pareto optimality of any allocation of zero goods is established by the lemma `is_fractionally_pareto_optimal_zero_goods`.

  1. To show the existential statement, it suffices to show that the empty allocation and zero subsidy vector satisfy EFX, envy-freeness with subsidies, and fractional Pareto optimality.

    We provide the empty allocation `Fin.elim0` (the unique function from `Fin 0` to `Fin n`) and the zero subsidy vector (`fun _ => 0`) as explicit witnesses, splitting the existential goal into three independent subgoals for the required properties.

    line 11

    uses Fin.elim0

      refine ⟨Fin.elim0, fun _ => 0, ?_, ?_, ?_⟩
  2. The empty allocation satisfies EFX (envy-freeness up to any good).

    To prove EFX, we assume for distinct agents `i ≠ j` that there is some good `g` in the bundle of agent `j`. Since there are no goods (`Fin 0`), the bundle of agent `j` is empty; simplifying `bundle_of` in the hypothesis derives a contradiction (`g ∈ ∅`), closing the goal vacuously.

    lines 12–13

      · intro i j hij g hg
        simp [bundle_of] at hg
  3. The empty allocation with zero subsidies is envy-free with subsidies.

    Envy-freeness with subsidies requires non-negative subsidies and that no agent envies another agent's bundle plus subsidy. Since each agent receives the empty bundle with valuation 0 and a subsidy of 0, all subsidies satisfy `0 ≤ 0` and every envy comparison reduces to `0 + 0 ≤ 0 + 0`, which the simplifier closes.

    line 14

      · simp [is_envy_free_with_subsidy, additive_valuation, bundle_of]
  4. The empty allocation is fractionally Pareto optimal.

    Fractional Pareto optimality holds directly by invoking `is_fractionally_pareto_optimal_zero_goods`, which asserts that any allocation of zero goods is fractionally Pareto optimal.

    line 15

    uses is_fractionally_pareto_optimal_zero_goods, Fin.elim0

      · exact is_fractionally_pareto_optimal_zero_goods n v Fin.elim0
Fin.elim0
the unique function from the empty type `Fin 0` to any type `α`, representing the empty allocation when there are zero goods
is_fractionally_pareto_optimal_zero_goods
for any number of agents and additive valuation functions, any allocation of zero goods is fractionally Pareto optimal

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

/-- For zero indivisible goods, the empty allocation with zero subsidies is EFX, envy-free with subsidies, and fractionally Pareto optimal. -/theorem scaled_common_ratio_bivalued_efx_fpo_envyfreeable_zero_goods    (n : ℕ) (hn : 2 ≤ n)    (r : ℝ) (hr : 1 < r)    (a : Fin n → ℝ) (ha : ∀ i, 0 < a i)    (v : Fin n → Fin 0 → ℝ) (hv : ∀ i g, v i g = a i ∨ v i g = r * a i) :    ∃ (σ : Fin 0 → Fin n) (s : Fin n → ℝ),      is_efx_goods v σ ∧      is_envy_free_with_subsidy (fun i => additive_valuation (v i)) σ s ∧      is_fractionally_pareto_optimal v σ := by  refine ⟨Fin.elim0, fun _ => 0, ?_, ?_, ?_⟩  · intro i j hij g hg    simp [bundle_of] at hg  · simp [is_envy_free_with_subsidy, additive_valuation, bundle_of]  · exact is_fractionally_pareto_optimal_zero_goods n v Fin.elim0
See it in the graphDiscuss this resultChallenge it