While this submission is a draft, it cannot be used by other submissions.

Proof of `Tree Nash equilibria have inefficiency below five`

groundedproofs/Lax899194Proofs/TreeNashEfficiency.lean · lax-899194

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Every tree Nash equilibrium has inefficiency strictly below five.

Proof strategy

For a path of length DD, let rr be its integer midpoint. Every vertex lies beyond rr from at least one endpoint. If both endpoints buy a link to rr, their combined distance savings are at least n(⌊D/2⌋−1)n(\lfloor D/2\rfloor-1). The two Nash inequalities bound this by 2α2\alpha, giving D≤3+4α/nD\le 3+4\alpha/n.

Positive edge price rules out duplicate purchases at equilibrium. A tree therefore has n−1n-1 purchases, and its social cost is at most 5α(n−1)+3n(n−1)5\alpha(n-1)+3n(n-1). Every connected profile has social cost at least α(n−1)+n(n−1)\alpha(n-1)+n(n-1); disconnected profiles have infinite cost. Since n≥2n\ge2, the former upper bound is strictly less than five times the latter lower bound. The optimum is positive and finite, so division proves the claim.

Attribution

The conclusion is Theorem 3 of Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker, On a Network Creation Game (PODC 2003, p. 350). This proof uses a midpoint argument instead of the paper's centroid argument. Tree paths, distances, and finite edge counting use mathlib.