Step 1, p. 25 — 1/n + θ/(n−1)(x̄/x_i − 1) ≥ 0 and its sum over N is ≥ 1, strictly off the diagonal for θ ≠ 0
ProvedFairRandomObject.Bads.step_1bottom-heavy-rulefair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , and let be a profile with for all . Write . Then
- for every ;
- ;
- if and is not parallel to (its coordinates are not all equal), the inequality in 2 is strict.
These facts make the Bottom-Heavy family (13) well defined: the shares are non-negative and the prefix sums eventually exceed .
Preamble
import Mathlib import Definitions.Def_FairRandomObject_Bads_Setting import Definitions.Def_FairRandomObject_Bads_BottomHeavy
Formal statement
namespace FairRandomObject.Bads
/-- Bogomolnaia, Moulin, Sandomirskiy, On the Fair Division of a Random Object, arXiv:1903.10361v4, p. 25, Step 1 of the proof of Theorem 17: for `θ ∈ [0, 1]` and a profile
with all `x_i > 0`, each `1/n + θ/(n−1)(x̄/x_i − 1)` is non-negative and their sum over `N` is
at least `1`, strictly if `x` is not parallel to `e^N` and `θ ≠ 0`. This is why (13) is well
defined.
**Formalization Note.** "Parallel to `e^N`" is "all coordinates equal". The positivity
`x_i > 0` is required since `x̄/x_i` is undefined (the paper's `+∞`) at `x_i = 0`. -/
theorem step_1 {n : ℕ} (hn : 2 ≤ n) (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ1 : θ ≤ 1)
(x : Fin n → ℝ) (hx : ∀ i, 0 < x i) :
(∀ i, 0 ≤ psi n θ x i) ∧ 1 ≤ ∑ i, psi n θ x i ∧
(θ ≠ 0 → (¬ ∃ c : ℝ, ∀ i, x i = c) → 1 < ∑ i, psi n θ x i) := by sorry
end FairRandomObject.Bads
Source
Bogomolnaia, Moulin, Sandomirskiy, On the Fair Division of a Random Object, arXiv:1903.10361v4, p. 25, proof of Theorem 17, Step 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.