AFTD Auto-Formalizing Theoretical Domains

two_facility_universal_expected_max_cost

def

Given types ι, X, and K with DecidableEq ι, Fintype ι, Nonempty ι, MetricSpace X, Fintype K, and Nonempty K, a candidate set C : Finset X, a preference profile p : ι → Fin 2 → Bool, a universally strategyproof mechanism M : TwoFacilityUniversalMechanism C p K, and an agent position profile x : ι → X, two_facility_universal_expected_max_cost M x is the sum over k : K of M.weights k * two_facility_max_cost x p (M.mech k x).

Statement

noncomputable def two_facility_universal_expected_max_cost
    {ι X K : Type*} [DecidableEq ι] [Fintype ι] [Nonempty ι] [MetricSpace X] [Fintype K] [Nonempty K]
    {C : Finset X} {p : ι → Fin 2 → Bool}
    (M : TwoFacilityUniversalMechanism C p K) (x : ι → X) : ℝ
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
  • TwoFacilityUniversalMechanismGiven types ι and X with DecidableEq ι and MetricSpace X, a finite set C : Finset X of candidate locations, an approval preference profile…
  • 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…
Used by 2

Read back from the Lean

A definition that, given: - a finite, non-empty type ι of agents with decidable equality, - a metric space X, - a finite, non-empty type K indexing deterministic mechanisms, - a finite set C of candidate locations in X (implicit), - a preference/assignment matrix p : ι → Fin 2 → Bool indicating which facilities each agent requires (implicit), - a universally strategyproof two-facility mechanism M : TwoFacilityUniversalMechanism C p K, - and an agent location profile x : ι → X, computes the real number equal to the expected maximum cost across agents under the randomized mechanism M on profile x. Specifically, it is the sum over k : K of M.weights k multiplied by the maximum over agents i : ι of the two-facility cost of agent i under the deterministic mechanism M.mech k applied to 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

/-- The expected max cost of a universally strategyproof mechanism on an agent position profile x. -/
noncomputable def two_facility_universal_expected_max_cost
    {ι X K : Type*} [DecidableEq ι] [Fintype ι] [Nonempty ι] [MetricSpace X] [Fintype K] [Nonempty K]
    {C : Finset X} {p : ι → Fin 2 → Bool}
    (M : TwoFacilityUniversalMechanism C p K) (x : ι → X) : ℝ := ∑ k : K, M.weights k * two_facility_max_cost x p (M.mech k x)
See it in the graphDiscuss this resultChallenge it