IsTwoFacilityStrategyproof
In the two-facility location problem on a metric space X with agent set ι and approval preferences p, a deterministic mechanism M : (ι → X) → (Fin 2 → X) is strategyproof if for every position profile x : ι → X, every agent i : ι, and every misreport x' : X, the cost of agent i under M x is at most the cost of agent i under M applied to the profile where agent i's position is updated to x'.
Statement
def IsTwoFacilityStrategyproof {ι X : Type*} [DecidableEq ι] [MetricSpace X] (p : ι → Fin 2 → Bool) (M : (ι → X) → (Fin 2 → X)) : Prop
- Defined in
- scout/2610-18006-truthful-two-facility-location-with-candidate-locations-in.md:197
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 1
- two_facility_costcost_i(c) = sum over j in {F_1, F_2} of p_ij * d(x_i, c_j).
- Used by 1
- TwoFacilityUniversalMechanismGiven types ι and X with DecidableEq ι and MetricSpace X, a finite set C : Finset X of candidate locations, an approval preference profile…
Read back from the Lean
Let ι be a type with decidable equality, X a metric space, p : ι → Fin 2 → Bool a function specifying each agent's connection to each of two facilities, and M : (ι → X) → (Fin 2 → X) a two-facility location mechanism. The predicate IsTwoFacilityStrategyproof p M asserts that for every location profile x : ι → X, every agent i : ι, and every reported alternative location x' : X, the two-facility cost to agent i under mechanism output M x is less than or equal to the two-facility cost to agent i (evaluated with respect to i's true location x i) under mechanism output M (Function.update x i 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 deterministic two-facility mechanism is strategyproof if no agent can reduce her cost by misreporting her position. -/ def IsTwoFacilityStrategyproof {ι X : Type*} [DecidableEq ι] [MetricSpace X] (p : ι → Fin 2 → Bool) (M : (ι → X) → (Fin 2 → X)) : Prop := ∀ (x : ι → X) (i : ι) (x' : X), two_facility_cost x p i (M x) ≤ two_facility_cost x p i (M (Function.update x i x'))