two_facility_cost_le_max_cost
For a finite nonempty set of agents, every agent i incurs individual cost under solution c that is at most the max cost of c.
Statement
theorem two_facility_cost_le_max_cost {ι X : Type*} [Fintype ι] [Nonempty ι] [MetricSpace X] (x : ι → X) (p : ι → Fin 2 → Bool) (i : ι) (c : Fin 2 → X) : two_facility_cost x p i c ≤ two_facility_max_cost x p c
- Source
- folklore
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- two_facility_costcost_i(c) = sum over j in {F_1, F_2} of p_ij * d(x_i, c_j).
- 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…
- Used by 2
- two_facility_max_cost_nonnegFor a finite nonempty set of agents, the max cost of any two-facility solution is nonnegative.
- 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
For any finite, nonempty type ι and any metric space X, given a client location map x : ι → X, a facility assignment/indicator function p : ι → Fin 2 → Bool, a client index i : ι, and facility locations c : Fin 2 → X, the cost two_facility_cost x p i c associated with client i is less than or equal to the maximum cost two_facility_max_cost x p c over all clients in ι.
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 maximum cost of a two-facility solution is defined as the supremum of all individual agent costs over the universal set of agents. Because agent i is an element of this universal set, its individual cost is bounded by this supremum directly.
The individual cost for agent i is at most the maximum cost across all agents.
By definition, `two_facility_max_cost x p c` is the supremum (`sup'`) of the cost function over the universal finite set `Finset.univ` of all agents. Since agent i trivially belongs to `Finset.univ` by `Finset.mem_univ`, applying `Finset.le_sup'` establishes that the cost at i is at most this supremum.
uses
Finset.le_sup',Finset.mem_univFinset.le_sup' (fun j => two_facility_cost x p j c) (Finset.mem_univ i)
Finset.le_sup'- For any element b in a finite set s, the value f(b) is less than or equal to the supremum of f over s.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set Finset.univ.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Each agent's individual cost is at most the max cost of the solution. -/theorem two_facility_cost_le_max_cost {ι X : Type*} [Fintype ι] [Nonempty ι] [MetricSpace X] (x : ι → X) (p : ι → Fin 2 → Bool) (i : ι) (c : Fin 2 → X) : two_facility_cost x p i c ≤ two_facility_max_cost x p c := Finset.le_sup' (fun j => two_facility_cost x p j c) (Finset.mem_univ i)