two_facility_max_cost_nonneg
For a finite nonempty set of agents, the max cost of any two-facility solution is nonnegative.
Statement
theorem two_facility_max_cost_nonneg {ι X : Type*} [Fintype ι] [Nonempty ι] [MetricSpace X] (x : ι → X) (p : ι → Fin 2 → Bool) (c : Fin 2 → X) : 0 ≤ two_facility_max_cost x p c
- Source
- folklore
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- two_facility_cost_nonnegSanity: every individual cost is nonnegative.
- two_facility_cost_le_max_costFor a finite nonempty set of agents, every agent i incurs individual cost under solution c that is at most the max cost of c.
- 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…
- two_facility_costcost_i(c) = sum over j in {F_1, F_2} of p_ij * d(x_i, c_j).
- Used by 3
- two_facility_universal_expected_max_cost_nonnegFor any universally strategyproof two-facility mechanism M with finite nonempty index type K on a finite nonempty agent set ι in a metric…
- fixed_dictator_max_cost_leOn general metric spaces, in the two-facility location problem with candidate locations C and a finite nonempty set of n ≥ 2 agents with…
- fixed_dictator_max_cost_le_of_singletonsIn the two-facility location problem on a metric space with a finite nonempty set of agents, if no agent approves both facilities, agent i…
Read back from the Lean
Given a finite, nonempty type ι, a metric space X, a function x : ι → X, a boolean indicator function p : ι → Fin 2 → Bool, and a function c : Fin 2 → X, the value two_facility_max_cost x p c 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
To show that the maximum cost is nonnegative, we choose an arbitrary agent from the nonempty set of agents. The cost incurred by this agent is nonnegative, and by definition, any individual agent's cost is at most the maximum cost across all agents. Transitivity of inequality then implies that the maximum cost is at least zero.
There exists an agent i in ι.
By assumption, the index set ι of agents is nonempty, so we may choose an arbitrary agent i.
obtain ⟨i⟩ := ‹Nonempty ι›0 ≤ two_facility_max_cost x p c
The cost for agent i is nonnegative (by two_facility_cost_nonneg) and is bounded above by the maximum cost over all agents (by two_facility_cost_le_max_cost). Combining these two inequalities using transitivity (le_trans) establishes that the maximum cost is at least 0.
uses
le_trans,two_facility_cost_nonneg,two_facility_cost_le_max_costexact le_trans (two_facility_cost_nonneg x p i c) (two_facility_cost_le_max_cost x p i c)
le_trans- If a ≤ b and b ≤ c, then a ≤ c (transitivity of inequality).
two_facility_cost_nonneg- The two-facility cost for any individual agent is nonnegative.
two_facility_cost_le_max_cost- The two-facility cost for any individual agent is at most the maximum cost across all agents.
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 max cost of any two-facility solution is nonnegative. -/theorem two_facility_max_cost_nonneg {ι X : Type*} [Fintype ι] [Nonempty ι] [MetricSpace X] (x : ι → X) (p : ι → Fin 2 → Bool) (c : Fin 2 → X) : 0 ≤ two_facility_max_cost x p c := by obtain ⟨i⟩ := ‹Nonempty ι› exact le_trans (two_facility_cost_nonneg x p i c) (two_facility_cost_le_max_cost x p i c)