two_facility_universal_expected_max_cost
Given types ι, X, and K with DecidableEq ι, Fintype ι, Nonempty ι, MetricSpace X, Fintype K, and Nonempty K, a candidate set C : Finset X, a preference profile p : ι → Fin 2 → Bool, a universally strategyproof mechanism M : TwoFacilityUniversalMechanism C p K, and an agent position profile x : ι → X, two_facility_universal_expected_max_cost M x is the sum over k : K of M.weights k * two_facility_max_cost x p (M.mech k x).
Statement
noncomputable def two_facility_universal_expected_max_cost {ι 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) : ℝ
- Defined in
- scout/2610-18006-truthful-two-facility-location-with-candidate-locations-in.md:202
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 2
- 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…
- Used by 2
- TwoFacilityUniversalMechanismHasApproxRatioGiven types ι, X, and K with DecidableEq ι, Fintype ι, Nonempty ι, MetricSpace X, Fintype K, and Nonempty K, candidate set C : Finset X,…
- 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…
Read back from the Lean
A definition that, given:
- a finite, non-empty type ι of agents with decidable equality,
- a metric space X,
- a finite, non-empty type K indexing deterministic mechanisms,
- a finite set C of candidate locations in X (implicit),
- a preference/assignment matrix p : ι → Fin 2 → Bool indicating which facilities each agent requires (implicit),
- a universally strategyproof two-facility mechanism M : TwoFacilityUniversalMechanism C p K,
- and an agent location profile x : ι → X,
computes the real number equal to the expected maximum cost across agents under the randomized mechanism M on profile x. Specifically, it is the sum over k : K of M.weights k multiplied by the maximum over agents i : ι of the two-facility cost of agent i under the deterministic mechanism M.mech k applied to x.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The expected max cost of a universally strategyproof mechanism on an agent position profile x. -/ noncomputable def two_facility_universal_expected_max_cost {ι 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) : ℝ := ∑ k : K, M.weights k * two_facility_max_cost x p (M.mech k x)