AFTD Auto-Formalizing Theoretical Domains

balanced_draft_normalized_utility_bounds

theoremverified

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.

  1. 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.

    lines 7–8

      classical
      let T := draft_rule s (fun j => balanced_draft_value_order (v j)) i
  2. 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.

    lines 9–14

    uses Finset.sum_le_sum_of_subset_of_nonneg, Finset.subset_univ, Finset.sum_nonneg

      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
  3. 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.

    lines 15–18

      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
  4. 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).

    line 19

    uses div_nonneg, mul_nonneg, Nat.cast_nonneg

      · exact div_nonneg (mul_nonneg (Nat.cast_nonneg n) hb) ht
  5. If 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.

    lines 20–21

      · by_cases ht0 : (∑ g : Fin m, v i g) = 0
        · simp [ht0]
  6. 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.

    lines 22–23

    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.

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

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)
See it in the graphDiscuss this resultChallenge it