2020 [ nach oben ]

• 
  Bilò, Davide; Lenzner, PascalOn the Tree Conjecture for the Network Creation Game. Theory of Computing Systems 2020: 422--443
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. (2003) is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of \($\alpha$\) per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all \($\alpha$\) and that for \($\alpha \geq n$\) all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price \($\alpha$\) and employ it to improve on the best known bound for the latter conjecture. In particular we show that for \($\alpha>4n −13$\) all equilibrium networks must be trees, which implies a constant price of anarchy for this range of \($\alpha$\). Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.
  @article{bilo2020conjecture, abstract = {Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. (2003) is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of $\alpha$ per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all $\alpha$ and that for $\alpha \geq n$ all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price $\alpha$ and employ it to improve on the best known bound for the latter conjecture. In particular we show that for $\alpha>4n −13$ all equilibrium networks must be trees, which implies a constant price of anarchy for this range of $\alpha$. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.}, author = {Bil{ò}, Davide and Lenzner, Pascal}, journal = {Theory of Computing Systems}, keywords = {TOCS pascallenzner year2020}, number = 3, pages = {422--443}, title = {On the Tree Conjecture for the Network Creation Game}, volume = 64, year = 2020 }
• 
  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
  [ BibTeX ] [ Download ]
   
  @inproceedings{bilo2020connection, 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}, title = {Fair Tree Connection Games with Topology-Dependent Edge Cost}, volume = 182, year = 2020 }
