TwoFacilityUniversalMechanism
Given types ι and X with DecidableEq ι and MetricSpace X, a finite set C : Finset X of candidate locations, an approval preference profile p : ι → Fin 2 → Bool, and a finite nonempty index type K with Fintype K and Nonempty K, a universally strategyproof mechanism TwoFacilityUniversalMechanism C p K consists of a weight function weights : K → ℝ satisfying weights ∈ stdSimplex ℝ K, and a family of deterministic mechanisms mech : K → (ι → X) → Fin 2 → X such that for every k : K and profile x : ι → X, mech k x is feasible in C (IsTwoFacilityFeasible C (mech k x)), and for every k : K, mech k is strategyproof with respect to p (IsTwoFacilityStrategyproof p (mech k)).
Statement
structure TwoFacilityUniversalMechanism {ι X : Type*} [DecidableEq ι] [MetricSpace X] (C : Finset X) (p : ι → Fin 2 → Bool) (K : Type*) [Fintype K] [Nonempty K]
- 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
- IsTwoFacilityStrategyproofIn the two-facility location problem on a metric space X with agent set ι and approval preferences p, a deterministic mechanism M : (ι →…
- IsTwoFacilityFeasiblec = (c_1, c_2) is feasible iff c_1, c_2 ∈ C and c_1 ≠ c_2.
- Used by 3
- 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…
- 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,…
Read back from the Lean
A structure TwoFacilityUniversalMechanism parameterized by:
- Types ι (with decidable equality) and X (equipped with a metric space structure),
- A finite subset C : Finset X of candidate facility locations,
- A preference table p : ι → Fin 2 → Bool indicating which facilities each agent i : ι uses,
- A finite, nonempty type K of constituent deterministic mechanisms,
consisting of:
1. weights : K → ℝ, a probability weighting on K,
2. weights_mem: proof that weights belongs to the standard simplex stdSimplex ℝ K (i.e., non-negative weights summing to 1),
3. mech : K → (ι → X) → (Fin 2 → X): for each k : K, a deterministic mechanism mapping a profile of agent locations x : ι → X to locations for two facilities Fin 2 → X,
4. feasible: a proof that for every k : K and every profile x : ι → X, the mechanism mech k x is feasible on C, meaning both facilities are placed at locations in C and the two facility locations are distinct,
5. strategyproof: a proof that for every k : K, the mechanism mech k is strategy-proof with respect to p, meaning no agent can lower their total distance to their required facilities by unilaterally misreporting their location.
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 parameterized by a finite index type K is a convex combination of deterministic strategyproof mechanisms. -/ structure TwoFacilityUniversalMechanism {ι X : Type*} [DecidableEq ι] [MetricSpace X] (C : Finset X) (p : ι → Fin 2 → Bool) (K : Type*) [Fintype K] [Nonempty K] where weights : K → ℝ weights_mem : weights ∈ stdSimplex ℝ K mech : K → (ι → X) → (Fin 2 → X) feasible : ∀ k x, IsTwoFacilityFeasible C (mech k x) strategyproof : ∀ k, IsTwoFacilityStrategyproof p (mech k)