Theorem E.3 — no finite ratio on superlinear group effects
OpenFairFacilityLoc.Supplement.theorem_E_3algorithmic-game-theoryfacility-locationmechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a positive dimension and . The function
is a nonzero, monotone, symmetric and superlinear group effect, and .
Every deterministic strategyproof mechanism has ratio at least
on the fixed structure of two disjoint two-agent groups, both using . Consequently, the supremum of its ratio over all superlinear group effects is infinite. This holds in every positive dimension and requires neither anonymity, continuity nor coordinate independence.
The finite bound belongs to each fixed ; the infinite class-wide conclusion ranges over the whole family as approaches zero.
Formalization Note The ratio is valued in with and for .
Differences from the source:
- encoding: every dimension → a natural number with and locations in
EuclideanSpace ℝ (Fin d); reason: the paper’s Euclidean dimensions are positive - encoding: real and on two nonnegative real coordinates →
ε : ℝ≥0with the same strict bounds andepsilonEffect ε : (Fin 2 → ℝ≥0) → ℝ≥0; reason: positivity makes the parameter nonnegative, andFin 2is the same two-coordinate domain with 0-based indexing - encoding: the group structure of Lemma E.2 →
epsilonTwoByTwo εonFin 4agents andFin 2groups; reason: it fixes labels for the same two disjoint two-agent groups - encoding: mechanisms and ratios range over group effects in the sense of Definition 2.1 →
GeneralMechanismis total on rawGeneralGroupStructuredata whileGeneralIsStrategyproofandsuperlinearRatioexplicitly requireIsGeneralGroupStructure; reason: separating admissibility keeps the printed group-effect conclusion for visible, and raw inadmissible inputs are excluded from every semantic quantifier - encoding: ratio at least and no finite ratio on the class → an inequality and
superlinearRatio M = ⊤in ; reason: top is exactly the absence of a finite upper bound
Preamble
import Mathlib import Definitions.Def_FairFacilityLoc_Supplement_epsilonEffect open scoped NNReal ENNReal
Formal statement
namespace FairFacilityLoc.Supplement
set_option autoImplicit false
/-- **Theorem E.3** (Yan–Zhou, *Fair and Strategyproof Facility Location in Euclidean Space*,
manuscript, sha256 642a1268…, pp.91–92, PDF pp.93–94). For `0 < ε < 1`, the exact effect
`E_ε(s,t) = (min{s,t} + ε max{s,t})/(1+ε)` is monotone, symmetric, superlinear and normalized
by `E_ε(1,1)=1`. Every strategyproof mechanism has ratio at least `1/(4ε)` on the fixed
two-disjoint-two-agent structure using this effect. Consequently its ratio over all superlinear
group effects is infinite, in every positive dimension.
**Formalization Note.** The first conjunct packages “monotone, symmetric” together with the
paper's standing nonzero condition as `IsGroupEffect`. The exact four-agent structure is
`epsilonTwoByTwo ε`. Ratios are in `ℝ≥0∞` with `0/0=1` and `a/0=∞`. No anonymity,
continuity, coordinate independence, or finite-ratio hypothesis is imposed. -/
theorem theorem_E_3 (d : ℕ) (hd : 1 ≤ d) (ε : ℝ≥0) (hε0 : 0 < ε) (hε1 : ε < 1)
(M : GeneralMechanism d) (hsp : GeneralIsStrategyproof M) :
FairFacilityLoc.IsGroupEffect (epsilonEffect ε) ∧
IsSuperlinearEffect (epsilonEffect ε) ∧
epsilonEffect ε 1 = 1 ∧
(((1 / (4 * ε) : ℝ≥0) : ℝ≥0∞) ≤ ratioOn M (epsilonTwoByTwo ε)) ∧
superlinearRatio M = ⊤ := by sorry
end FairFacilityLoc.Supplement
Source
Yan, Zhou, Fair and Strategyproof Facility Location in Euclidean Space, manuscript (sha256 642a1268…), Theorem E.3, pp.91–92 (PDF pp.93–94), equation (E.3)