AFTD Auto-Formalizing Theoretical Domains

two_facility_universal_expected_max_cost_nonneg

theoremverified

For any universally strategyproof two-facility mechanism M with finite nonempty index type K on a finite nonempty agent set ι in a metric space X and any position profile x : ι → X, two_facility_universal_expected_max_cost M x is nonnegative (0 ≤ two_facility_universal_expected_max_cost M x).

Statement

theorem two_facility_universal_expected_max_cost_nonneg
    {ι X K : Type*} [DecidableEq ι] [Fintype ι] [Nonempty ι] [MetricSpace X] [Fintype K] [Nonempty K]
    {C : Finset X} {p : ι → Fin 2 → Bool}
    (M : TwoFacilityUniversalMechanism C p K) (x : ι → X) :
    0 ≤ two_facility_universal_expected_max_cost M x
Source
folklore
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • two_facility_universal_expected_max_costGiven types ι, X, and K with DecidableEq ι, Fintype ι, Nonempty ι, MetricSpace X, Fintype K, and Nonempty K, a candidate set C : Finset X,…
  • two_facility_max_cost_nonnegFor a finite nonempty set of agents, the max cost of any two-facility solution is nonnegative.
  • TwoFacilityUniversalMechanismGiven types ι and X with DecidableEq ι and MetricSpace X, a finite set C : Finset X of candidate locations, an approval preference profile…
  • two_facility_max_costGiven a finite and nonempty set of agents ι, a metric space X, agent positions x, approval preferences p, and facility locations c, the…

Read back from the Lean

For any finite, nonempty type ι with decidable equality, any metric space X, and any finite, nonempty type K, given a finite subset C of X, an agent-to-facility requirement function p : ι → Fin 2 → Bool, a universal two-facility mechanism M (a randomized mechanism represented as a distribution over deterministic mechanisms indexed by K, where each deterministic mechanism is feasible with respect to C and strategyproof with respect to p), and a location profile x : ι → X, the expected maximum cost two_facility_universal_expected_max_cost M x is greater than or equal to 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The expected maximum cost of a universally strategyproof two-facility mechanism is defined as the convex combination of the deterministic maximum costs of its constituent mechanisms. Since the distribution weights in the standard simplex are nonnegative and each individual mechanism's maximum cost is nonnegative by `two_facility_max_cost_nonneg`, every term in the sum is a product of nonnegative numbers. Consequently, the entire sum is nonnegative.

  1. The goal is rewritten as showing that the weighted sum over all constituent mechanisms, ∑ k, M.weights k * two_facility_max_cost x p (M.mech k x), is nonnegative.

    Unfolding the definition of `two_facility_universal_expected_max_cost` expands the expected maximum cost into an explicit sum over the index type K of each mechanism's probability weight multiplied by its deterministic maximum cost.

    line 7

      unfold two_facility_universal_expected_max_cost
  2. The expected maximum cost is nonnegative.

    By `Finset.sum_nonneg`, a finite sum is nonnegative if every term is nonnegative. For each index k, the summand is a product of two factors: the weight `M.weights k`, which is nonnegative because the weights lie in the standard simplex (`M.weights_mem.1`), and the deterministic maximum cost, which is nonnegative by `two_facility_max_cost_nonneg`. Hence, each summand is nonnegative by `mul_nonneg`, which closes the goal.

    lines 8–9

    uses Finset.sum_nonneg, mul_nonneg, two_facility_max_cost_nonneg

      exact Finset.sum_nonneg fun k _ =>
        mul_nonneg (M.weights_mem.1 k) (two_facility_max_cost_nonneg x p (M.mech k x))
Finset.sum_nonneg
A finite sum of nonnegative terms is nonnegative.
mul_nonneg
The product of two nonnegative numbers is nonnegative.
two_facility_max_cost_nonneg
For any agent positions, preference profile, and facility locations, the maximum two-facility cost among agents is nonnegative.

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

/-- The expected max cost of a universally strategyproof two-facility mechanism is nonnegative. -/theorem two_facility_universal_expected_max_cost_nonneg    {ι X K : Type*} [DecidableEq ι] [Fintype ι] [Nonempty ι] [MetricSpace X] [Fintype K] [Nonempty K]    {C : Finset X} {p : ι → Fin 2 → Bool}    (M : TwoFacilityUniversalMechanism C p K) (x : ι → X) :    0 ≤ two_facility_universal_expected_max_cost M x := by  unfold two_facility_universal_expected_max_cost  exact Finset.sum_nonneg fun k _ =>    mul_nonneg (M.weights_mem.1 k) (two_facility_max_cost_nonneg x p (M.mech k x))
See it in the graphDiscuss this resultChallenge it