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.
Description
Every tree Nash equilibrium has inefficiency strictly below five.
Proof strategy
For a path of length , let be its integer midpoint. Every vertex lies beyond from at least one endpoint. If both endpoints buy a link to , their combined distance savings are at least . The two Nash inequalities bound this by , giving .
Positive edge price rules out duplicate purchases at equilibrium. A tree therefore has purchases, and its social cost is at most . Every connected profile has social cost at least ; disconnected profiles have infinite cost. Since , 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.