Research map / Multi-agent systems and games / Games and equilibria
Strategic Network Creation for Enabling Greedy Routing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces a network creation game where selfish agents in a metric space build directed links while ensuring all-pairs greedy routing is enabled and minimizing stretch, and characterizes equilibria across 1-2, tree, Euclidean and general metrics.
Problem
Selfish agents creating a decentralized communication network must keep it navigable by greedy routing (forwarding to a neighbor closer to the destination) while optimizing their own stretch; the existence of equilibria and computational hardness of best responses in different metric spaces is uncle
Approach
A game-theoretic network creation model where agents embedded in a metric space buy directed edges, with cost combining edge price and greedy-routing stretch (with a large penalty Z if greedy routing fails), so equilibria must enable all-pairs greedy routing.
Key results
- In 1-2 metrics and tree metrics, Nash equilibria always exist; in tree metrics the greedy-routing network G^T is the unique NE and GE.
- In Euclidean metrics, greedy equilibria need not exist (2D counterexample), and best response computation is NP-hard.
- Approximate equilibria exist: O(log n)-approximate NE in 1-2 metrics, 5-approximate NE in Euclidean metrics via Theta-graphs, and (alpha+1)-approximate NE in general metrics.
Surprising findings
- Greedy equilibria can fail to exist in 2D Euclidean metrics, unlike the shortest-path variant of the model where NE exist in some settings.
- In 1-2 metrics, the equilibrium structure is characterized via domination set graphs, and best response dynamics cannot cycle.
Limitations
- Best response computation is NP-hard in most metrics, so equilibria are hard to compute in general.
- Euclidean equilibria may not exist, so only approximate stability is guaranteed.
Experimental setup
Metrics: Nash equilibrium existence approximation factor of equilibria stretch computational complexity
Builds on: Network Creation Games Greedy Equilibrium Moscibroda-Schmid-Wattenhofer stretch model Theta-graph
Closest papers by meaning
- Selfish Creation of Social Networks (AAAI 2021 · similarity 0.88)
- Networked Anti-coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence (AAAI 2023 · similarity 0.86)
- The Complexity of Optimizing Atomic Congestion (AAAI 2024 · similarity 0.85)
- Information Design for Congestion Games with Unknown Demand (AAAI 2024 · similarity 0.84)
- Network Intervention by Polling Strategic Agents (NeurIPS 2026 · similarity 0.84)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.