AFTD Auto-Formalizing Theoretical Domains

IsTwoFacilityStrategyproof

def

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