Pascal Lenzner
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Pascal Lenzner has a total of 54 co-authors. Here are the top co-authors by number of shared publications:
- Hans Gawendowicz
Hasso-Plattner-Institut Potsdam Germany
7 shared publications - Tobias Friedrich
Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
6 shared publications - Alexander Skopalik
University of Twente
5 shared publications - Davide Bilò
University of L'Aquila
5 shared publications - Daniel Schmand
University of Bremen, Bremen, Germany
4 shared publications Louise Molitor
University of Potsdam
3 shared publications
Latest Publications
- Open Access
- 9 May 2026
- Published by Springer Nature in Autonomous Agents and Multi-Agent Systems
- Vol. 40 (1)
Temporal network creation games: the impact of non-locality and terminals
Our economy, communication, and even our social life crucially depend on networks. These typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. In particular, Bilò et al. [1] recently introduced a model where a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i.e., incident, edges to ensure temporal reachability towards everyone at low cost. We explore two novel conceptual features: agents can create non-incident edges, called the global setting , and agents might only want to ensure reachability of a subset of nodes, called the terminal model . For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many properties depend on the number of terminals and we show how to translate equilibrium constructions from the non-terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. Finally, all of our results hold for the general case where every edge can have multiple labels.
- 9 May 2026
- Published by Springer Nature in Autonomous Agents and Multi-Agent Systems
- Vol. 40 (1)
Open AccessTemporal network creation games: the impact of non-locality and terminals
Our economy, communication, and even our social life crucially depend on networks. These typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. In particular, Bilò et al. [1] recently introduced a model where a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i.e., incident, edges to ensure temporal reachability towards everyone at low cost. We explore two novel conceptual features: agents can create non-incident edges, called the global setting , and agents might only want to ensure reachability of a subset of nodes, called the terminal model . For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many properties depend on the number of terminals and we show how to translate equilibrium constructions from the non-terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks. Finally, all of our results hold for the general case where every edge can have multiple labels.
- 1 May 2026
- Published by Springer Nature
- p. 358-373
Cooperation in Bilateral Generalized Network Creation
- 1 May 2026
- Published by Springer Nature
- p. 358-373
Cooperation in Bilateral Generalized Network Creation
- Open Access
Greedy Routing Reachability Games
Today's networks consist of many autonomous entities that follow their own objectives, i.e., smart devices or parts of large AI systems, that are interconnected. Given the size and complexity of most communication networks, each entity typically only has a local view and thus must rely on a local routing protocol for sending and forwarding packets. A common solution for this is greedy routing, where packets are locally forwarded to a neighbor in the network that is closer to the packet's destination. In this paper we investigate a game-theoretic model with autonomous agents that aim at forming a network where greedy routing is enabled. The agents are positioned in a metric space and each agent tries to establish as few links as possible, while maintaining that it can reach every other agent via greedy routing. Thus, this model captures how greedy routing networks are formed without any assumption on the distribution of the agents or the specific employed greedy routing protocol. Hence, it distills the essence that makes greedy routing work. We study two variants of the model: with directed edges or with undirected edges. For the former, we show that equilibria exist, have optimal total cost, and that in Euclidean metrics they can be found efficiently. However, even for this simple setting computing optimal strategies is NP-hard. For the much more challenging setting with undirected edges, we show for the realistic setting with agents in 2D Euclidean space that the price of anarchy is between 1.75 and 1.8 and for higher dimensions it is less than 2. Also, we show that best response dynamics may cycle, but that in Euclidean space almost optimal approximate equilibria can be computed in polynomial time. Moreover, for 2D Euclidean space, these approximate equilibria outperform the well-known Delaunay triangulation.
Open AccessGreedy Routing Reachability Games
Today's networks consist of many autonomous entities that follow their own objectives, i.e., smart devices or parts of large AI systems, that are interconnected. Given the size and complexity of most communication networks, each entity typically only has a local view and thus must rely on a local routing protocol for sending and forwarding packets. A common solution for this is greedy routing, where packets are locally forwarded to a neighbor in the network that is closer to the packet's destination. In this paper we investigate a game-theoretic model with autonomous agents that aim at forming a network where greedy routing is enabled. The agents are positioned in a metric space and each agent tries to establish as few links as possible, while maintaining that it can reach every other agent via greedy routing. Thus, this model captures how greedy routing networks are formed without any assumption on the distribution of the agents or the specific employed greedy routing protocol. Hence, it distills the essence that makes greedy routing work. We study two variants of the model: with directed edges or with undirected edges. For the former, we show that equilibria exist, have optimal total cost, and that in Euclidean metrics they can be found efficiently. However, even for this simple setting computing optimal strategies is NP-hard. For the much more challenging setting with undirected edges, we show for the realistic setting with agents in 2D Euclidean space that the price of anarchy is between 1.75 and 1.8 and for higher dimensions it is less than 2. Also, we show that best response dynamics may cycle, but that in Euclidean space almost optimal approximate equilibria can be computed in polynomial time. Moreover, for 2D Euclidean space, these approximate equilibria outperform the well-known Delaunay triangulation.
- Open Access
Optimal Welfare in Noncooperative Network Formation under Attack
Communication networks are essential for our economy and our everyday lives. This makes them lucrative targets for attacks. Today, we see an ongoing battle between criminals that try to disrupt our key communication networks and security professionals that try to mitigate these attacks. However, today's networks, like the Internet or peer-to-peer networks among smart devices, are not controlled by a single authority, but instead consist of many independently administrated entities that are interconnected. Thus, both the decisions of how to interconnect and how to secure against potential attacks are taken in a decentralized way by selfish agents. This strategic setting, with agents that want to interconnect and potential attackers that want to disrupt the network, was captured via an influential game-theoretic model by Goyal, Jabbari, Kearns, Khanna, and Morgenstern (WINE 2016). We revisit this model and show improved tight bounds on the achieved robustness of networks created by selfish agents. As our main result, we show that such networks can resist attacks of a large class of potential attackers, i.e., these networks maintain asymptotically optimal welfare post attack. This improves several bounds and resolves an open problem. Along the way, we show the counter-intuitive result, that attackers that aim at minimizing the social welfare post attack do not actually inflict the greatest possible damage.
Open AccessOptimal Welfare in Noncooperative Network Formation under Attack
Communication networks are essential for our economy and our everyday lives. This makes them lucrative targets for attacks. Today, we see an ongoing battle between criminals that try to disrupt our key communication networks and security professionals that try to mitigate these attacks. However, today's networks, like the Internet or peer-to-peer networks among smart devices, are not controlled by a single authority, but instead consist of many independently administrated entities that are interconnected. Thus, both the decisions of how to interconnect and how to secure against potential attacks are taken in a decentralized way by selfish agents. This strategic setting, with agents that want to interconnect and potential attackers that want to disrupt the network, was captured via an influential game-theoretic model by Goyal, Jabbari, Kearns, Khanna, and Morgenstern (WINE 2016). We revisit this model and show improved tight bounds on the achieved robustness of networks created by selfish agents. As our main result, we show that such networks can resist attacks of a large class of potential attackers, i.e., these networks maintain asymptotically optimal welfare post attack. This improves several bounds and resolves an open problem. Along the way, we show the counter-intuitive result, that attackers that aim at minimizing the social welfare post attack do not actually inflict the greatest possible damage.
- Open Access
Cooperation in Bilateral Generalized Network Creation
Studying the impact of cooperation in strategic settings is one of the cornerstones of algorithmic game theory. Intuitively, allowing more cooperation yields equilibria that are more beneficial for the society of agents. However, for many games it is still an open question how much cooperation is actually needed to ensure socially good equilibria. We contribute to this research endeavor by analyzing the benefits of cooperation in a network formation game that models the creation of communication networks via the interaction of selfish agents. In our game, agents that correspond to nodes of a network can buy incident edges of a given weighted host graph to increase their centrality in the formed network. The cost of an edge is proportional to its length, and both endpoints must agree and pay for an edge to be created. This setting is known for having a high price of anarchy. To uncover the impact of cooperation, we investigate the price of anarchy of our network formation game with respect to multiple solution concepts that allow for varying amounts of cooperation. On the negative side, we show that on host graphs with arbitrary edge weights even the strongest form of cooperation cannot improve the price of anarchy. In contrast to this, as our main result, we show that cooperation has a significant positive impact if the given host graph has metric edge weights. For this, we prove asymptotically tight bounds on the price of anarchy via a novel proof technique that might be of independent interest and can be applied in other models with metric weights.
Open AccessCooperation in Bilateral Generalized Network Creation
Studying the impact of cooperation in strategic settings is one of the cornerstones of algorithmic game theory. Intuitively, allowing more cooperation yields equilibria that are more beneficial for the society of agents. However, for many games it is still an open question how much cooperation is actually needed to ensure socially good equilibria. We contribute to this research endeavor by analyzing the benefits of cooperation in a network formation game that models the creation of communication networks via the interaction of selfish agents. In our game, agents that correspond to nodes of a network can buy incident edges of a given weighted host graph to increase their centrality in the formed network. The cost of an edge is proportional to its length, and both endpoints must agree and pay for an edge to be created. This setting is known for having a high price of anarchy. To uncover the impact of cooperation, we investigate the price of anarchy of our network formation game with respect to multiple solution concepts that allow for varying amounts of cooperation. On the negative side, we show that on host graphs with arbitrary edge weights even the strongest form of cooperation cannot improve the price of anarchy. In contrast to this, as our main result, we show that cooperation has a significant positive impact if the given host graph has metric edge weights. For this, we prove asymptotically tight bounds on the price of anarchy via a novel proof technique that might be of independent interest and can be applied in other models with metric weights.
- 1 September 2025
- Published by Springer Nature
- p. 63-80
Social Welfare in Battery Charging Games
- Open Access
Social Welfare in Battery Charging Games
The recent rise of renewable energy produced by many decentralized sources yields interesting market design challenges for electrical grids. Balancing supply and demand in such networks is both a temporal and spatial challenge due to capacity constraints. The recent surge in the number of household-owned batteries, especially in regions with rooftop solar adoption, offers mitigation potential but often acts misaligned with grid-level objectives. In fact, the decision to charge or discharge a household-owned battery is a strategic choice by each battery owner governed by selfish incentives. This calls for an analysis from a game-theoretic point of view. We initiate this timely research direction by considering a game-theoretic setting where selfish agents strategically charge or discharge their batteries to increase their profit. In particular, we study a Stackelberg-like market model where a third party introduces price incentives, aiming to optimize renewable energy utilization while preserving grid feasibility. For this, we study the existence and the quality of equilibria under various pricing strategies. We find that the existence of equilibria crucially depends on the chosen pricing and that the obtained social welfare varies widely. This calls for more sophisticated market models and pricing mechanisms and opens up a rich field for future research in Algorithmic Game Theory on incentives in renewable energy networks.
Open AccessSocial Welfare in Battery Charging Games
The recent rise of renewable energy produced by many decentralized sources yields interesting market design challenges for electrical grids. Balancing supply and demand in such networks is both a temporal and spatial challenge due to capacity constraints. The recent surge in the number of household-owned batteries, especially in regions with rooftop solar adoption, offers mitigation potential but often acts misaligned with grid-level objectives. In fact, the decision to charge or discharge a household-owned battery is a strategic choice by each battery owner governed by selfish incentives. This calls for an analysis from a game-theoretic point of view. We initiate this timely research direction by considering a game-theoretic setting where selfish agents strategically charge or discharge their batteries to increase their profit. In particular, we study a Stackelberg-like market model where a third party introduces price incentives, aiming to optimize renewable energy utilization while preserving grid feasibility. For this, we study the existence and the quality of equilibria under various pricing strategies. We find that the existence of equilibria crucially depends on the chosen pricing and that the obtained social welfare varies widely. This calls for more sophisticated market models and pricing mechanisms and opens up a rich field for future research in Algorithmic Game Theory on incentives in renewable energy networks.
- 18 May 2025
- Published by Springer Nature
- p. 18-34
Network Creation Games with 2-Neighborhood Maximization
- 18 May 2025
- Published by Springer Nature
- p. 18-34
Network Creation Games with 2-Neighborhood Maximization
- Open Access
Network Creation Games with 2-Neighborhood Maximization
Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost $α$ and the number of agents $n$. Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a $Ω(\log(\frac{n}α))$ lower bound for NE, and a tight linear bound for GE for low $α$.Open AccessNetwork Creation Games with 2-Neighborhood Maximization
Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games, selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This seems natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away. For this natural model, we study the existence, the structure and the quality both of Nash equilibria (NE) and greedy equilibria (GE). We give structural results on the existence of degree-2 paths and cycles, and we provide tight constant bounds on the diameter. In contrast to most previous network creation game research, our bounds on the diameter are independent of edge cost $α$ and the number of agents $n$. Also, bounding the diameter does not imply bounding the price of anarchy, which calls for other methods. Using them, we obtain non-trivial bounds on the price of anarchy, including a $Ω(\log(\frac{n}α))$ lower bound for NE, and a tight linear bound for GE for low $α$. - Open Access
Temporal Network Creation Games: The Impact of Non-Locality and Terminals
We live in a world full of networks where our economy, our communication, and even our social life crucially depends on them. These networks typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. While traditionally static networks with a fixed set of links were considered, a recent stream of works focuses on networks whose behavior may change over time. In particular, Bilò et al. (IJCAI 2023) recently introduced a game-theoretic network formation model that embeds temporal aspects in networks. More precisely, a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i.e., incident, edges to ensure temporal reachability towards everyone at low cost. In this work we set out to explore the impact of two novel conceptual features: agents are no longer restricted to creating incident edges, called the global setting, and agents might only want to ensure that they can reach a subset of the other nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many core properties crucially depend on the number of terminals. We also develop a novel tool that allows translating equilibrium constructions from the non-terminal model to the terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks.
Open AccessTemporal Network Creation Games: The Impact of Non-Locality and Terminals
We live in a world full of networks where our economy, our communication, and even our social life crucially depends on them. These networks typically emerge from the interaction of many entities, which is why researchers study agent-based models of network formation. While traditionally static networks with a fixed set of links were considered, a recent stream of works focuses on networks whose behavior may change over time. In particular, Bilò et al. (IJCAI 2023) recently introduced a game-theoretic network formation model that embeds temporal aspects in networks. More precisely, a network is formed by selfish agents corresponding to nodes in a given host network with edges having labels denoting their availability over time. Each agent strategically selects local, i.e., incident, edges to ensure temporal reachability towards everyone at low cost. In this work we set out to explore the impact of two novel conceptual features: agents are no longer restricted to creating incident edges, called the global setting, and agents might only want to ensure that they can reach a subset of the other nodes, called the terminal model. For both, we study the existence, structure, and quality of equilibrium networks. For the terminal model, we prove that many core properties crucially depend on the number of terminals. We also develop a novel tool that allows translating equilibrium constructions from the non-terminal model to the terminal model. For the global setting, we show the surprising result that equilibria in the global and the local model are incomparable and we establish a high lower bound on the Price of Anarchy of the global setting that matches the upper bound of the local model. This shows the counter-intuitive fact that allowing agents more flexibility in edge creation does not improve the quality of equilibrium networks.