TwoFacilityUniversalMechanismHasApproxRatio
Given types ι, X, and K with DecidableEq ι, Fintype ι, Nonempty ι, MetricSpace X, Fintype K, and Nonempty K, candidate set C : Finset X, preference profile p : ι → Fin 2 → Bool, a universally strategyproof mechanism M : TwoFacilityUniversalMechanism C p K, and a real number α, TwoFacilityUniversalMechanismHasApproxRatio M α asserts that for every position profile x : ι → X and every feasible solution o : Fin 2 → X (satisfying IsTwoFacilityFeasible C o), two_facility_universal_expected_max_cost M x ≤ α * two_facility_max_cost x p o.
Statement
def TwoFacilityUniversalMechanismHasApproxRatio {ι X K : Type*} [DecidableEq ι] [Fintype ι] [Nonempty ι] [MetricSpace X] [Fintype K] [Nonempty K] {C : Finset X} {p : ι → Fin 2 → Bool} (M : TwoFacilityUniversalMechanism C p K) (α : ℝ) : Prop
- Defined in
- scout/2610-18006-truthful-two-facility-location-with-candidate-locations-in.md:194
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 4
- TwoFacilityUniversalMechanismGiven types ι and X with DecidableEq ι and MetricSpace X, a finite set C : Finset X of candidate locations, an approval preference profile…
- 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_costGiven a finite and nonempty set of agents ι, a metric space X, agent positions x, approval preferences p, and facility locations c, the…
- IsTwoFacilityFeasiblec = (c_1, c_2) is feasible iff c_1, c_2 ∈ C and c_1 ≠ c_2.
Read back from the Lean
Let $ι$ be a finite, nonempty type with decidable equality, $X$ a metric space, $K$ a finite, nonempty type, $C$ a finite subset of $X$, and $p : ι → \mathrm{Fin}\ 2 → \mathrm{Bool}$ a requirement function indicating which facilities each agent connects to.
Given a universal two-facility mechanism $M$ (a probability distribution over $K$ given by weights in the standard simplex, together with a family of deterministic mechanisms indexed by $K$ that are each feasible for $C$ and strategyproof with respect to $p$) and a real number $α$, the declaration TwoFacilityUniversalMechanismHasApproxRatio M α asserts that:
For every agent location profile $x : ι → X$ and every two-facility placement $o : \mathrm{Fin}\ 2 → X$,
if $o$ is feasible (that is, $o(0) \in C$, $o(1) \in C$, and $o(0) \neq o(1)$),
then the expected maximum cost across agents under $M$ on input $x$ is at most $α$ times the maximum cost across agents under the placement $o$ on input $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
/-- A universally strategyproof mechanism has approximation ratio at most α for max cost if its expected max cost is at most α times the optimal max cost on every profile. -/ def TwoFacilityUniversalMechanismHasApproxRatio {ι X K : Type*} [DecidableEq ι] [Fintype ι] [Nonempty ι] [MetricSpace X] [Fintype K] [Nonempty K] {C : Finset X} {p : ι → Fin 2 → Bool} (M : TwoFacilityUniversalMechanism C p K) (α : ℝ) : Prop := ∀ (x : ι → X) (o : Fin 2 → X), IsTwoFacilityFeasible C o → two_facility_universal_expected_max_cost M x ≤ α * two_facility_max_cost x p o