**Chair for**** Algorithm Engineering**

Hasso Plattner Institute

Office: K-2.17

Tel.: +49 331 5509-418

E-Mail: Pascal.Lenzner(at)hpi.de

## Research Interests

My research interests lie in the intersection of algorithms, game theory and artificial intelligence.

I'm especially interested in:

- Algorithmic Game Theory, in particular the impact of selfish behavior in optimization problems
- Foundations of Artificial Intelligence, in particular strategic behavior in multi-agent systems
- Network Science, in particular modeling and analyzing network creation by selfish agents
- Network Design and algorithmic problems on graphs in general
- Game-theoretic analysis of models from Sociology (e.g. Schelling's segregation model) and Economics (e.g. the Hotelling-Downs model)

## News

- Our paper
**Equilibria in Two-Stage Facility Location with Atomic Clients**(with Simon Krogmann, Alexander Skopalik, Marc Uetz, and Marnix C. Vos) has been accepted at IJCAI. A preprint is available on arXiv. - Our paper
**Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games**(with Andrei Constantinescu, Rebecca Reiffenhäuser, Daniel Schmand and Giovanna Varricchio) has been accepted at ICALP. A preprint is available on arXiv. - Our preprint
**Strategic Network Creation for Enabling Greedy Routing**(with Julian Berger, Tobias Friedrich, Paraskevi Machaira, and Janosch Ruff) is available on arXiv. - Our paper
**Asynchronous Opinion Dynamics in Social Networks**(with Petra Berenbrink, Martin Hoefer, Dominik Kaaser, Malin Rau, and Daniel Schmand) has been accepted at the Distributed Computing journal. You can find the article here. - Our preprint
**Towards Linear Spanners in All Temporal Cliques**(with all members of our recent master's project "Reachability Problems on Temporal Graphs": Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Jonas Schmidt, George Skretas, and Armin Wells) is available on arXiv. - I gave a lecture and an interactive puzzle-solving course for high-school students from all over Germany in the recent Fit-for-BWINF-Camp 2024 at HPI.
- Our paper
**Geometric Network Creation Games**(with Davide Bilò, Tobias Friedrich, and Anna Melnichenko) has been published in the SIAM Journal on Discrete Mathematics. - Our paper
**Improving ranking quality and fairness in Swiss-system chess tournaments**(with Pascal Sauer and Ágnes Cseh) has been accepted at the Journal of Quantitative Analysis in Sports. - I did an interactive puzzle-solving course and gave a lecture both exclusively for female high-school students from all over Germany in the recent Girls@BWInf-Camp at HPI.
- In the last semester I taught Algorithmic Problem Solving (with Timo Kötzing), Theoretical Computer Science Unplugged, and the project seminar Analyzing Swiss-System Tournaments. Moreover, in the last semester and in the current summer semester I am co-supervising the Bachelor Project "Efficient Reachability Computation for Electric Vehicles"
- I participated in the HPI Sommercamp 2023 for high-school students, where I gave a talk about divide-and-conquer algorithms.
- Last July Louise Molitor graduated with a PhD. I supervised her as main daily advisor.
- I co-organized the ADYN Summer School on Algorithm Engineering for Network Problems at HPI Potsdam.
- I co-organized ALGO 2022 at HPI Potsdam.
- In 2022 Anna Melnichenko graduated with a PhD. I supervised her as main daily advisor.

## Short CV

**Education:**

2014: PhD degree (Dr. rer. nat.) in computer science from Humboldt-University Berlin, Germany

2009: Diploma degree in computer science (Dipl.-Inf.) from Friedrich-Schiller-University Jena, Germany

2007 - 2009: Studies in theoretical computer science at ETH Zürich, Switzerland

2003 - 2007: Studies in computer science at Friedrich-Schiller-University Jena, Germany

### Positions:

Starting 10/2020: Associated Member in the Research Unit Algorithms, Dynamics and Information Flow in Networks (ADYN) funded by the German Science Foundation

Starting 08/2020: Principal Investigator for the project Geometric Selfish Network Creation (GEONET) funded by the German Science Foundation

Starting 10/2015: PostDoc in the Algorithm Engineering Group at Hasso-Plattner-Institute Potsdam, Germany

2014 - 2015: PostDoc in the Complexity and the Theoretical Computer Science I groups at Friedrich-Schiller-University Jena, Germany

2014: PostDoc in the Algorithms & Complexity Group at Humboldt-University Berlin, Germany

2009 - 2014: PhD Student in the Algorithms & Complexity Group at Humboldt-University Berlin, Germany

2024 [ nach oben ]

- Berenbrink, Petra; Hoefer, Martin; Kaaser, Dominik; Lenzner, Pascal; Rau, Malin; Schmand, Daniel
**Asynchronous Opinion Dynamics in Social Networks**Distributed Computing 2024[ BibTeX ] - Sauer, Pascal; Cseh, Ágnes; Lenzner, Pascal
**Improving ranking quality and fairness in Swiss-system chess tournaments**Journal of Quantitative Analysis in Sports 2024[ BibTeX ] - Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna
**Geometric Network Creation Games**SIAM Journal on Discrete Mathematics 2024: 277–315 - Constantinescu, Andrei; Lenzner, Pascal; Reiffenhäuser, Rebecca; Schmand, Daniel; Varricchio, Giovanna
**Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games**International Colloquium on Automata, Languages and Programming (ICALP) 2024[ BibTeX ] - Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander; Uetz, Marc; Vos, Marnix C.
**Equilibria in Two-Stage Facility Location with Atomic Clients**International Joint Conference on Artificial Intelligence (IJCAI) 2024

2023 [ nach oben ]

- Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna
**Social Distancing Network Creation**Algorithmica 2023 - Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Seifert, Lars
**Single-Peaked Jump Schelling Games**International Symposium on Algorithmic Game Theory (SAGT) 2023 - Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander
**Strategic Facility Location with Clients that Minimize Total Waiting Time**Conference on Artificial Intelligence (AAAI) 2023: 5714–5721 - Cseh, Ágnes; Führlich, Pascal; Lenzner, Pascal
**The Swiss Gambit**Autonomous Agents and Multi-Agent Systems (AAMAS) 2023 - Bertschinger, Nils; Hoefer, Martin; Krogmann, Simon; Lenzner, Pascal; Schuldenzucker, Steffen; Wilhelmi, Lisa
**Equilibria and Convergence in Fire Sale Games**Autonomous Agents and Multiagent Systems (AAMAS) 2023: 215–223 - Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Seifert, Lars
**Single-Peaked Jump Schelling Games**Autonomous Agents and Multiagent Systems (AAMAS) 2023: 2899–2901 - Khomutovskiy, Ivan; Dunker, Rebekka; Dierking, Jessica; Egbert, Julian; Helms, Christian; Schöllkopf, Finn; Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Isaac, Davis; Krogmann, Simon; Lenzner, Pascal
**Applying Skeletons to Speed Up the Arc-Flags Routing Algorithm**SIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2023: 110–122 - Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Gawendowicz, Hans; Klodt, Nicolas; Lenzner, Pascal; Skretas, George
**Temporal Network Creation Games**International Joint Conference on Artificial Intelligence (IJCAI) 2023: 2511–2519 - Bilò, Davide; Bilò, Vittorio; Döring, Michelle; Lenzner, Pascal; Molitor, Louise; Schmidt, Jonas
**Schelling Games with Continuous Types**International Joint Conference on Artificial Intelligence (IJCAI) 2023: 2520–2527 - Gadea Harder, Jonathan; Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander
**Strategic Resource Selection with Homophilic Agents**International Joint Conference on Artificial Intelligence (IJCAI) 2023: 2701–2709 - Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Zahn, Arthur
**The Impact of Cooperation in Bilateral Network Creation**ACM Symposium on Principles of Distributed Computing (PODC) 2023

2022 [ nach oben ]

- Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise
**Topological Influence and Locality in Swap Schelling Games**Autonomous Agents and Multi-Agent Systems (AGNT) 2022: 47 - Berenbrink, Petra; Hoefer, Martin; Kaaser, Dominik; Lenzner, Pascal; Rau, Malin; Schmand, Daniel
**Asynchronous Opinion Dynamics in Social Networks**Autonomous Agents and Multi-Agent Systems (AAMAS) 2022: 109–117 - Führlich, Pascal; Cseh, Ágnes; Lenzner, Pascal
**Improving Ranking Quality and Fairness in Swiss-System Chess Tournaments**ACM Conference on Economics and Computation (EC) 2022: 1101–1102 - Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna
**Social Distancing Network Creation**International Colloquium on Automata, Languages and Programming (ICALP) 2022: 62:1–62:21 - Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise
**Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games**International Joint Conference on Artificial Intelligence (IJCAI) 2022: 81–87 - Bullinger, Martin; Lenzner, Pascal; Melnichenko, Anna
**Network Creation with Homophilic Agents**International Joint Conference on Artificial Intelligence (IJCAI) 2022: 151–157

2021 [ nach oben ]

- Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Lowski, Stefanie; Melnichenko, Anna
**Selfish Creation of Social Networks**Conference on Artificial Intelligence (AAAI) 2021: 5185–5193 - Krogmann, Simon; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander
**Two-Stage Facility Location Games with Strategic Clients and Facilities**International Joint Conference on Artificial Intelligence (IJCAI) 2021: 292–298 - Friedemann, Wilhelm; Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna; Peters, Jannik; Stephan, Daniel; Vaichenker, Michael
**Efficiency and Stability in Euclidean Network Design**Symposium on Parallelism in Algorithms and Architectures (SPAA) 2021: 232–242

2020 [ nach oben ]

- Bilò, Davide; Lenzner, Pascal
**On the Tree Conjecture for the Network Creation Game**Theory of Computing Systems 2020: 422–443 - 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; Wietheger, Simon
**A Strategic Routing Framework and Algorithms for Computing Alternative Paths**Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1–10:14 - Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise
**Fair Tree Connection Games with Topology-Dependent Edge Cost**Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020: 15:1–15:15 - Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna
**Flow-Based Network Creation Games**International Joint Conference on Artificial Intelligence (IJCAI) 2020: 139–145 - Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise
**Topological Influence and Locality in Swap Schelling Games**International Symposium on Mathematical Foundations of Computer Science (MFCS) 2020: 15:1–15:15

2019 [ nach oben ]

- Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander
**From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation**Autonomous Agents and Multiagent Systems (AAMAS) 2019: 1949–1951 - Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna
**Geometric Network Creation Games**Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323–332 - Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David
**Convergence and Hardness of Strategic Schelling Segregation**Web and Internet Economics (WINE) 2019: 156–170

2018 [ nach oben ]

- Chauhan, Ankit; Lenzner, Pascal; Molitor, Louise
**Schelling Segregation with Strategic Agents**Symposium on Algorithmic Game Theory (SAGT) 2018 - Bilò, Davide; Lenzner, Pascal
**On the Tree Conjecture for the Network Creation Game**Symposium on the Theoretical Aspects of Computer Science (STACS) 2018: 14:1–14:15

2017 [ nach oben ]

- Chauhan, Ankit; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise
**Selfish Network Creation with Non-Uniform Edge Cost**Symposium on Algorithmic Game Theory (SAGT) 2017: 160–172 - 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: 199–211 - 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: 321–323

2016 [ nach oben ]

2015 [ nach oben ]

2014 [ nach oben ]

2013 [ nach oben ]

- Albers, Susanne; Lenzner, Pascal
**On Approximate Nash Equilibria in Network Design**Internet Mathematics 2013: 384–405 - Kawald, Bernd; Lenzner, Pascal
**On dynamics in selfish network creation**Symposium on Parallelism in Algorithms and Architectures (SPAA) 2013: 83–92

2012 [ nach oben ]

2011 [ nach oben ]

- Lenzner, Pascal
**On Dynamics in Basic Network Creation Games**Symposium on Algorithmic Game Theory (SAGT) 2011: 254–265 - 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

2010 [ nach oben ]

## Community Service

Program Committee Memberships: SAGT'16, IJCAI'18, IJCAI'19, AAAI'20, IJCAI'20, AAAI'21, IJCAI'21, SAGT'21, AAAI'22, IJCAI'22, WINE'22, IJCAI'23, SAGT'23, WINE'23, AAMAS'24, IJCAI'24, SAGT'24, GAMENETS'24

Scientific Reviewer for various Algorithmic Game Theory (e.g. SAGT, WINE, EC), Algorithms (e.g. SPAA, STACS, ESA, ICALP, MFCS) and Artificial Intelligence (e.g. IJCAI, AAAI) conferences and journals.

Organizer of the 6th Day on Computational Game Theory in Potsdam, Germany

General Co-Chair of WINE 2021 in Potsdam, Germany

Local Co-Organizer of ALGO 2022 in Potsdam, Germany

Co-Organizer of the ADYN Summer School on Algorithm Engineering for Network Problems in Potsdam, Germany

## Teaching

I'm proud and grateful to have received the 2017 FRITSE teaching award.

**Courses:**

- Bachelor Project "Efficient Reachability Computation for Electric Vehicles", Winter 23/24, Summer 2024, HPI Potsdam
- Algorithmic Problem Solving, Bahelor-Course, Winter 23/24, HPI Potsdam
- Theoretical Computer Science Unplugged, Bachelor-Course, Winter 23/24, HPI Potsdam
- Analyzing Swiss-System Tournaments, Bachelor Project Seminar, Winter 23/24, HPI Potsdam
- (Advanced) Competitive Programming, Bachelor/Master-Course, Summer 2023, HPI Potsdam
- Algorithmic Game Theory, Master-Course, Summer 2023, HPI Potsdam
- Algorithmic Problem Solving, Bachelor-Course, Winter 22/23, HPI Potsdam
- Graph Algorithms, Master-Course, Winter 22/23, HPI Potsdam
- (Advanced) Competitive Programming, Bachelor/Master-Course, Summer 2022, HPI Potsdam
- Bachelor Project "Electric Vehicle Charging Coverage", Winter 21/22, Summer 2022, HPI Potsdam
- Algorithmic Problem Solving, Bachelor-Course, Winter 21/22, HPI Potsdam
- Graph Algorithms, Master-Course, Winter 21/22, HPI Potsdam
- (Advanced) Competitve Programming, Bachelor/Master-Course, Summer 2021, HPI Potsdam
- Algorithmic Game Theory, Master-Course, Winter 20/21, HPI Potsdam
- Algorithmic Problem Solving, Bachelor-Course, Winter 20/21, HPI Potsdam
- Master Project "Selfish Creation of Efficent Geometric Networks", Summer 2020, HPI Potsdam
- Graph Algorithms, Master-Course, Summer 2020, HPI Potsdam
- (Advanced) Competitive Programming, Bachelor/Master-Course, Summer 2020, HPI Potsdam
- Bachelor Project "Computing Strategic Routes", Winter 19/20, Summer 2020, HPI Potsdam
- Algorithmic Problem Solving, Bachelor-Course, Winter 19/20, HPI Potsdam
- (Advanced) Competitive Programming, Bachelor/Master-Course, Summer 2019, HPI Potsdam
- Graph Algorithms, Master-Course, Summer 2019, HPI Potsdam
- Algorithmix, Master-Course, Winter 18/19, HPI Potsdam
- Algorithmic Problem Solving, Bachelor-Course, Winter 18/19, HPI Potsdam
- Seminar on Modern Algorithm Theory, Master-Course, Winter 18/19, HPI Potsdam
- Master Project "Exploring Game-theoretic Schelling Segregation", Winter 18/19, HPI Potsdam
- Introduction to the Mathematics of Algorithms, openHPI MOOC, Summer 2018, HPI Potsdam
- (Advanced) Competitive Programming, Bachelor/Master-Course, Summer 2018, HPI Potsdam
- Graph Algorithms, Master-Course, Summer 2018, HPI Potsdam
- Seminar on Network Science, Master-Course, Summer 2018, HPI Potsdam
- Algorithmix, Master-Course, Winter 17/18, HPI Potsdam
- (Advanced) Algorithmic Problem Solving, Bachelor/Master-Course, Winter 17/18, HPI Potsdam
- Introduction to the Mathematics of Algorithms, openHPI MOOC, Summer 2017, HPI Potsdam
- Seminar on Algorithmic Game Theory, Master-Course, Summer 2017, HPI Potsdam
- (Advanced) Competitive Progamming, Bachelor/Master-Course, Summer 2017, HPI Potsdam
- Graph Algorithms, Master-Course, Summer 2017, HPI Potsdam
- Algorithmix, Master-Course, Winter 16/17, HPI Potsdam
- (Advanced) Algorithmic Problem Solving, Bachelor/Master-Course, Winter 16/17, HPI Potsdam
- Master Project "Strategic Network Formation under Attack", Summer 2016, HPI Potsdam
- (Advanced) Competitive Programming, Bachelor/Master-Course, Summer 2016, HPI Potsdam
- Graph Algorithms, Master-Course, Summer 2016, HPI Potsdam
- Introduction to Algorithms, Bachelor-Course, Winter 2015/16, HPI Potsdam
- Algorithmic Foundations, Bachelor-Course, Summer 2015, FSU Jena
- Discrete Modeling, Bachelor-Course, Winter 2014/15, FSU Jena

### Teaching (as TA)

*Algorithms & Data Structures*, Summer 2014, HU Berlin*Introduction to Theoretical Computer Science*, Winter 2013/14, HU Berlin*Algorithms & Data Structures*, Summer 2013, HU Berlin*Introduction to Theoretical Computer Science*, Winter 2012/13, HU Berlin*Algorithms & Data Structures*, Summer 2012, HU Berlin*Seminar on Algorithmic Game Theory*, Winter 2011/12, HU Berlin*Algorithms & Data Structures*, Summer 2011, HU Berlin*Seminar on Algorithmic Game Theory*, Winter 2010/11, HU Berlin*Seminar: Perlen der theoretischen Informatik*, Summer 2010, HU Berlin*Seminar on Energy Efficient Algorithms*, Summer 2010, HU Berlin*Introduction to Theoretical Computer Science*, Winter 2009/10, HU Berlin*Theoretical Computer Science*, Winter 2008/09, ETH Zürich*Discrete Mathematics & Logic I*, Winter 2006/07, FSU Jena*Discrete Mathematics & Logic II*, Summer 2006, FSU Jena*Discrete Mathematics & Logic I*, Winter 2005/06, FSU Jena