2017 [ to top ]

• 
  Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, David Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2017
  [ BibTeX ]
   
  @inproceedings{friedrich2017brief, 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)}, publisher = {ACM}, title = {Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack}, year = 2017 }
• 
  Friedrich, Tobias; Ihde, Sven; Keßler, Christoph; Lenzner, Pascal; Neubert, Stefan; Schumann, David Efficient Best Response Computation for Strategic Network Formation under Attack. Symposium on Algorithmic Game Theory (SAGT) 2017
  [ BibTeX ] [ Download ]
   
  @inproceedings{friedrich2017efficient, 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)}, title = {Efficient Best Response Computation for Strategic Network Formation under Attack}, year = 2017 }
• 
  Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise Selfish Network Creation with Non-Uniform Edge Cost. Symposium on Algorithmic Game Theory (SAGT) 2017
  [ BibTeX ] [ Download ]
   
  @inproceedings{chauhan2017selfish, author = {Chauhan, Ankit and Lenzner, Pascal and Melnichenko, Anna and Molitor, Louise}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, title = {Selfish Network Creation with Non-Uniform Edge Cost}, year = 2017 }

2016 [ to top ]

• 
  Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Münn, Martin On 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}, pages = {141-152}, publisher = {Springer Berlin Heidelberg}, title = {On Selfish Creation of Robust Networks}, year = 2016 }

2015 [ to top ]

• 
  Cord-Landwehr, Andreas; Lenzner, Pascal Network 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)}, pages = {248-260}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Network Creation Games: Think Global - Act Local}, volume = 9235, year = 2015 }

2014 [ to top ]

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

2013 [ to top ]

• 
  Kawald, Bernd; Lenzner, Pascal On 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)}, pages = {83-92}, publisher = {ACM}, title = {On dynamics in selfish network creation}, year = 2013 }
• 
  Albers, Susanne; Lenzner, Pascal On 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}, number = 4, pages = {384-405}, title = {On Approximate Nash Equilibria in Network Design}, volume = 9, year = 2013 }

2012 [ to top ]

• 
  Lenzner, Pascal Greedy Selfish Network Creation. Conference on 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 = {Conference on Web and Internet Economics (WINE)}, pages = {142-155}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Greedy Selfish Network Creation}, volume = 7695, year = 2012 }

2011 [ to top ]

• 
  Antoniadis, Antonios; Hüffner, Falk; Lenzner, Pascal; Moldenhauer, Carsten; Souza, Alexander Balanced 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)}, pages = {531-542}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Balanced Interval Coloring}, volume = 9, year = 2011 }
• 
  Lenzner, Pascal On 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)}, pages = {254-265}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On Dynamics in Basic Network Creation Games}, volume = 6982, year = 2011 }

2010 [ to top ]

• 
  Albers, Susanne; Lenzner, Pascal On Approximate Nash Equilibria in Network Design. Conference on Web and Internet Economics (WINE) 2010: 14-25
  [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  @inproceedings{Albers2010, address = {Berlin, Heidelberg}, author = {Albers, Susanne and Lenzner, Pascal}, booktitle = {Conference on Web and Internet Economics (WINE)}, editor = {Saberi, Amin}, pages = {14-25}, publisher = {Springer Berlin Heidelberg}, title = {On Approximate Nash Equilibria in Network Design}, type = {Publication}, year = 2010 }