Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Strategic Network Creation for Enabling Greedy Routing
Authors: Julian Berger, Tobias Friedrich, Pascal Lenzner, Paraskevi Machaira, Janosch Ruff
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we present the first game-theoretic network creation model that incorporates greedy routing, i.e., the strategic agents in our model are embedded in some metric space and strive for creating a network among themselves where all-pairs greedy routing is enabled. Besides this, the agents optimize their connection quality within the created network by aiming for greedy routing paths with low stretch. For our model, we analyze the existence of (approximate)equilibria and the computational hardness in different underlying metric spaces. E.g., we characterize the set of equilibria in 1-2-metrics and tree metrics and show that Nash equilibria always exist. For Euclidean space, the setting which is most relevant in practice, we prove that equilibria are not guaranteed to exist but that the well-known Θ-graph construction yields networks having a low stretch that are gametheoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link. |
| Researcher Affiliation | Academia | Julian Berger 1, Tobias Friedrich 1, Pascal Lenzner2, Paraskevi Machaira 1, Janosch Ruff 1 1Hasso Plattner Institute, University of Potsdam, Potsdam, Germany 2Institute of Computer Science, University of Augsburg, Augsburg, Germany |
| Pseudocode | No | The paper describes theoretical concepts and proofs, but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper provides a link to the full version on arXiv (https://doi.org/10.48550/ar Xiv.2403.15307), which is a preprint server and not a source code repository. No other statements regarding code availability are found. |
| Open Datasets | No | The paper focuses on theoretical models and proofs for network creation games and does not describe or use any specific datasets for empirical evaluation. |
| Dataset Splits | No | The paper does not use any datasets for experiments, therefore, no dataset splits are provided. |
| Hardware Specification | No | The paper focuses on theoretical analysis and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical analysis and does not describe any experiments or implementations that would require specific software dependencies. |
| Experiment Setup | No | The paper focuses on theoretical analysis and does not describe any experiments or their setup details, such as hyperparameters or training configurations. |