AFTD Auto-Formalizing Theoretical Domains

two_facility_cost_le_max_cost

theoremverified

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

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.

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

    line 5

    uses Finset.le_sup', Finset.mem_univ

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