2020 [ nach oben ]

• 
  Bläsius, Thomas; Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Gries, Alina; Hüffner, Falk; Kißig, Otto; Lenzner, Pascal; Molitor, Louise; Schiller, Leon; Wells, Armin; Witheger, SimonA Strategic Routing Framework and Algorithms for Computing Alternative Paths. Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1--10:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin–destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines.Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.
  @inproceedings{blasius2020strategic, abstract = {Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin–destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines.Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.}, author = {Bläsius, Thomas and Böther, Maximilian and Fischbeck, Philipp and Friedrich, Tobias and Gries, Alina and Hüffner, Falk and Kißig, Otto and Lenzner, Pascal and Molitor, Louise and Schiller, Leon and Wells, Armin and Witheger, Simon}, booktitle = {Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)}, keywords = {sys:relevantfor:ae alinagries arminwells atmos falkhueffner leonschiller louisemolitor maximilianboether ottokissig pascallenzner philippfischbeck simonwietheger thomasblaesius tobiasfriedrich year2020}, pages = {10:1--10:14}, title = {A Strategic Routing Framework and Algorithms for Computing Alternative Paths}, volume = 85, year = 2020 }
• 
  Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna; Molitor, LouiseFair Tree Connection Games with Topology-Dependent Edge Cost. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020: 15:1--15:15
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  How do rational agents self-organize when trying to connect to a common target? We study this question with a simple tree formation game which is related to the well-known fair single-source connection game by Anshelevich et al.(FOCS'04) and selfish spanning tree games by Gourvès and Monnot (WINE'08). In our game agents correspond to nodes in a network that activate a single outgoing edge to connect to the common target node (possibly via other nodes). Agents pay for their path to the common target, and edge costs are shared fairly among all agents using an edge. The main novelty of our model is dynamic edge costs that depend on the in-degree of the respective endpoint. This reflects that connecting to popular nodes that have increased internal coordination costs is more expensive since they can charge higher prices for their routing service. In contrast to related models, we show that equilibria are not guaranteed to exist, but we prove the existence for infinitely many numbers of agents. Moreover, we analyze the structure of equilibrium trees and employ these insights to prove a constant upper bound on the Price of Anarchy as well as non-trivial lower bounds on both the Price of Anarchy and the Price of Stability. We also show that in comparison with the social optimum tree the overall cost of an equilibrium tree is more fairly shared among the agents. Thus, we prove that self-organization of rational agents yields on average only slightly higher cost per agent compared to the centralized optimum, and at the same time, it induces a more fair cost distribution. Moreover, equilibrium trees achieve a beneficial trade-off between a low height and low maximum degree, and hence these trees might be of independent interest from a combinatorics point-of-view. We conclude with a discussion of promising extensions of our model.
  @inproceedings{bilo2020connection, abstract = {How do rational agents self-organize when trying to connect to a common target? We study this question with a simple tree formation game which is related to the well-known fair single-source connection game by Anshelevich et al.(FOCS'04) and selfish spanning tree games by Gourvès and Monnot (WINE'08). In our game agents correspond to nodes in a network that activate a single outgoing edge to connect to the common target node (possibly via other nodes). Agents pay for their path to the common target, and edge costs are shared fairly among all agents using an edge. The main novelty of our model is dynamic edge costs that depend on the in-degree of the respective endpoint. This reflects that connecting to popular nodes that have increased internal coordination costs is more expensive since they can charge higher prices for their routing service. In contrast to related models, we show that equilibria are not guaranteed to exist, but we prove the existence for infinitely many numbers of agents. Moreover, we analyze the structure of equilibrium trees and employ these insights to prove a constant upper bound on the Price of Anarchy as well as non-trivial lower bounds on both the Price of Anarchy and the Price of Stability. We also show that in comparison with the social optimum tree the overall cost of an equilibrium tree is more fairly shared among the agents. Thus, we prove that self-organization of rational agents yields on average only slightly higher cost per agent compared to the centralized optimum, and at the same time, it induces a more fair cost distribution. Moreover, equilibrium trees achieve a beneficial trade-off between a low height and low maximum degree, and hence these trees might be of independent interest from a combinatorics point-of-view. We conclude with a discussion of promising extensions of our model.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna and Molitor, Louise}, booktitle = {Foundations of Software Technology and Theoretical Computer Science (FSTTCS)}, keywords = {annamelnichenko fsttcs louisemolitor pascallenzner tobiasfriedrich year2020}, pages = {15:1--15:15}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{ü}r Informatik}, title = {Fair Tree Connection Games with Topology-Dependent Edge Cost}, volume = 182, year = 2020 }
