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

Tree Nash Equilibria in the Network Creation Game

lax-899194·created ·GitHub @ab7c839·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    In the network creation game, each player purchases incident undirected edges at price α>0\alpha>0 per edge and pays the sum of its distances to all players. Disconnected pairs have infinite distance. A pure Nash equilibrium admits no unilateral strategy change that reduces the changing player's cost.

    This submission proves Theorem 3 of Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker, On a Network Creation Game (PODC 2003, p. 350): every tree Nash equilibrium has social cost strictly less than five times the social optimum. The optimum ranges over all strategy profiles, and the bound holds for every positive edge price and every number of players at least two.

    The concept package separates strategy profiles, individual cost, Nash equilibrium, social cost, the inefficiency ratio, and the theorem statement. The proof compares the distance savings obtained when both endpoints of a tree path buy a link to its midpoint. The resulting distance bound, together with unique edge ownership at equilibrium and a lower bound on every profile's social cost, gives the strict factor-five inequality.

    Concepts

    Concept map
    6 concepts
    100%
    Proven claimDefinitionThis submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    No other submission in the archive builds on this one, and this one builds on none.

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-899194,
      title = {Tree Nash Equilibria in the Network Creation Game},
      year = {2026},
      howpublished = {Lax Archive, lax-899194},
      url = {https://laxarchive.org/lax-899194/},
      note = {draft},
    }

    References

    1. Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou and Scott Shenker. On a Network Creation Game. In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing 347–351, 2003. doi:10.1145/872035.872088 · people.eecs.berkeley.edu/~kubitron/courses/cs294-4-F03/papers/p347-fabrikant.pdf

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…