Maximilian J. Stahlberg

Now at: Technische Universität Hamburg

Email: (lastname)@math.tu-berlin.de

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

Publications

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},
  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.
• 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, pp. 938–955.
  PDF DOI 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 = {2023},
  pages = {938--955},
  doi = {10.1145/3580507.3597780},
  }
  
  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.
• Deterministic Impartial Selection with Weights (Javier Cembrano, Svenja M. Griesbach, and Maximilian J. Stahlberg)
  WINE 2023 – Proc. 19th Conference on Web and Internet Economics, Springer Nature Switzerland, pp. 151–168.
  PDF DOI arxiv Bibtex Abstract
  @inproceedings{CembranoGriesbachStahlberg2023,
  author = {Javier Cembrano and Svenja M. Griesbach and Maximilian J. Stahlberg},
  title = {Deterministic Impartial Selection with Weights},
  editor = {Jugal Garg and Max Klimm and Yuqing Kong},
  booktitle = {WINE 2023 – Proc. 19th Conference on Web and Internet Economics},
  series = {LNCS},
  volume = {14413},
  publisher = {Springer Nature Switzerland},
  address = {Cham},
  year = {2023},
  pages = {151--168},
  doi = {10.1007/978-3-031-48974-7\_9},
  arxiv = {2310.14991},
  }
  
  In the impartial selection problem, a subset of agents up to a fixed size $k$ among a group of $n$ is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is $\alpha$-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of $\alpha$ of the votes received by the subset of size $k$ with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly $1/\lceil 2n/k\rceil$. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best known approximation ratio of $1/k$ for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to $k$ agents are to be selected, with a loss in the approximation ratio of $1/2$.

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.

Recent Talks

• Convex Optimization in Python, TES Summer School on Optimization and Machine Learning, 11. Sep 23
• Complexity of Equilibria in Binary Public Goods Games on Undirected Graphs, International Conference on Operations Research, 30. Aug 23
• Complexity of Equilibria in Binary Public Goods Games on Undirected Graphs, EC 2023, 12. Jul 23
• Complexity of Equilibria in Binary Public Goods Games on Undirected Graphs, 13th Day on Computational Game Theory, 16. Jun 23
• Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost–Benefit Analysis, Math+ Spotlight Talk Series, 31. May 23
• Practical semidefinite programming with PICOS, Advanced School on Optimization Methods in Quantum Information, 28. Feb 23
• Robust conic optimization in Python, 31st European Conference on Operational Research, 13. Jul 21

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