• 
  Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, LouiseTopological Influence and Locality in Swap Schelling Games. International Symposium on Mathematical Foundations of Computer Science (MFCS) 2020: 15:1--15:15
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Residential segregation is a wide-spread phenomenon that can be observed in almost everymajor city. In these urban areas residents with different racial or socioeconomic backgroundtend to form homogeneous clusters. Schelling’s famous agent-based model for residentialsegregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slightbias towards agents preferring similar neighbors. Very recently, Schelling’s model has beeninvestigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight boundson the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, whichare commonly used in empirical studies. For grids we also show that locality has a severeimpact on the game dynamics.
  @inproceedings{bilo2020topological, abstract = {Residential segregation is a wide-spread phenomenon that can be observed in almost everymajor city. In these urban areas residents with different racial or socioeconomic backgroundtend to form homogeneous clusters. Schelling’s famous agent-based model for residentialsegregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slightbias towards agents preferring similar neighbors. Very recently, Schelling’s model has beeninvestigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight boundson the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, whichare commonly used in empirical studies. For grids we also show that locality has a severeimpact on the game dynamics.}, author = {Bilò, Davide and Bilò, Vittorio and Lenzner, Pascal and Molitor, Louise}, booktitle = {International Symposium on Mathematical Foundations of Computer Science (MFCS)}, editor = {Esparza, Javier and Kr{{á}}l', Daniel}, keywords = {louisemolitor mfcs pascallenzner year2020}, pages = {15:1--15:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{{ü}}r Informatik}, series = {LIPIcs}, title = {Topological Influence and Locality in Swap Schelling Games}, volume = 170, year = 2020 }

2019 [ nach oben ]

• 
  Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, AlexanderFrom Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation. Autonomous Agents and Multiagent Systems (AAMAS) 2019: 1949-1951
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  Competing firms tend to select similar locations for their stores. This phenomenon, called the principle of minimum differentiation, was captured by Hotelling with a landmark model of spatial competition but is still the object of an ongoing scientific debate. Although consistently observed in practice, many more realistic variants of Hotelling's model fail to support minimum differentiation or do not have pure equilibria at all. In particular, it was recently proven for a generalized model which incorporates negative network externalities and which contains Hotelling's model and classical selfish load balancing as special cases, that the unique equilibria do not adhere to minimum differentiation. Furthermore, it was shown that for a significant parameter range pure equilibria do not exist. We derive a sharp contrast to these previous results by investigating Hotelling's model with negative network externalities from an entirely new angle: approximate pure subgame perfect equilibria. This approach allows us to prove analytically and via agent-based simulations that approximate equilibria having good approximation guarantees and that adhere to minimum differentiation exist for the full parameter range of the model. Moreover, we show that the obtained approximate equilibria have high social welfare.
  @inproceedings{feldotto2019hotelling, abstract = {Competing firms tend to select similar locations for their stores. This phenomenon, called the principle of minimum differentiation, was captured by Hotelling with a landmark model of spatial competition but is still the object of an ongoing scientific debate. Although consistently observed in practice, many more realistic variants of Hotelling's model fail to support minimum differentiation or do not have pure equilibria at all. In particular, it was recently proven for a generalized model which incorporates negative network externalities and which contains Hotelling's model and classical selfish load balancing as special cases, that the unique equilibria do not adhere to minimum differentiation. Furthermore, it was shown that for a significant parameter range pure equilibria do not exist. We derive a sharp contrast to these previous results by investigating Hotelling's model with negative network externalities from an entirely new angle: approximate pure subgame perfect equilibria. This approach allows us to prove analytically and via agent-based simulations that approximate equilibria having good approximation guarantees and that adhere to minimum differentiation exist for the full parameter range of the model. Moreover, we show that the obtained approximate equilibria have high social welfare.}, author = {Feldotto, Matthias and Lenzner, Pascal and Molitor, Louise and Skopalik, Alexander}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas alexanderskopalik louisemolitor matthiasfeldotto pascallenzner year2019}, pages = {1949-1951}, title = {From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation}, year = 2019 }
• 
  Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, DavidConvergence and Hardness of Strategic Schelling Segregation. Web and Internet Economics (WINE) 2019: 156-170
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \(\tau\), for some \(0<\tau<1\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \(O(m)\) steps, where \(m\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.
  @inproceedings{echzell2019convergence, abstract = {The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \(\tau\), for some \(0<\tau<1\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \(O(m)\) steps, where \(m\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.}, author = {Echzell, Hagen and Friedrich, Tobias and Lenzner, Pascal and Molitor, Louise and Pappik, Marcus and Schöne, Friedrich and Sommer, Fabian and Stangl, David}, booktitle = {Web and Internet Economics (WINE)}, keywords = {louisemolitor marcuspappik pascallenzner tobiasfriedrich wine year2019}, pages = {156-170}, title = {Convergence and Hardness of Strategic Schelling Segregation}, year = 2019 }

2018 [ nach oben ]

• 
  Chauhan, Ankit; Lenzner, Pascal; Molitor, LouiseSchelling Segregation with Strategic Agents. Symposium on Algorithmic Game Theory (SAGT) 2018
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Schelling’s segregation model is a landmark model in sociology. It shows the counter-intuitive phenomenon that residential segregation between individuals of different groups can emerge even when all involved individuals are tolerant. Although the model is widely studied, no pure game-theoretic version where rational agents strategically choose their location exists. We close this gap by introducing and analyzing generalized game-theoretic models of Schelling segregation, where the agents can also have individual location preferences. For our models we investigate the convergence behavior and the efficiency of their equilibria. In particular, we prove guaranteed convergence to an equilibrium in the version which is closest to Schelling’s original model. Moreover, we provide tight bounds on the Price of Anarchy.
  @inproceedings{chauhan2018schelling, abstract = {Schelling’s segregation model is a landmark model in sociology. It shows the counter-intuitive phenomenon that residential segregation between individuals of different groups can emerge even when all involved individuals are tolerant. Although the model is widely studied, no pure game-theoretic version where rational agents strategically choose their location exists. We close this gap by introducing and analyzing generalized game-theoretic models of Schelling segregation, where the agents can also have individual location preferences. For our models we investigate the convergence behavior and the efficiency of their equilibria. In particular, we prove guaranteed convergence to an equilibrium in the version which is closest to Schelling’s original model. Moreover, we provide tight bounds on the Price of Anarchy.}, author = {Chauhan, Ankit and Lenzner, Pascal and Molitor, Louise}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, keywords = {ankitchauhan louisemolitor pascallenzner sagt year2018}, title = {Schelling Segregation with Strategic Agents}, year = 2018 }

2017 [ nach oben ]

• 
  Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Molitor, LouiseSelfish Network Creation with Non-Uniform Edge Cost. Symposium on Algorithmic Game Theory (SAGT) 2017: 160-172
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has con- stant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.
  @inproceedings{chauhan2017selfish, abstract = {Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games. We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the complexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has con- stant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.}, author = {Chauhan, Ankit and Lenzner, Pascal and Melnichenko, Anna and Molitor, Louise}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, keywords = {ankitchauhan annamelnichenko louisemolitor pascallenzner sagt year2017}, pages = {160-172}, title = {Selfish Network Creation with Non-Uniform Edge Cost}, year = 2017 }