Theorem 4.2 — arbitrary demands at block rank two
OpenPoSUndirected.Supplement.theorem_4_2algorithmic-game-theorygraph-theorynetwork-designp2o-gran-per-chapterp2o-plan-bookp2o-v1
Consider any finite loopless undirected network-design game with positive real edge costs, arbitrary labelled demand pairs, all simple terminal-to-terminal paths available, maximum physical block rank , and . There are an optimum profile and a weak equilibrium such that
Moreover, if the whole host is a single theta and some optimum forest profile is unstable, then every global minimum of Rosenthal's harmonic potential satisfies the same strict inequality relative to every optimum profile.
Differences from the source:
- encoding: cycle rank and → on each connected physical block, the subtraction-free inequality ; reason: equivalent for connected blocks and avoids truncated natural subtraction
- encoding: with → existence of an optimum and equilibrium with , plus the positive-optimum hypothesis; reason: the finite game attains both minima and this avoids totalized division
Preamble
import Mathlib import Definitions.Def_PoSUndirected_Supplement_MaxBlockRankLE open CongestionPoA.AsymSum PriceOfStability.Harmonic set_option autoImplicit false
Formal statement
namespace PoSUndirected.Supplement
/-- **Theorem 4.2 (arbitrary demands at block rank two).** Tsoufis, preprint sha256
c095d811…, p.7 (PDF p.9).
For every finite positive-cost loopless undirected network-design game with `b(G) ≤ 2` and
positive optimum, some equilibrium costs strictly less than twice optimum. On a single theta, if
an optimum forest profile is unstable, every global harmonic-potential minimum obeys the same
strict bound.
**Formalization Note.** `MaxBlockRankLE ends 2` is the maximum rank of one physical block, not the
total cycle rank. The second clause is deliberately local to one theta and retains both the
unstable optimum forest profile and the universal quantifier over potential minima. -/
theorem theorem_4_2 {V E ι : Type*} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
[Fintype ι] [DecidableEq ι] (ends : E → Sym2 V) (c : E → ℝ) (s t : ι → V)
(hloop : IsLoopless ends) (hcost : ∀ e, 0 < c e)
(hfeas : ∀ i, (pathStrategies ends (s i) (t i)).Nonempty)
(hrank : MaxBlockRankLE ends 2)
(hopt : ∃ O : ι → Finset E,
IsSocialOptimum (ndGame ends c s t) c O ∧ 0 < socialCost c O) :
(∃ (O N : ι → Finset E),
IsSocialOptimum (ndGame ends c s t) c O ∧
IsPureNash (ndGame ends c s t) N ∧
socialCost c N < 2 * socialCost c O) ∧
(IsSingleTheta ends →
(∃ (F : Finset E) (O : ι → Finset E), IsForestProfile ends s t F O ∧
IsSocialOptimum (ndGame ends c s t) c O ∧
¬ IsPureNash (ndGame ends c s t) O) →
∀ (N O : ι → Finset E),
IsGlobalPotentialMinimum (ndGame ends c s t) N →
IsSocialOptimum (ndGame ends c s t) c O →
socialCost c N < 2 * socialCost c O) := by sorry
end PoSUndirected.Supplement
Source
Tsoufis, The Price of Stability in Undirected Network Design: Lower Bounds and Structural Guarantees (preprint, sha256 c095d811fa04b471d74ba4fdab8fb89ccb3d34079d3bf07384f46ac57144866c), Theorem 4.2, p.7 (PDF p.9)