2025 [ nach oben ]

Berger, Julian; Friedrich, Tobias; Lenzner, Pascal; Paraskevi, Voula; Ruff, Janosch Strategic Network Creation for Enabling Greedy RoutingConference on Artificial Intelligence (AAAI) 2025
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination. Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. 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 \(\Theta\)-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.
@article{bflmr-aaai25, abstract = {Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination. Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. 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 \(\Theta\)-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.}, author = {Berger, Julian and Friedrich, Tobias and Lenzner, Pascal and Paraskevi, Voula and Ruff, Janosch}, journal = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai janoschruff julianberger paraskevimachaira pascallenzner tobiasfriedrich year2025}, title = {Strategic Network Creation for Enabling Greedy Routing}, year = 2025 }

2022 [ nach oben ]

Kontogiannis, Spyros; Machaira, Paraskevi-Maria-Malevi; Paraskevopoulos, Andreas; Zaroliagis, Christos REX: A Realistic Time-Dependent Model for Multimodal Public TransportAlgorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2022: 12:1–12:16
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We present the non-FIFO time-dependent graph model with REalistic vehicle eXchange times (REX) for schedule-based multimodal public transport, along with a novel query algorithm called TRIP-based LAbel-correction propagation (TRIPLA) algorithm that efficiently solves the realistic earliest-arrival routing problem. The REX model possesses all strong features of previous time-dependent graph models without suffering from their deficiencies. It handles non-negligible exchanges from one vehicle to another, as well as supports non-FIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with real-world data which demonstrates that TRIPLA significantly outperforms all state-of-the-art query algorithms for multimodal earliest-arrival routing in schedule-based public transport.
@inproceedings{noauthororeditor2022realistic, abstract = {We present the non-FIFO time-dependent graph model with REalistic vehicle eXchange times (REX) for schedule-based multimodal public transport, along with a novel query algorithm called TRIP-based LAbel-correction propagation (TRIPLA) algorithm that efficiently solves the realistic earliest-arrival routing problem. The REX model possesses all strong features of previous time-dependent graph models without suffering from their deficiencies. It handles non-negligible exchanges from one vehicle to another, as well as supports non-FIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with real-world data which demonstrates that TRIPLA significantly outperforms all state-of-the-art query algorithms for multimodal earliest-arrival routing in schedule-based public transport.}, author = {Kontogiannis, Spyros and Machaira, Paraskevi-Maria-Malevi and Paraskevopoulos, Andreas and Zaroliagis, Christos}, booktitle = {Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)}, keywords = {sys:relevantfor:ae atmos paraskevimachaira year2022}, pages = {12:1–12:16}, title = {REX: A Realistic Time-Dependent Model for Multimodal Public Transport}, year = 2022 }