Theorem 4.1 — lower bound on uniform group structures
OpenFairFacilityLoc.Supplement.theorem_4_1_lower_boundalgorithmic-game-theoryfacility-locationmechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a positive dimension . Every deterministic mechanism that is strategyproof and anonymous has approximation ratio at least
even when the worst-case supremum is restricted to uniform group structures: disjoint equal-size groups partitioning the agents, with linear weight for every member of a size- group.
This is the paper’s matching lower bound. It applies to mechanisms that choose coordinates jointly and assumes neither coordinate independence nor continuity.
Formalization Note Determinism is built into the mechanism type. The restricted ratio is in with the paper’s zero-denominator conventions.
Differences from the source:
- encoding: every dimension → a natural number with and locations in
EuclideanSpace ℝ (Fin d); reason: the paper works in positive finite-dimensional Euclidean space - encoding: uniform linear groups with equal sizes and total masses, normalized on p.51 to weight →
IsUniformrequires the displayed normalized weight ; reason: this is the paper’s explicit normalization and common rescaling changes no ratio - encoding: approximation ratio at least on uniform structures → an inequality in against the restricted supremum
uniformRatio; reason: it preserves the conventions and
Preamble
import Mathlib import Definitions.Def_FairFacilityLoc_IsStrategyproof import Definitions.Def_FairFacilityLoc_alpha import Definitions.Def_FairFacilityLoc_Supplement_uniformRatio open scoped ENNReal
Formal statement
namespace FairFacilityLoc.Supplement
set_option autoImplicit false
/-- **Theorem 4.1 (Lower bound)** (Yan–Zhou, *Fair and Strategyproof Facility Location in
Euclidean Space*, manuscript, sha256 642a1268…, p.52, PDF p.54). Every deterministic,
strategyproof, anonymous mechanism has approximation ratio at least `α_d`, even when the
supremum is restricted to uniform group structures.
**Formalization Note.** Determinism is built into `FairFacilityLoc.Mechanism`. `uniformRatio`
uses the paper's normalization: disjoint equal-size groups partition the agents and every member
of a size-`K` group has weight `1/K`, so every group has total mass one. No coordinate
independence, continuity, unanimity, or finite-ratio hypothesis is imposed. -/
theorem theorem_4_1_lower_bound (d : ℕ) (hd : 1 ≤ d) (M : FairFacilityLoc.Mechanism d)
(hsp : FairFacilityLoc.IsStrategyproof M) (han : FairFacilityLoc.IsAnonymous M) :
ENNReal.ofReal (FairFacilityLoc.alpha d) ≤ uniformRatio M := by sorry
end FairFacilityLoc.Supplement
Source
Yan, Zhou, Fair and Strategyproof Facility Location in Euclidean Space, manuscript (sha256 642a1268…), Theorem 4.1, p.52 (PDF p.54)