Maximilian J. Stahlberg

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Office: MA 505
Telephone: +49 30 314 25739
Email: (lastname)@math.tu-berlin.de

0000-0002-0190-2693
Bibliography on dblp
GitHub
GitLab

Projects

• Evolution Models for Historical Networks
  Math+ project EF5-6. Project heads: Benjamin Ducke, Max Klimm and Guillaume Sagnol

Publications

to appear

• Complexity of Equilibria in Binary Public Goods Games on Undirected Graphs (Max Klimm and Maximilian J. Stahlberg)
  EC 2023 – Proc. 24th ACM Conference on Economics and Computation.
  PDF arxiv Bibtex Abstract
  @inproceedings{KlimmStahlberg2023,
  arxiv = {2301.11849},
  author = {Max Klimm and Maximilian J. Stahlberg},
  title = {Complexity of Equilibria in Binary Public Goods Games on Undirected Graphs},
  booktitle = {EC 2023 – Proc. 24th ACM Conference on Economics and Computation},
  year = {to appear},
  accepted = {2.5.2023},
  }
  
  We study the complexity of computing equilibria in binary public goods games on undirected graphs. In such a game, players correspond to vertices in a graph and face a binary choice of performing an action, or not. Each player's decision depends only on the number of neighbors in the graph who perform the action and is encoded by a per-player binary pattern. We show that games with decreasing patterns (where players only want to act up to a threshold number of adjacent players doing so) always have a pure Nash equilibrium and that one is reached from any starting profile by following a polynomially bounded sequence of best responses. For non-monotonic patterns of the form $10^k10^*$ (where players want to act alone or alongside $k+1$ neighbors), we show that it is NP-hard to decide whether a pure Nash equilibrium exists. We further investigate a generalization of the model that permits ties of varying strength: an edge with integral weight $w$ behaves as $w$ parallel edges. While, in this model, a pure Nash equilibrium still exists for decreasing patters, we show that the task of computing one is PLS-complete.

2023

• Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost–Benefit Analysis (Maximilian J. Stahlberg, Guillaume Sagnol, Benjamin Ducke and Max Klimm)
  PNAS Nexus, 2(2), 2023.
  DOI Bibtex Abstract
  @article{StahlbergSagnolDucke+2022,
  author = {Maximilian J. Stahlberg and Guillaume Sagnol and Benjamin Ducke and Max Klimm},
  title = {Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost--Benefit Analysis},
  journal = {PNAS Nexus},
  year = {2023},
  volume = {2},
  number = {2},
  accepted = {20.12.2022},
  doi = {10.1093/pnasnexus/pgac313},
  }
  
  The construction of ancient road networks spanned generations and exhibits temporal path dependence that is not fully captured by established network formation models that are used to support archaeological reasoning. We introduce an evolutionary model that captures explicitly the sequential nature of road network formation: A central feature is that connections are added successively and according to an optimal cost–benefit trade-off with respect to existing connections. In this model, the network topology emerges rapidly from early decisions, a trait that makes it possible to identify plausible road construction orders in practice. Based on this observation we develop a method to compress the search space of path-dependent optimization problems. We use this method to show that the model's assumptions on ancient decision making allow the reconstruction of partially known road networks from the Roman era in good detail and from sparse archaeological evidence. In particular, we identify missing links in the major road network of ancient Sardinia that are in good agreement with expert predictions.

2022

• PICOS: A Python interface to conic optimization solvers (Guillaume Sagnol and Maximilian J. Stahlberg)
  Journal of Open Source Software, 7(70):3915, 2022.
  PDF DOI Bibtex Abstract
  @article{SagnolStahlberg2022,
  author = {Guillaume Sagnol and Maximilian J. Stahlberg},
  doi = {10.21105/joss.03915},
  journal = {Journal of Open Source Software},
  number = {70},
  pages = {3915},
  title = {{PICOS}: A {Python} interface to conic optimization solvers},
  volume = {7},
  year = {2022},
  }
  
  Many convex and mixed integer constrained optimization problems can be compiled into a canonical form and handed to some off-the-shelf optimization solver for numeric solution. However, the necessary reformulations can be technically challenging and a program written to use one solver cannot easily be made to use another. PICOS is a well-established Python meta-interface to many proprietary and open source optimization solvers that allows problems to be input in a natural algebraic form and that handles solver selection and the required transformations transparently. This enables users to focus more on the high level optimization model and its application and less on technicalities.

2019

• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths (Cristina Bazgan, Till Fluschnik, André Nichterlein, Rolf Niedermeier and Maximilian J. Stahlberg)
  Networks, 73(1):23–37, 2019.
  PDF DOI arxiv Bibtex Abstract
  @article{BazganFluschnikNichterlein+2019,
  arxiv = {1804.09155},
  author = {Cristina Bazgan and Till Fluschnik and Andr{\'e} Nichterlein and Rolf Niedermeier and Maximilian J. Stahlberg},
  doi = {10.1002/net.21832},
  journal = {Networks},
  number = {1},
  pages = {23--37},
  title = {A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths},
  volume = {73},
  year = {2019},
  }
  
  We study the $\mathsf{NP}$-hard shortest path most vital edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and two designated vertices s and t, the goal is to delete as few edges as possible in order to increase the length of the (new) shortest $st$-path as much as possible. This scenario has been studied from the viewpoint of parameterized complexity and approximation algorithms. We contribute to this line of research by providing refined computational tractability as well as hardness results. We achieve this by a systematic investigation of various problem-specific parameters and their influence on the computational complexity. Charting the border between tractability and intractability, we also identify numerous challenges for future research.

Theses

• Robust conic optimization in Python (Maximilian J. Stahlberg)
  Master's thesis, 2020.
  pdf doi
• Finding the Most Vital Edges for Shortest Paths: Algorithms and Complexity for Special Graph Classes (Maximilian J. Stahlberg)
  Bachelor's thesis, 2016.
  pdf doi

Software

• PICOS (Guillaume Sagnol and Maximilian J. Stahlberg)
  A Python interface to conic optimization solvers.
  docs source