2019 [ to top ]

• 
  Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander From 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, David Convergence and Hardness of Strategic Schelling Segregation. Web and Internet Economics (WINE) 2019
  [ Abstract ] [ BibTeX ] [ 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 \($\mathcal{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 $\mathcal{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 pascallenzner tobiasfriedrich wine year2019}, title = {Convergence and Hardness of Strategic Schelling Segregation}, year = 2019 }

2018 [ to top ]

• 
  Chauhan, Ankit; Lenzner, Pascal; Molitor, Louise Schelling 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 [ to top ]

• 
  Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise Selfish 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 }