tfx_core
theoremverified
Core case analysis: with three rounds of the goods {z, a, b} (values 0, 1, x), no allocation (given by its nine entries) is α-TEFX as soon as α x > 2, 2αx > x + 2 and α(x + 2) > x.
Statement
theorem tfx_core (α x : ℝ) (hα0 : 0 < α) (hx0 : 0 < x) (h1 : 2 < α * x)
(h2 : 2 + x < 2 * (α * x)) (h3 : x < 2 * α + α * x)
(a00 a01 a02 a10 a11 a12 a20 a21 a22 : Fin 2)
(h : tfx_alphaTEFX α (tfx_val x) (![![a00, a01, a02], ![a10, a11, a12], ![a20, a21, a22]] : Fin 3 → Fin 3 → Fin 2)) :
False- Source
- step towards tfx_identical_days_upper_bound (approximation ratio of TEFX on identical days, open in arXiv:2607.17224, Sec. 7)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- tfx_alphaTEFXα-TEFX: the cumulative allocation is α-EFX after every round.
- tfx_valThe identical valuation used in the counterexample: good types z, a, b worth 0, 1, x.
- tfx_round1Round 1 of the counterexample: the agent receiving b must receive nothing else.
- tfx_round2ARound 2 of the counterexample after round-1 allocation 1, 1, 0.
- tfx_round2BRound 2 of the counterexample after round-1 allocation 0, 0, 1.
- tfx_round3_1Round 3 of the counterexample after rounds 1–2 allocations 1, 1, 0 and 1, 0, 1: every allocation of the third round violates α-EFX.
- tfx_round3_2Round 3 of the counterexample after rounds 1–2 allocations 1, 1, 0 and 0, 0, 1: every allocation of the third round violates α-EFX.
- tfx_round3_3Round 3 of the counterexample after rounds 1–2 allocations 0, 0, 1 and 1, 1, 0: every allocation of the third round violates α-EFX.
- tfx_round3_4Round 3 of the counterexample after rounds 1–2 allocations 0, 0, 1 and 0, 1, 0: every allocation of the third round violates α-EFX.
- Used by 1
- tfx_no_alphaTEFXFor the explicit instance with values 0, 1, x and three identical rounds, no allocation is α-TEFX whenever α x > 2, 2αx > x + 2 and α(x +…
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.
/-- Core case analysis: with three rounds of the goods `{z, a, b}` (values `0, 1, x`), no allocation (given by its nine entries) is `α`-TEFX as soon as `α x > 2`, `2αx > x + 2` and `α(x + 2) > x`. -/theorem tfx_core (α x : ℝ) (hα0 : 0 < α) (hx0 : 0 < x) (h1 : 2 < α * x) (h2 : 2 + x < 2 * (α * x)) (h3 : x < 2 * α + α * x) (a00 a01 a02 a10 a11 a12 a20 a21 a22 : Fin 2) (h : tfx_alphaTEFX α (tfx_val x) (![![a00, a01, a02], ![a10, a11, a12], ![a20, a21, a22]] : Fin 3 → Fin 3 → Fin 2)) : False := by have d0 := h 0 (by norm_num) have d1 := h 1 (by norm_num) have d2 := h 2 (by norm_num) rcases tfx_round1 α x hα0 hx0 h1 h2 h3 _ _ _ _ _ _ _ _ _ d0 with ⟨rfl, rfl, rfl⟩ | ⟨rfl, rfl, rfl⟩ · rcases tfx_round2A α x hα0 hx0 h1 h2 h3 _ _ _ _ _ _ d1 with ⟨rfl, rfl, rfl⟩ | ⟨rfl, rfl, rfl⟩ · exact tfx_round3_1 α x hα0 hx0 h1 h2 h3 _ _ _ d2 · exact tfx_round3_2 α x hα0 hx0 h1 h2 h3 _ _ _ d2 · rcases tfx_round2B α x hα0 hx0 h1 h2 h3 _ _ _ _ _ _ d1 with ⟨rfl, rfl, rfl⟩ | ⟨rfl, rfl, rfl⟩ · exact tfx_round3_3 α x hα0 hx0 h1 h2 h3 _ _ _ d2 · exact tfx_round3_4 α x hα0 hx0 h1 h2 h3 _ _ _ d2