AFTD Auto-Formalizing Theoretical Domains

TwoFacilityUniversalMechanism

structure

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

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