Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 12 — the optimal randomized two-server ratio on the 1-d-d isosceles triangle is (e2d−1+1/4d)/((e2d−1−1)+1/2d)(e_{2d-1}+1/4d)/((e_{2d-1}-1)+1/2d)(e2d−1​+1/4d)/((e2d−1​−1)+1/2d)

Proved
NonuniformCompetitive.Isosceles.optimal_ratio

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysisk-serverp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms

Let d≥1d\ge 1d≥1 be an integer and let MMM be the isosceles triangle with edge lengths 111, ddd, ddd: a metric space consisting of exactly three points aaa, bbb, ccc with

dist⁡(a,b)=1,dist⁡(a,c)=dist⁡(b,c)=d.\operatorname{dist}(a,b)=1,\qquad \operatorname{dist}(a,c)=\operatorname{dist}(b,c)=d.dist(a,b)=1,dist(a,c)=dist(b,c)=d.

In the two-server problem on MMM, two mobile servers occupy points of MMM; each request names a point, which must be covered by a server after the request is served, and the cost is the total distance the servers move. A randomized on-line algorithm is a probability distribution over deterministic on-line algorithms (each of which decides its configuration from the requests seen so far), and its expected cost on a request sequence σ\sigmaσ is ECA(σ)\mathbf{E}C_A(\sigma)ECA​(σ). Such an algorithm is ρ\rhoρ-competitive against an oblivious adversary from the initial configuration C0C_0C0​ if every algorithm in its support starts in C0C_0C0​ and there is a constant aaa such that, for every finite request sequence σ\sigmaσ,

ECA(σ)≤ρ⋅Copt(σ)+a,\mathbf{E}C_A(\sigma)\le \rho\cdot C_{opt}(\sigma)+a,ECA​(σ)≤ρ⋅Copt​(σ)+a,

where Copt(σ)C_{opt}(\sigma)Copt​(σ) is the least cost of serving σ\sigmaσ from C0C_0C0​ with full knowledge of σ\sigmaσ.

Write e2d−1=(1+12d−1)2d−1=(2d2d−1)2d−1e_{2d-1}=\left(1+\frac{1}{2d-1}\right)^{2d-1}=\left(\frac{2d}{2d-1}\right)^{2d-1}e2d−1​=(1+2d−11​)2d−1=(2d−12d​)2d−1 and

αd=e2d−1+1/4d(e2d−1−1)+1/2d.\alpha_d=\frac{e_{2d-1}+1/4d}{(e_{2d-1}-1)+1/2d}.αd​=(e2d−1​−1)+1/2de2d−1​+1/4d​.

Theorem 12. For every initial configuration C0C_0C0​ of the two servers:

  1. no randomized on-line algorithm is competitive against an oblivious adversary from C0C_0C0​ within a factor less than
e2d−1+1/4d(e2d−1−1)+1/2d;\frac{e_{2d-1}+1/4d}{(e_{2d-1}-1)+1/2d};(e2d−1​−1)+1/2de2d−1​+1/4d​;

that is, if AAA is ρ\rhoρ-competitive from C0C_0C0​ then ρ≥αd\rho\ge\alpha_dρ≥αd​; 2. there is a randomized on-line algorithm that is αd\alpha_dαd​-competitive against an oblivious adversary from C0C_0C0​.

The ratio αd\alpha_dαd​ equals 3/23/23/2 on the equilateral triangle (d=1d=1d=1), increases with ddd, and tends to e/(e−1)e/(e-1)e/(e−1). The deterministic optimal ratio on every such triangle is 222, so randomization strictly helps.

Formalization Note The model is the platform's published KServer_model and KServer_randomized (labelled servers Fin 2 → M, a randomized algorithm as a probability measure over deterministic on-line algorithms whose cost on each sequence is measurable, expected cost as a lower Lebesgue integral in [0,∞][0,\infty][0,∞], the off-line optimum as a real infimum over schedules starting at C0C_0C0​). The triangle is any metric space whose points are exactly a,b,ca,b,ca,b,c at the stated distances; every such space is isometric to the paper's triangle. The claim is stated for every initial configuration C0C_0C0​, including both servers on one point; the paper's argument absorbs the initial partial phase into the additive constant.

Preamble
import Mathlib
import Definitions.Def_KServer_model
import Definitions.Def_KServer_randomized
import Definitions.Def_NonuniformCompetitive_Isosceles_isoscelesRatio
Formal statement
namespace NonuniformCompetitive.Isosceles

/-- Theorem 12 (Karlin–Manasse–McGeoch–Owicki, Competitive Randomized Algorithms for Nonuniform
Problems, Algorithmica 11 (1994), p. 564). Consider the two-server problem on an isosceles
triangle with integer edge lengths `1, d, d` (`1 ≤ d`): a metric space consisting of exactly the
three points `a, b, c` with `dist a b = 1` and `dist a c = dist b c = d`. From every initial
configuration `C₀` of the two servers:
1. no randomized algorithm is competitive against an oblivious adversary within a factor less
   than `(e_{2d-1} + 1/(4d)) / ((e_{2d-1} - 1) + 1/(2d))`, and
2. some randomized algorithm achieves this competitive factor. -/
theorem optimal_ratio {M : Type} [MetricSpace M] (d : ℕ) (hd : 1 ≤ d) (a b c : M)
    (hM : ∀ x : M, x = a ∨ x = b ∨ x = c)
    (hab : dist a b = 1) (hac : dist a c = d) (hbc : dist b c = d)
    (C₀ : KServer.Config 2 M) :
    (∀ (A : KServer.RandomizedAlgorithm 2 M) (ρ : ℝ), A.IsCompetitiveFrom C₀ ρ →
        isoscelesRatio d ≤ ρ) ∧
      ∃ A : KServer.RandomizedAlgorithm 2 M, A.IsCompetitiveFrom C₀ (isoscelesRatio d) := by sorry

end NonuniformCompetitive.Isosceles
Source
Karlin, Manasse, McGeoch, Owicki, Competitive Randomized Algorithms for Nonuniform Problems, Algorithmica 11 (1994), DOI 10.1007/BF01189993, p. 564, Theorem 12 (proof pp. 564–566)
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me