• 
  Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, AnnaFlow-Based Network Creation Games. International Joint Conference on Artificial Intelligence (IJCAI) 2020: 139-145
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is~1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.
  @inproceedings{echzell2020flowbased, abstract = {Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is~1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.}, author = {Echzell, Hagen and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, editor = {Bessiere, Christian}, keywords = {annamelnichenko hagenechzell ijcai pascallenzner tobiasfriedrich year2020}, pages = {139-145}, publisher = {ijcai.org}, title = {Flow-Based Network Creation Games}, 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
  [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  @inproceedings{bilo2020topological, 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 }
• 
  Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, AnnaGeometric Network Creation Games. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323-332
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al.~[PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
  @inproceedings{bil2019geometric, abstract = {Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al.~[PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {annamelnichenko davidebilo pascallenzner spaa tobiasfriedrich year2019}, pages = {323-332}, title = {Geometric Network Creation Games}, 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 }
• 
  Bilò, Davide; Lenzner, PascalOn the Tree Conjecture for the Network Creation Game. Symposium on the Theoretical Aspects of Computer Science (STACS) 2018: 14:1-14:15
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. [PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all \($\alpha$\) and that for \($\alpha \geq n$\) all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for \($\alpha > 4n-13$\) all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.
  @inproceedings{bil2018conjecture, abstract = {Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. [PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all $\alpha$ and that for $\alpha \geq n$ all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for $\alpha > 4n-13$ all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.}, author = {Bilò, Davide and Lenzner, Pascal}, booktitle = {Symposium on the Theoretical Aspects of Computer Science (STACS)}, keywords = {pascallenzner stacs year2018}, pages = {14:1-14:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, title = {On the Tree Conjecture for the Network Creation Game}, 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 }
• 
  Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, DavidEfficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Algorithmic Game Theory (SAGT) 2017: 199-211
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.
  @inproceedings{friedrich2017efficient, abstract = {Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.}, author = {Friedrich, Tobias and Ihde, Sven and Keßler, Christoph and Lenzner, Pascal and Neubert, Stefan and Schumann, David}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, keywords = {christophkessler davidschumann pascallenzner sagt stefanneubert svenihde tobiasfriedrich year2017}, pages = {199-211}, title = {Efficient Best Response Computation for Strategic Network Formation under Attack}, year = 2017 }
• 
  Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, DavidBrief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2017: 321-323
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by establishing that the recently introduced model by Goyal et al.[WINE'16], which focuses on robust networks in the presence of a strong adversary, is a rare exception which is both realistic and computationally tractable. In particular, we sketch an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure.
  @inproceedings{friedrich2017brief, abstract = {Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by establishing that the recently introduced model by Goyal et al.[WINE'16], which focuses on robust networks in the presence of a strong adversary, is a rare exception which is both realistic and computationally tractable. In particular, we sketch an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure.}, author = {Friedrich, Tobias and Ihde, Sven and Keßler, Christoph and Lenzner, Pascal and Neubert, Stefan and Schumann, David}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {christophkessler davidschumann pascallenzner spaa stefanneubert svenihde tobiasfriedrich year2017}, pages = {321-323}, title = {Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack}, year = 2017 }

2016 [ nach oben ]

• 
  Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Münn, MartinOn Selfish Creation of Robust Networks. Symposium on Algorithmic Game Theory (SAGT) 2016: 141-152
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.
  @inproceedings{Chauhan2016, abstract = {Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the Internet, are not created and controlled by a central authority. Instead, Internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the Price of Anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.}, address = {Berlin, Heidelberg}, author = {Chauhan, Ankit and Lenzner, Pascal and Melnichenko, Anna and Münn, Martin}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, editor = {Gairing, Martin and Savani, Rahul}, keywords = {ankitchauhan annamelnichenko pascallenzner sagt year2016}, pages = {141-152}, publisher = {Springer Berlin Heidelberg}, title = {On Selfish Creation of Robust Networks}, year = 2016 }

2015 [ nach oben ]

• 
  Cord-Landwehr, Andreas; Lenzner, PascalNetwork Creation Games: Think Global - Act Local. Mathematical Foundations of Computer Science (MFCS) 2015: 248-260
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bilo et al., SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non-constant lower bound on the Price of Anarchy.
  @inproceedings{DBLP:conf/mfcs/Cord-LandwehrL15, abstract = {We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bilo et al., SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non-constant lower bound on the Price of Anarchy.}, author = {Cord-Landwehr, Andreas and Lenzner, Pascal}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {imported mfcs pascal pascallenzner year2015}, pages = {248-260}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Network Creation Games: Think Global - Act Local}, volume = 9235, year = 2015 }

2014 [ nach oben ]

• 
  Lenzner, PascalOn selfish network creation. Doctoral Dissertation, Humboldt University of Berlin 2014
  [ BibTeX ] [ URL ] [ Download ]
   
  @phdthesis{DBLP:phd/dnb/Lenzner14, annote = {Doctoral Dissertation, Humboldt University of Berlin}, author = {Lenzner, Pascal}, keywords = {pascallenzner phdthesis theses year2014}, school = {Humboldt University of Berlin}, title = {On selfish network creation}, type = {PhD Thesis}, year = 2014 }

2013 [ nach oben ]

• 
  Albers, Susanne; Lenzner, PascalOn Approximate Nash Equilibria in Network Design. Internet Mathematics 2013: 384-405
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We study a basic network design game where \(n\) self-interested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost sharing mechanism is Shapley cost sharing that splits the cost of an edge in a fair manner among the agents using the edge. In this paper we investigate if an optimal minimum-cost network represents an attractive, relatively stable state that agents might want to purchase. We resort to the concept of \(\alpha\)-approximate Nash equilibria. We prove that for single source games in undirected graphs, any optimal network represents an \(H(n)\)-approximate Nash equilibrium, where \(H(n)\) is the \(n\)-th Harmonic number. We show that this bound is tight. We extend the results to cooperative games, where agents may form coalitions, and to weighted games. In both cases we give tight or nearly tight lower and upper bounds on the stability of optimal solutions. Finally we show that in general source-sink games and in directed graphs, minimum-cost networks do not represent good states.
  @article{DBLP:journals/im/AlbersL13, abstract = {We study a basic network design game where \(n\) self-interested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost sharing mechanism is Shapley cost sharing that splits the cost of an edge in a fair manner among the agents using the edge. In this paper we investigate if an optimal minimum-cost network represents an attractive, relatively stable state that agents might want to purchase. We resort to the concept of \(\alpha\)-approximate Nash equilibria. We prove that for single source games in undirected graphs, any optimal network represents an \(H(n)\)-approximate Nash equilibrium, where \(H(n)\) is the \(n\)-th Harmonic number. We show that this bound is tight. We extend the results to cooperative games, where agents may form coalitions, and to weighted games. In both cases we give tight or nearly tight lower and upper bounds on the stability of optimal solutions. Finally we show that in general source-sink games and in directed graphs, minimum-cost networks do not represent good states.}, author = {Albers, Susanne and Lenzner, Pascal}, journal = {Internet Mathematics}, keywords = {imported pascal pascallenzner year2013}, number = 4, pages = {384-405}, title = {On Approximate Nash Equilibria in Network Design}, volume = 9, year = 2013 }
• 
  Kawald, Bernd; Lenzner, PascalOn dynamics in selfish network creation. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2013: 83-92
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We consider the dynamic behavior of several variants of the Network Creation Game, introduced by Fabrikant et al. [PODC'03]. Equilibrium networks in these models have desirable properties like low social cost and small diameter, which makes them attractive for the decentralized creation of overlay-networks. Unfortunately, due to the non-constructiveness of the Nash equilibrium, no distributed algorithm for finding such networks is known. We treat these games as sequential-move games and analyze if (uncoordinated) selfish play eventually converges to an equilibrium. Thus, we shed light on one of the most natural algorithms for this problem: distributed local search, where in each step some agent performs a myopic selfish improving move. We show that fast convergence is guaranteed for all versions of Swap Games, introduced by Alon et al. [SPAA'10], if the initial network is a tree. Furthermore, we prove that this process can be sped up to an almost optimal number of moves by employing a very natural move policy. Unfortunately, these positive results are no longer true if the initial network has cycles and we show the surprising result that even one non-tree edge suffices to destroy the convergence guarantee. This answers an open problem from Ehsani et al. [SPAA'11] in the negative. Moreover, we show that on non-tree networks no move policy can enforce convergence. We extend our negative results to the well-studied original version, where agents are allowed to buy and delete edges as well. For this model we prove that there is no convergence guarantee - even if all agents play optimally. Even worse, if played on a non-complete host-graph, then there are instances where no sequence of improving moves leads to a stable network. Furthermore, we analyze whether cost-sharing has positive impact on the convergence behavior. For this we consider a version by Corbo and Parkes [PODC'05] where bilateral consent is needed for the creation of an edge and where edge-costs are shared among the involved agents. We show that employing such a cost-sharing rule yields even worse dynamic behavior..
  @inproceedings{DBLP:conf/spaa/KawaldL13, abstract = {We consider the dynamic behavior of several variants of the Network Creation Game, introduced by Fabrikant et al. [PODC'03]. Equilibrium networks in these models have desirable properties like low social cost and small diameter, which makes them attractive for the decentralized creation of overlay-networks. Unfortunately, due to the non-constructiveness of the Nash equilibrium, no distributed algorithm for finding such networks is known. We treat these games as sequential-move games and analyze if (uncoordinated) selfish play eventually converges to an equilibrium. Thus, we shed light on one of the most natural algorithms for this problem: distributed local search, where in each step some agent performs a myopic selfish improving move. We show that fast convergence is guaranteed for all versions of Swap Games, introduced by Alon et al. [SPAA'10], if the initial network is a tree. Furthermore, we prove that this process can be sped up to an almost optimal number of moves by employing a very natural move policy. Unfortunately, these positive results are no longer true if the initial network has cycles and we show the surprising result that even one non-tree edge suffices to destroy the convergence guarantee. This answers an open problem from Ehsani et al. [SPAA'11] in the negative. Moreover, we show that on non-tree networks no move policy can enforce convergence. We extend our negative results to the well-studied original version, where agents are allowed to buy and delete edges as well. For this model we prove that there is no convergence guarantee - even if all agents play optimally. Even worse, if played on a non-complete host-graph, then there are instances where no sequence of improving moves leads to a stable network. Furthermore, we analyze whether cost-sharing has positive impact on the convergence behavior. For this we consider a version by Corbo and Parkes [PODC'05] where bilateral consent is needed for the creation of an edge and where edge-costs are shared among the involved agents. We show that employing such a cost-sharing rule yields even worse dynamic behavior..}, author = {Kawald, Bernd and Lenzner, Pascal}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {imported pascallenzner spaa year2013}, pages = {83-92}, title = {On dynamics in selfish network creation}, year = 2013 }

2012 [ nach oben ]

• 
  Lenzner, PascalGreedy Selfish Network Creation. Web and Internet Economics (WINE) 2012: 142-155
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We introduce and analyze greedy equilibria (GE) for the well-known model of selfish network creation by Fabrikant et al.[PODC'03]. GE are interesting for two reasons: (1) they model outcomes found by agents which prefer smooth adaptations over radical strategy-changes, (2) GE are outcomes found by agents which do not have enough computational resources to play optimally. In the model of Fabrikant et al. agents correspond to Internet Service Providers which buy network links to improve their quality of network usage. It is known that computing a best response in this model is NP-hard. Hence, poly-time agents are likely not to play optimally. But how good are networks created by such agents? We answer this question for very simple agents. Quite surprisingly, naive greedy play suffices to create remarkably stable networks. Specifically, we show that in the SUM version, where agents attempt to minimize their average distance to all other agents, GE capture Nash equilibria (NE) on trees and that any GE is in 3-approximate NE on general networks. For the latter we also provide a lower bound of 3/2 on the approximation ratio. For the MAX version, where agents attempt to minimize their maximum distance, we show that any GE-star is in 2-approximate NE and any GE-tree having larger diameter is in 6/5-approximate NE. Both bounds are tight. We contrast these positive results by providing a linear lower bound on the approximation ratio for the MAX version on general networks in GE. This result implies a locality gap of \(\Omega(n)\) for the metric min-max facility location problem, where \(n\) is the number of clients.
  @inproceedings{DBLP:conf/wine/Lenzner12, abstract = {We introduce and analyze greedy equilibria (GE) for the well-known model of selfish network creation by Fabrikant et al.[PODC'03]. GE are interesting for two reasons: (1) they model outcomes found by agents which prefer smooth adaptations over radical strategy-changes, (2) GE are outcomes found by agents which do not have enough computational resources to play optimally. In the model of Fabrikant et al. agents correspond to Internet Service Providers which buy network links to improve their quality of network usage. It is known that computing a best response in this model is NP-hard. Hence, poly-time agents are likely not to play optimally. But how good are networks created by such agents? We answer this question for very simple agents. Quite surprisingly, naive greedy play suffices to create remarkably stable networks. Specifically, we show that in the SUM version, where agents attempt to minimize their average distance to all other agents, GE capture Nash equilibria (NE) on trees and that any GE is in 3-approximate NE on general networks. For the latter we also provide a lower bound of 3/2 on the approximation ratio. For the MAX version, where agents attempt to minimize their maximum distance, we show that any GE-star is in 2-approximate NE and any GE-tree having larger diameter is in 6/5-approximate NE. Both bounds are tight. We contrast these positive results by providing a linear lower bound on the approximation ratio for the MAX version on general networks in GE. This result implies a locality gap of \(\Omega(n)\) for the metric min-max facility location problem, where \(n\) is the number of clients.}, author = {Lenzner, Pascal}, booktitle = {Web and Internet Economics (WINE)}, keywords = {imported pascallenzner wine year2012}, pages = {142-155}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Greedy Selfish Network Creation}, volume = 7695, year = 2012 }

2011 [ nach oben ]

• 
  Lenzner, PascalOn Dynamics in Basic Network Creation Games. Symposium on Algorithmic Game Theory (SAGT) 2011: 254-265
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We initiate the study of game dynamics in the Sum Basic Network Creation Game, which was recently introduced by Alon et al.[SPAA'10]. In this game players are associated to vertices in a graph and are allowed to "swap" edges, that is to remove an incident edge and insert a new incident edge. By performing such moves, every player tries to minimize her connection cost, which is the sum of distances to all other vertices. When played on a tree, we prove that this game admits an ordinal potential function, which implies guaranteed convergence to a pure Nash Equilibrium. We show a cubic upper bound on the number of steps needed for any improving response dynamic to converge to a stable tree and propose and analyse a best response dynamic, where the players having the highest cost are allowed to move. For this dynamic we show an almost tight linear upper bound for the convergence speed. Furthermore, we contrast these positive results by showing that, when played on general graphs, this game allows best response cycles. This implies that there cannot exist an ordinal potential function and that fundamentally different techniques are required for analysing this case. For computing a best response we show a similar contrast: On the one hand we give a linear-time algorithm for computing a best response on trees even if players are allowed to swap multiple edges at a time. On the other hand we prove that this task is NP-hard even on simple general graphs, if more than one edge can be swapped at a time. The latter addresses a proposal by Alon et al..
  @inproceedings{DBLP:conf/sagt/Lenzner11, abstract = {We initiate the study of game dynamics in the Sum Basic Network Creation Game, which was recently introduced by Alon et al.[SPAA'10]. In this game players are associated to vertices in a graph and are allowed to "swap" edges, that is to remove an incident edge and insert a new incident edge. By performing such moves, every player tries to minimize her connection cost, which is the sum of distances to all other vertices. When played on a tree, we prove that this game admits an ordinal potential function, which implies guaranteed convergence to a pure Nash Equilibrium. We show a cubic upper bound on the number of steps needed for any improving response dynamic to converge to a stable tree and propose and analyse a best response dynamic, where the players having the highest cost are allowed to move. For this dynamic we show an almost tight linear upper bound for the convergence speed. Furthermore, we contrast these positive results by showing that, when played on general graphs, this game allows best response cycles. This implies that there cannot exist an ordinal potential function and that fundamentally different techniques are required for analysing this case. For computing a best response we show a similar contrast: On the one hand we give a linear-time algorithm for computing a best response on trees even if players are allowed to swap multiple edges at a time. On the other hand we prove that this task is NP-hard even on simple general graphs, if more than one edge can be swapped at a time. The latter addresses a proposal by Alon et al..}, author = {Lenzner, Pascal}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, keywords = {imported pascallenzner sagt year2011}, pages = {254-265}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On Dynamics in Basic Network Creation Games}, volume = 6982, year = 2011 }
• 
  Antoniadis, Antonios; Hüffner, Falk; Lenzner, Pascal; Moldenhauer, Carsten; Souza, AlexanderBalanced Interval Coloring. Symposium on Theoretical Aspects of Computer Science (STACS) 2011: 531-542
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We consider the discrepancy problem of coloring n intervals with \(k\) colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is minimal. Somewhat surprisingly, a coloring with maximal difference at most one always exists. Furthermore, we give an algorithm with running time \(O(n \log n + k n \log k)\) for its construction. This is in particular interesting because many known results for discrepancy problems are non-constructive. This problem naturally models a load balancing scenario, where \(n\) tasks with given start- and endtimes have to be distributed among \(k\) servers. Our results imply that this can be done ideally balanced. When generalizing to \(d\)-dimensional boxes (instead of intervals), a solution with difference at most one is not always possible. We show that for any \(d \ge 2\) and any \(k \ge 2\) it is NP-complete to decide if such a solution exists, which implies also NP-hardness of the respective minimization problem. In an online scenario, where intervals arrive over time and the color has to be decided upon arrival, the maximal difference in the size of color classes can become arbitrarily high for any online algorithm.
  @inproceedings{DBLP:conf/stacs/AntoniadisHLMS11, abstract = {We consider the discrepancy problem of coloring n intervals with \(k\) colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is minimal. Somewhat surprisingly, a coloring with maximal difference at most one always exists. Furthermore, we give an algorithm with running time \(O(n \log n + k n \log k)\) for its construction. This is in particular interesting because many known results for discrepancy problems are non-constructive. This problem naturally models a load balancing scenario, where \(n\) tasks with given start- and endtimes have to be distributed among \(k\) servers. Our results imply that this can be done ideally balanced. When generalizing to \(d\)-dimensional boxes (instead of intervals), a solution with difference at most one is not always possible. We show that for any \(d \ge 2\) and any \(k \ge 2\) it is NP-complete to decide if such a solution exists, which implies also NP-hardness of the respective minimization problem. In an online scenario, where intervals arrive over time and the color has to be decided upon arrival, the maximal difference in the size of color classes can become arbitrarily high for any online algorithm.}, author = {Antoniadis, Antonios and Hüffner, Falk and Lenzner, Pascal and Moldenhauer, Carsten and Souza, Alexander}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, keywords = {imported pascallenzner stacs year2011}, pages = {531-542}, series = {LIPIcs}, title = {Balanced Interval Coloring}, volume = 9, year = 2011 }

2010 [ nach oben ]

• 
  Albers, Susanne; Lenzner, PascalOn Approximate Nash Equilibria in Network Design. Web and Internet Economics (WINE) 2010: 14-25
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We study a basic network design game where \($n$\) self-interested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost sharing mechanism is Shapley cost sharing that splits the cost of an edge in a fair manner among the agents using the edge. In this paper we investigate if an optimal minimum-cost network represents an attractive, relatively stable state that agents might want to purchase. We resort to the concept of \($\alpha$\)-approximate Nash equilibria. We prove that for single source games in undirected graphs, any optimal network represents an \($H(n)$\)-approximate Nash equilibrium, where \($H(n)$\) is the \($n$\)-th Harmonic number. We show that this bound is tight. We extend the results to cooperative games, where agents may form coalitions, and to weighted games. In both cases we give tight or nearly tight lower and upper bounds on the stability of optimal solutions. Finally we show that in general source-sink games and in directed graphs, minimum-cost networks do not represent good states.
  @inproceedings{Albers2010, abstract = {We study a basic network design game where $n$ self-interested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost sharing mechanism is Shapley cost sharing that splits the cost of an edge in a fair manner among the agents using the edge. In this paper we investigate if an optimal minimum-cost network represents an attractive, relatively stable state that agents might want to purchase. We resort to the concept of $\alpha$-approximate Nash equilibria. We prove that for single source games in undirected graphs, any optimal network represents an $H(n)$-approximate Nash equilibrium, where $H(n)$ is the $n$-th Harmonic number. We show that this bound is tight. We extend the results to cooperative games, where agents may form coalitions, and to weighted games. In both cases we give tight or nearly tight lower and upper bounds on the stability of optimal solutions. Finally we show that in general source-sink games and in directed graphs, minimum-cost networks do not represent good states.}, address = {Berlin, Heidelberg}, author = {Albers, Susanne and Lenzner, Pascal}, booktitle = {Web and Internet Economics (WINE)}, editor = {Saberi, Amin}, keywords = {pascallenzner wine year2010}, pages = {14-25}, publisher = {Springer Berlin Heidelberg}, title = {On Approximate Nash Equilibria in Network Design}, type = {Publication}, year = 2010 }