two_facility_universal_expected_max_cost_nonneg
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.
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.
unfold two_facility_universal_expected_max_costThe 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.
uses
Finset.sum_nonneg,mul_nonneg,two_facility_max_cost_nonnegexact 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.
- The nonnegativity of the mechanism weights is obtained as `M.weights_mem.1`, which extracts the first conjunct (∀ k, 0 ≤ weights k) from the definition of the standard simplex.
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.
/-- 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))