balanced_draft_normalized_utility_bounds
If an agent assigns nonnegative values to all goods, her normalized utility under any schedule lies between zero and the number of agents, including when total value is zero.
Statement
theorem balanced_draft_normalized_utility_bounds (n m : ℕ) (s : Fin m → Fin n) (v : Fin n → Fin m → ℝ)
(i : Fin n) (hv : ∀ g, 0 ≤ v i g) :
0 ≤ balanced_draft_normalized_utility n m s v i ∧ balanced_draft_normalized_utility n m s v i ≤ n- Source
- Definitions and auxiliary facts for OP-1493, the joint Gaussian limit for balanced sincere drafting.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- balanced_draft_normalized_utilityFor a schedule and a real valuation profile, multiply an agent's sincere-draft bundle value by the number of agents and divide by her…
- balanced_draft_value_orderThe strict preference order induced by a real value vector, ordered first by increasing value and then by increasing good index; hence a…
- draft_ruleGiven types Agent and Object with decidable equality and finite Object, an implicit natural number T, a picking sequence s : Fin T ->…
The proof, explained
The normalized utility of an agent is defined as n times her bundle value divided by her total value across all goods. Since goods have nonnegative values, the bundle value is nonnegative and bounded by the total value. The lower bound (≥ 0) holds because both the numerator and denominator are nonnegative, while the upper bound (≤ n) holds either trivially when the total value is zero (via division by zero yielding 0) or by clearing the positive denominator and scaling the bundle bound by n.
Let T be the set of goods allocated to agent i under the draft rule.
We work in classical logic and define T to be the bundle of goods that agent i receives when agents choose according to their value orderings under schedule s.
classical let T := draft_rule s (fun j => balanced_draft_value_order (v j)) i
The agent's value for bundle T is at most her total value for all goods, and both values are nonnegative.
Since every good has a nonnegative value (hv), summing over the subset T is at most summing over all goods by Finset.sum_le_sum_of_subset_of_nonneg and Finset.subset_univ. Moreover, sums of nonnegative terms are nonnegative by Finset.sum_nonneg, so both the bundle value ∑ g ∈ T, v i g and the total value ∑ g, v i g are nonnegative.
uses
Finset.sum_le_sum_of_subset_of_nonneg,Finset.subset_univ,Finset.sum_nonneghave hs : (∑ g ∈ T, v i g) ≤ ∑ g : Fin m, v i g := by apply Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ T) intro g _ _ exact hv g have ht : 0 ≤ ∑ g : Fin m, v i g := Finset.sum_nonneg fun g _ => hv g have hb : 0 ≤ ∑ g ∈ T, v i g := Finset.sum_nonneg fun g _ => hv g
The goal splits into showing 0 ≤ n * (∑ g ∈ T, v i g) / (∑ g, v i g) and n * (∑ g ∈ T, v i g) / (∑ g, v i g) ≤ n.
Unfolding the definition of balanced_draft_normalized_utility rewrites it as n times the agent's bundle value divided by her total value for all goods. We then split the conjunction into two separate goals for the lower and upper bounds.
unfold balanced_draft_normalized_utility change 0 ≤ (n : ℝ) * (∑ g ∈ T, v i g) / (∑ g : Fin m, v i g) ∧ (n : ℝ) * (∑ g ∈ T, v i g) / (∑ g : Fin m, v i g) ≤ n constructor
The normalized utility is at least zero.
Because n ≥ 0 (by Nat.cast_nonneg) and the bundle value is nonnegative, their product is nonnegative (by mul_nonneg). Dividing this product by the nonnegative total value gives a nonnegative quotient (by div_nonneg).
uses
div_nonneg,mul_nonneg,Nat.cast_nonneg· exact div_nonneg (mul_nonneg (Nat.cast_nonneg n) hb) htIf the total value of all goods is zero, the normalized utility is at most n. automation
We perform a case split on whether the total value is zero. When the total value is zero, division by zero evaluates to 0 in Lean, and simp verifies that 0 ≤ n.
· by_cases ht0 : (∑ g : Fin m, v i g) = 0 · simp [ht0]
If the total value of all goods is nonzero, the normalized utility is at most n.
Since the total value is nonnegative and nonzero, it is strictly positive (by lt_of_le_of_ne and Ne.symm). By div_le_iff₀, dividing by this positive denominator allows clearing the fraction to n * (∑ g ∈ T, v i g) ≤ n * (∑ g, v i g). This inequality follows from multiplying the bundle bound ∑ g ∈ T, v i g ≤ ∑ g, v i g by n ≥ 0 via mul_le_mul_of_nonneg_left and Nat.cast_nonneg.
uses
div_le_iff₀,lt_of_le_of_ne,Ne.symm,mul_le_mul_of_nonneg_left,Nat.cast_nonneg· apply (div_le_iff₀ (lt_of_le_of_ne ht (Ne.symm ht0))).2 exact mul_le_mul_of_nonneg_left hs (Nat.cast_nonneg n)
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t and all elements outside s have nonnegative values, the sum over s is at most the sum over t.
Finset.subset_univ- Every finset of elements of a finite type is a subset of the universal finset.
Finset.sum_nonneg- A finite sum of nonnegative terms is nonnegative.
div_nonneg- The quotient of two nonnegative numbers is nonnegative.
mul_nonneg- The product of two nonnegative numbers is nonnegative.
Nat.cast_nonneg- The coercion of a natural number to an ordered semiring is nonnegative.
div_le_iff₀- For c > 0, b / c ≤ a if and only if b ≤ a * c.
lt_of_le_of_ne- If a ≤ b and a ≠ b, then a < b.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a nonnegative number a preserves the inequality: a * b ≤ a * c.
- In Lean, division by zero is defined to yield zero. When the total value of all goods is zero, the normalized utility evaluates to 0, which trivially satisfies 0 ≤ n.
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.
open MeasureTheory ProbabilityTheory Filteropen scoped BigOperators Topologytheorem balanced_draft_normalized_utility_bounds (n m : ℕ) (s : Fin m → Fin n) (v : Fin n → Fin m → ℝ) (i : Fin n) (hv : ∀ g, 0 ≤ v i g) : 0 ≤ balanced_draft_normalized_utility n m s v i ∧ balanced_draft_normalized_utility n m s v i ≤ n := by classical let T := draft_rule s (fun j => balanced_draft_value_order (v j)) i have hs : (∑ g ∈ T, v i g) ≤ ∑ g : Fin m, v i g := by apply Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ T) intro g _ _ exact hv g have ht : 0 ≤ ∑ g : Fin m, v i g := Finset.sum_nonneg fun g _ => hv g have hb : 0 ≤ ∑ g ∈ T, v i g := Finset.sum_nonneg fun g _ => hv g unfold balanced_draft_normalized_utility change 0 ≤ (n : ℝ) * (∑ g ∈ T, v i g) / (∑ g : Fin m, v i g) ∧ (n : ℝ) * (∑ g ∈ T, v i g) / (∑ g : Fin m, v i g) ≤ n constructor · exact div_nonneg (mul_nonneg (Nat.cast_nonneg n) hb) ht · by_cases ht0 : (∑ g : Fin m, v i g) = 0 · simp [ht0] · apply (div_le_iff₀ (lt_of_le_of_ne ht (Ne.symm ht0))).2 exact mul_le_mul_of_nonneg_left hs (Nat.cast_nonneg n)