scaled_common_ratio_bivalued_efx_fpo_envyfreeable_zero_goods
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`.
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.
uses
Fin.elim0refine ⟨Fin.elim0, fun _ => 0, ?_, ?_, ?_⟩
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.
· intro i j hij g hg simp [bundle_of] at hg
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.
· simp [is_envy_free_with_subsidy, additive_valuation, bundle_of]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.
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
- In the EFX step, `simp [bundle_of] at hg` closes the goal because the set of goods `Fin 0` is empty, reducing the assumption `g ∈ bundle_of Fin.elim0 j` to `False`.
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.
/-- 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