News

 

Search

• Application Deadline for BMS

  01. Dec 23
  

  The Berlin Mathematical School (BMS) is accepting applications both for phase I students (requiring equivalent of a Bachelors degree) and phase II students (requiring a Masters degree) who wish to pursue their further mathematical career in Berlin.

  More information

  Berlin Mathematical School (BMS) – Get Your Math PhD in Berlin

  The Berlin Mathematical School is the graduate school of the Cluster of Excellence MATH+ and a joint endeavor of the mathematics departments at the universities in Berlin: Freie Universität (FU), Humboldt-Universität (HU) and Technische Universität (TU).
  We offer an excellent doctoral program taught in English in a broad and active research environment together with mentoring programs, language courses, soft-skills seminars, funding for summer schools and conferences, a buddy program and funding for students with children. “Mathematics as a whole“ is a leading principle of the BMS. Its focus encompasses fields that are traditionally termed “pure“ or “applied“ mathematics, though we prefer not to make that distinction. Instead, research topics are grouped into eight parts, each covering a broad, but coherent, part of mathematics:

  1. Differential geometry, global analysis, and mathematical physics
  2. Algebraic and arithmetic geometry, number theory
  3. Stochastics and mathematical finance
  4. Discrete mathematics and optimization
  5. Geometry, topology, and visualization
  6. Numerical analysis and scientific computing
  7. Applied analysis and differential equations
  8. Mathematics of data science

  For applicants with a Bachelor, Phase I offers a basic graduate phase of 3-4 semesters completed by a qualifying exam. Phase II is the research phase and open to candidates with a Master's degree. It lasts 4-6 semesters in which candidates conduct specialized research and attend at least one advanced course per semester. All you need to know about applying to the BMS is available online. You can apply here.

  Application Deadlines

  The first round application deadline of 1 December 2023 is for

  • Phase I applicants requiring admission with scholarship
  • Phase II who want to start before August 2024.

  The second round application deadline of 1 April 2024 is for

  • Phase I applicants requiring admission only
  • Phase II applicants who want to start in August, September or October 2024.

  Contact: application@math-berlin.de

• Paper accepted at Games and Economic Behavior

  29. Sep 23
  The paper Impartial Selection with Additive Guarantees via Iterated Deletion by Javier Cembrano, Felix Fischer, David Hannon, and Max Klimm has been accepted at Games and Economic Behavior.

  Abstract

  Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. For this problem, we give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\kappa)/2})$ in a setting with $n$ individuals where each individual casts $O(n^{\kappa})$ nominations, where $\kappa\in[0,1]$. For $\kappa=0$, ie when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\kappa=1$ the bound is $O(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

• Talk at the TES Summer School on Optimization and Machine Learning

  11. Sep 23
  Maximilian J. Stahlberg gave the talk Convex Optimization in Python at the TES Summer School on Optimization and Machine Learning.

  Abstract

  From classical methods for prediction and classification such as linear regression or support vector machines to auxiliary algorithms for training neural networks: convex optimization plays a key role in machine learning applications. Convex problems can be found in the literature formalized as linear, quadratic, or semidefinite programs, often with a remark that they may be solved using adequate software. In this hands-on session, you will learn to implement and solve such problems in Python using the PICOS library, which allows you to treat their mathematical formulation much like pseudocode. I will first give some background on how software like PICOS transforms a variety of problems to a low level form understood by numeric solvers, and then invite you to solve a constrained least squares model in a Jupyter notebook. In the second part of the session, we will use a convex program to pick from a set of unlabeled data points a small but informative subset to label and add to a training set. This can be useful when training data must be collected from time-consuming and possibly error-prone experiments.

• Paper accepted at WINE 2023

  08. Sep 23
  

  The paper Deterministic Impartial Selection with Weights by Javier Cembrano, Svenja M. Griesbach, and Maximilian J. Stahlberg has been accepted at WINE 2023.

  Abstract

  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$.

• Talk at the ESA 2023

  05. Sep 23
  

  Svenja M. Griesbach gave the talk Improved Approximation Algorithms for the Expanding Search Problem at the ESA 2023.

  Abstract

  A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a $(2e+\varepsilon)$-approximation for any $\varepsilon > 0$. For the case that all vertices have unit weight, we provide a $2e$-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an $8$-approximation was known.

• Talk at the International Conference on Operations Research

  31. Aug 23
  

  Max Klimm gave the talk Information design for congested networks at the International Conference on Operations Research.

  Abstract

  We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times or demands. As this data is subject to stochastic uncertainty resulting from various parameters such as weather condition, occurrences of road works, or traffic accidents. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling. We tightly characterize the class of single-commodity networks, in which full information revelation is always an optimal signaling strategy. Moreover, we construct algorithms computing the optimal signaling scheme whose complexity is polynomial in the number of support vectors that arise in the equilibrium. While this number may be exponential in worst-case instances, it is relatively small in realistic instances. Using a cell decomposition technique, we obtain a polynomial-time algorithm for multi-commodity parallel edge networks with a constant number of commodities, even when we have a constant number of different states of nature.

• Talk at the International Conference on Operations Research

  31. Aug 23
  

  Martin Knaack gave the talk Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint at the International Conference on Operations Research.

  Abstract

  We study the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $c$ of the submodular function. For the extreme cases $c=0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c=1$ it yields a robustness factor of approximately $0.35$ improving over the best previously known robustness factor of approximately $0.06$.

• Talk at the International Conference on Operations Research

  30. Aug 23
  

  Svenja M. Griesbach gave the talk Improved Approximation Algorithms for the Expanding Search Problem at the International Conference on Operations Research.

  Abstract

  A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a $(2e+\varepsilon)$-approximation for every strictly positive value of $\varepsilon$. For the case that all vertices have unit weight, we provide a $2e$-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an $8$-approximation was known.

• Talk at the International Conference on Operations Research

  30. Aug 23
  Maximilian J. Stahlberg gave the talk Complexity of Equilibria in Binary Public Goods Games on Undirected Graphs at the International Conference on Operations Research.

  Abstract

  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.

• Talk at the International Conference on Operations Research

  30. Aug 23
  

  Lea Strubberg gave the talk To couple models for cardiac electrophysiology with transparent interface conditions at the International Conference on Operations Research.

  Abstract

  Mathematical models are useful for studying the effects of medications and diseases on the heart, but achieving both accuracy and computational efficiency is challenging. Highly precise models that can describe cardiac electrophysiology on a cellular level are computationally demanding and not practical for simulating a large amount of myocytes. On the other hand, efficient models may lack accuracy and are not suitable for all applications, such as when modelling cardiac fibrillation or arrhythmia. A spatial coupling of cardiac models can combine the benefits of both by using a precise model for parts of the tissue that require high accuracy, such as scar tissue, and an efficient model for the remaining tissue, thereby reducing computational costs. However, this coupling creates an artificial interface between the models that requires the definition of boundary conditions. The question is how to define these conditions so that the interface becomes as transparent as possible when simulating the tissue as a whole. To address this problem, we will focus on two macroscopic models: the monodomain and the eikonal model. By solving the eikonal model at each time step of the monodomain simulation, we can interlink the information they provide and obtain a transparent coupling scheme.

• Paper accepted at Discrete Mathematics

  18. Aug 23
  

  The paper Book Embeddings of $k$-Framed Graphs and $k$-Map Graphs by Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou has been accepted at Discrete Mathematics.

  Abstract

  An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, namely to $k$-map graphs. In fact, our technique can deal with any nonplanar graph having a biconnected skeleton of crossing-free edges whose faces have bounded degree. We prove that this family of graphs has book thickness bounded in $k$, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal $2$-planar graphs.

• Talk at the Berlin Workshop on Computational Social Choice

  27. Jul 23
  

  Javier Cembrano gave the talk Impartial Selection with Additive Guarantees via Iterated Deletion at the Berlin Workshop on Computational Social Choice.

  Abstract

  Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $\mathcal{O}(n^{(1+\kappa)/2})$ in a setting with $n$ individuals where each individual casts $\mathcal{O}(n^\kappa)$ nominations, where $\kappa \in [0,1]$. For $\kappa =0$, i.e. when each individual casts at most a constant number of nominations, this bound is $\mathcal{O}(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\kappa=1$ the bound is $\mathcal{O}(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

• Talk at the EC 2023

  12. Jul 23
  Maximilian J. Stahlberg gave the talk Complexity of Equilibria in Binary Public Goods Games on Undirected Graphs at the EC 2023.

  Abstract

  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.

• Talk at the ICALP Workshop on Congestion Games

  10. Jul 23
  

  Svenja M. Griesbach gave the talk Information Design for Congestion Games with Unknown Demand at the ICALP Workshop on Congestion Games.

  Abstract

  This paper considers non-atomic congestion games with affine costs and a single commodity whose demand is unknown to the players of the game, but can be observed by a principal. Prior to observing the demand, the principal commits to a public signaling scheme that governs to which extend (if at all) the information about the realized demand is communicated to the players. Upon receiving the signal, the players update their beliefs about the demand and respond by playing a Wardrop equilibrium for the resulting cost functions. We study the question of how to compute the signaling scheme that minimizes the total cost of the induced Wardrop equilibrium. First, we devise a fully polynomial-time approximation scheme (FPTAS) for the case that the demand can only take two values. The FPTAS relies on several structural properties of the cost of the induced Wardrop equilibrium as a function of the updated belief of the distribution of demands. We show that this function is piecewise linear for any number of demands, and monotonic for two demands. Second, we give a complete characterization of the graph structures where it is optimal for the principal to fully reveal the information about the realized demand to the players. Specifically, we show that this signaling scheme is optimal for all cost functions and probability distributions over demands if and only if the graph is series-parallel. Third, we propose an algorithm that computes the optimal signaling scheme for any number of demands whose time complexity is polynomial in the number of supports that occur in a Wardrop equilibrium for some demand. Finally, we conduct a computational study that tests this algorithm on real-world instances.

• Talk at the EC 2023

  10. Jul 23
  

  Javier Cembrano gave the talk Improved Bounds for Single-Nomination Impartial Selection at the EC 2023.

  Abstract

  We give new bounds for the single-nomination model of impartial selection, a problem proposed by Holzman and Moulin (Econometrica, 2013). A selection mechanism, which may be randomized, selects one individual from a group of $n$ based on nominations among members of the group; a mechanism is impartial if the selection of an individual is independent of nominations cast by that individual, and $\alpha$-optimal if under any circumstance the expected number of nominations received by the selected individual is at least $\alpha$ times that received by any individual. In a many-nominations model, where individuals may cast an arbitrary number of nominations, the so-called permutation mechanism is $1/2$-optimal, and this is best possible. In the single-nomination model, where each individual casts exactly one nomination, the permutation mechanism does better and prior to this work was known to be $67/108$-optimal but no better than $2/3$-optimal. We show that it is in fact $2/3$-optimal for all $n$. This result is obtained via tight bounds on the performance of the mechanism for graphs with maximum degree $\Delta$, for any $\Delta$, which we prove using an adversarial argument. We then show that the permutation mechanism is not best possible; indeed, by combining the permutation mechanism, another mechanism called plurality with runner-up, and some new ideas, $2105/3147$-optimality can be achieved for all $n$. We finally give new upper bounds on $\alpha$ for any $\alpha$-optimal impartial mechanism. They improve on the existing upper bounds for all $n \geq 7$ and imply that no impartial mechanism can be better than $76/105$-optimal for all $n$; they do not preclude the existence of a (3/4−\varepsilon)-optimal impartial mechanism for arbitrary $\varepsilon > 0$ if $n$ is large.

• Talk at the AI and Business Analytics Workshop

  07. Jul 23
  

  Max Klimm gave the talk Impartial selection problems at the AI and Business Analytics Workshop .

  Abstract

  Impartial selection problems are concerned with situations where a group of agents selects a subset of the agents based on nominations from within the set. The fact that the agents act both as voters and as nominees may give rise to incentive issues when some agents may not be willing to communicate their true opinion about who should be selected in order to influence their own chances of being selected. These issues may arise in a number of applications such as voting in committees, peer review in conferences where committee members also submit papers, and peer grading. One way to circumvent these incentive issues is to use impartial mechanism that have the property that the selection probability of each agent is independent of its nominations. In this talk, I will give an overview on impartial selection mechanisms and their approximation guarantees. (Based on joint work with Antje Bjelde, Javier Cembrano, David Hannon and Felix Fischer)

• Paper accepted at ESA 2023

  23. Jun 23
  

  The paper Improved Approximation Algorithms for the Expanding Search Problem by Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior has been accepted at ESA 2023.

  Abstract

  A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a $(2e+\varepsilon)$-approximation for any $\varepsilon > 0$. For the case that all vertices have unit weight, we provide a $2e$-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an $8$-approximation was known.

• Talk at the 13th Day on Computational Game Theory

  16. Jun 23
  Maximilian J. Stahlberg gave the talk Complexity of Equilibria in Binary Public Goods Games on Undirected Graphs at the 13th Day on Computational Game Theory.

  Abstract

  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.

• Talk at the Math+ Spotlight Talk Series

  14. Jun 23
  

  Svenja M. Griesbach gave the talk Information Design for Bayesian Networks at the Math+ Spotlight Talk Series .

  AbstractZoom

  This talk considers non-atomic congestion games with affine costs and a single commodity whose demand is unknown to the players of the game, but can be observed by a principal. Prior to observing the demand, the principal commits to a public signaling scheme that governs to which extend (if at all) the information about the realized demand is communicated to the players. Upon receiving the signal, the players update their beliefs about the demand and respond by playing a Wardrop equilibrium for the resulting cost functions. We study the question of how to compute the signaling scheme that minimizes the total cost of the induced Wardrop equilibrium. First, we devise a fully polynomial-time approximation scheme (FPTAS) for the case that the demand can only take two values. The FPTAS relies on several structural properties of the cost of the induced Wardrop equilibrium as a function of the updated belief of the distribution of demands. We show that this function is piecewise linear for any number of demands, and monotonic for two demands. Second, we give a complete characterization of the graph structures where it is optimal for the principal to fully reveal the information about the realized demand to the players. Specifically, we show that this signaling scheme is optimal for all cost functions and probability distributions over demands if and only if the graph is series-parallel. Third, we propose an algorithm that computes the optimal signaling scheme for any number of demands whose time complexity is polynomial in the number of supports that occur in a Wardrop equilibrium for some demand. Finally, we conduct a computational study that tests this algorithm on real-world instances.

• Talk at the Math+ Spotlight Talk Series

  31. May 23
  Maximilian J. Stahlberg gave the talk Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost–Benefit Analysis at the Math+ Spotlight Talk Series.

  Abstract

  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.

• Paper featured in Tagesspiegel

  23. May 23
  The paper Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost–Benefit Analysis has been featured in an article of the newspaper Tagesspiegel.

• Paper accepted at EC 2023

  02. May 23
  

  The paper Improved Bounds for Single-Nomination Impartial Selection by Javier Cembrano, Felix Fischer, and Max Klimm has been accepted at EC 2023.

  Abstract

  We give new bounds for the single-nomination model of impartial selection, a problem proposed by Holzman and Moulin (Econometrica, 2013). A selection mechanism, which may be randomized, selects one individual from a group of $n$ based on nominations among members of the group; a mechanism is impartial if the selection of an individual is independent of nominations cast by that individual, and $\alpha$-optimal if under any circumstance the expected number of nominations received by the selected individual is at least $\alpha$ times that received by any individual. In a many-nominations model, where individuals may cast an arbitrary number of nominations, the so-called permutation mechanism is $1/2$-optimal, and this is best possible. In the single-nomination model, where each individual casts exactly one nomination, the permutation mechanism does better and prior to this work was known to be $67/108$-optimal but no better than $2/3$-optimal. We show that it is in fact $2/3$-optimal for all $n$. This result is obtained via tight bounds on the performance of the mechanism for graphs with maximum degree $\Delta$, for any $\Delta$, which we prove using an adversarial argument. We then show that the permutation mechanism is not best possible; indeed, by combining the permutation mechanism, another mechanism called plurality with runner-up, and some new ideas, $2105/3147$-optimality can be achieved for all $n$. We finally give new upper bounds on $\alpha$ for any $\alpha$-optimal impartial mechanism. They improve on the existing upper bounds for all $n \geq 7$ and imply that no impartial mechanism can be better than $76/105$-optimal for all $n$; they do not preclude the existence of a (3/4−\varepsilon)-optimal impartial mechanism for arbitrary $\varepsilon > 0$ if $n$ is large.

• Talk at the University of Bremen

  27. Apr 23
  

  Svenja M. Griesbach gave the talk Improved Approximation Algorithms for the Expanding Search Problem at the University of Bremen.

  Abstract

  A searcher faces a graph with edge costs and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge cost. The goal is to minimize the vertex-weighted sum of the exploration times of all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the case that all vertices have unit weight, we provide a $2e$-approximation. For the general case, we give a $(5e/2+\epsilon)$-approximation for any $\epsilon > 0$. Previously, for both cases only an $8$-approximation was known. Finally, we provide a PTAS for the case of a Euclidean graph.

• Talk at the Queen Mary University

  26. Apr 23
  

  Javier Cembrano gave the talk Multidimensional political apportionment at the Queen Mary University.

  Abstract

  Deciding how to allocate the seats of a deliberative assembly is one of the most fundamental problems in the political organization of societies, and has been widely studied over already two centuries. The idea of proportionality is at the core of most approaches to tackle this problem, and this notion is captured by the divisor methods, such as the Jefferson/D'Hondt method. In a seminal work, Balinski and Demange extended the single-dimensional idea of divisor methods to the setting in which the seat allocation is simultaneously determined by two dimensions, and proposed the so-called biproportional apportionment method. The method, currently used in several electoral systems, is however limited to two dimensions and the question of extending it is considered to be an important problem both theoretically and in practice. In this work we initiate the study of multidimensional proportional apportionment. We first formalize a notion of multidimensional proportionality that naturally extends that of Balinski and Demange. By means of analyzing an appropriate integer linear program we are able to prove that, in contrast to the two-dimensional case, the existence of multidimensional proportional apportionments is not guaranteed and deciding their existence is NP-complete. Interestingly, our main result asserts that it is possible to find approximate multidimensional proportional apportionments that deviate from the marginals by a small amount. The proof arises through the lens of discrepancy theory, mainly inspired by the celebrated Beck-Fiala Theorem. We finally evaluate our approach by using the data from the recent 2021 Chilean Constitutional Convention election. (Joint work with José Correa and Victor Verdugo)

• Talk at the University of Oxford

  25. Apr 23
  

  Max Klimm gave the talk Improved bounds for single nomination impartial selection at the University of Oxford.

  Abstract

  We give new bounds for the single-nomination model of impartial selection, a problem proposed by Holzman and Moulin (Econometrica, 2013). A selection mechanism, which may be randomized, selects one individual from a group of $n$ based on nominations among members of the group; a mechanism is impartial if the selection of an individual is independent of nominations cast by that individual, and $\alpha$-optimal if under any circumstance the expected number of nominations received by the selected individual is at least $\alpha$ times that received by any individual. In a many-nominations model, where individuals may cast an arbitrary number of nominations, the so-called permutation mechanism is $1/2$-optimal, and this is best possible. In the single-nomination model, where each individual casts exactly one nomination, the permutation mechanism does better and prior to this work was known to be $67/108$-optimal but no better than $2/3$-optimal. We show that it is in fact $2/3$-optimal for all $n$. This result is obtained via tight bounds on the performance of the mechanism for graphs with maximum degree $\Delta$, for any $\Delta$, which we prove using an adversarial argument. We then show that the permutation mechanism is not best possible; indeed, by combining the permutation mechanism, another mechanism called plurality with runner-up, and some new ideas, $2105/3147$-optimality can be achieved for all $n$. We finally give new upper bounds on $\alpha$ for any $\alpha$-optimal impartial mechanism. They improve on the existing upper bounds for all $n\geq 7$ and imply that no impartial mechanism can be better than $76/105$-optimal for all $n$; they do not preclude the existence of a $(3/4-\varepsilon)$-optimal impartial mechanism for arbitrary $\varepsilon>0$ if $n$ is large. (Joint work with Javier Cembrano and Felix Fischer)

• Paper accepted at ICALP 2023

  21. Apr 23
  

  The paper Incremental Maximization via Continuization by Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker has been accepted at ICALP 2023.

  Abstract

  We consider the problem of finding an incremental solution to a cardinality-constrained maximization problem that not only captures the solution for a fixed cardinality, but also describes how to gradually grow the solution as the cardinality bound increases. The goal is to find an incremental solution that guarantees a good competitive ratio against the optimum solution for all cardinalities simultaneously. The central challenge is to characterize maximization problems where this is possible, and to determine the best-possible competitive ratio that can be attained. A lower bound of $2.18$ and an upper bound of $\varphi + 1 \approx 2.618$ are known on the competitive ratio for monotone and accountable objectives [Bernstein et al.,Math. Prog., 2022], which capture a wide range of maximization problems. We introduce a continuization technique and identify an optimal incremental algorithm that provides strong evidence that $\varphi+1$ is the best-possible competitive ratio. Using this continuization, we obtain an improved lower bound of $2.246$ by studying a particular recurrence relation whose characteristic polynomial has complex roots exactly beyond the lower bound. Based on the optimal continuous algorithm combined with a scaling approach, we also provide a $1.772$-competitive randomized algorithm. We complement this by a randomized lower bound of $1.447$ via Yao's principle.

• Lea Strubberg joined the group

  01. Apr 23
  

  Lea Strubberg joined the DISCO group as a PhD student. Welcome, Lea.

• Talk at the Bellairs Workshop on Multi-Agent Systems

  29. Mar 23
  

  Max Klimm gave the talk Impartial Selection with Additive Guarantees via Iterated Deletion at the Bellairs Workshop on Multi-Agent Systems.

  AbstractSlides

  Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $O(n^{1/2})$ in a setting where each agent cast at most a constant number of nomination. This matches the best-known guarantee for randomized mechanisms and a single nomination. When each agent casts up to $n-1$ nominations the same mechanism achieves only the trivial bound of $O(n)$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone. (Joint work with Javier Cembrano and Felix Fischer)

• PostDoc position available

  20. Mar 23
  A joint postdoc position togeter with Combinatorial Optimization and Graph Algorithms group is available at TU Berlin. The position is for two years. The application deadline is March 20, 2023.

  More information

  The successful applicant is expected to perform innovative research in the area of combinatorial optimization and efficient algorithms, and will also contribute to third-party funded research projects. Moreover, he or she will assist in teaching basic as well as advanced math courses, mainly in the area of algorithmic discrete mathematics (both in German and in English).
  Candidates should have an excellent PhD in mathematics, computer science or a closely related area, and must have profound knowledge in Algorithmic Discrete Mathematics and deepened knowledge of Combinatorial Optimization and related areas. Good communication skills and solid command of German and English in speaking and writing are expected. Experience in academic teaching, e.g., as a student assistant, is an advantage.
  Besides its many cultural attractions, Berlin offers a strong scientific landscape including three major universities and the Berlin Mathematics Research Center MATH+ , including the international graduate program Berlin Mathematical School, promoted by the German Excellence Strategy; these offer ample opportunities for joint research and support for Postdocs and PhD students (e.g., meetings, lecture series, international summer schools etc.).
  Instructions on how to apply and more details on the position can be found at job portal of TU Berlin.
  Informal inquiries can be directed to Martin Skutella or Max Klimm. The application deadline is: March 20, 2023

• Talk at the Advanced School on Optimization Methods in Quantum Information

  28. Feb 23
  Maximilian J. Stahlberg gave the talk Practical semidefinite programming with PICOS at the Advanced School on Optimization Methods in Quantum Information.

• Talk at the 3rd GOR Meeting on Game Theory and Behavioral Management Science

  01. Feb 23
  

  Javier Cembrano gave the talk Impartial Selection with Additive Guarantees via Iterated Deletion at the 3rd GOR Meeting on Game Theory and Behavioral Management Science.

  Abstract

  Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\gamma)/2})$ in a setting with $n$ individuals where each individual casts $O(n^\gamma)$ nominations, where $\gamma \in [0,1]$. For $\gamma = 0$, i.e., when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\gamma = 1$, the bound is $O(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

• Talk at the 3rd GOR Meeting on Game Theory and Behavioral Management Science

  31. Jan 23
  

  Svenja M. Griesbach gave the talk Public Signals in Network Congestion Games at the 3rd GOR Meeting on Game Theory and Behavioral Management Science.

  Abstract

  We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times. Travel times are subject to stochastic uncertainty resulting from various parameters such as weather condition, occurrences of road works, or traffic accidents. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate within any non-trivial bounds, even for affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. We tightly characterize the class of single-commodity networks, in which full information revelation is always an optimal signaling strategy. Moreover, we construct a reduction from optimal signaling to computing an optimal collection of support vectors for the Wardrop equilibrium. For two states, this insight can be used to compute an optimal signaling scheme. The algorithm runs in polynomial time whenever the number of different supports resulting from any signal distribution is bounded to a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity parallel link networks with a constant number of commodities, even when we have a constant number of different states of nature.

• Paper accepted at IPCO 2023

  20. Jan 23
  

  The paper The Polyhedral Geometry of Truthful Auctions by Michael Joswig, Max Klimm, and Sylvain Spitz has been accepted at IPCO 2023.

  Abstract

  The difference set of an outcome in an auction is the set of types that the auction mechanism maps to the outcome. We give a complete characterization of the geometry of the difference sets that can appear for a dominant strategy incentive compatible multi-unit auction showing that they correspond to regular subdivisions of the unit cube. This observation is then used to construct mechanisms that are robust in the sense that the set of items allocated to a player does change only slightly when the player's reported type is changed slightly.

• Paper accepted at PNAS Nexus

  20. Dec 22
  

  The paper Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost–Benefit Analysis by Maximilian J. Stahlberg, Guillaume Sagnol, Benjamin Ducke, and Max Klimm has been accepted at PNAS Nexus.

  Abstract

  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.

• Application Deadline for BMS

  01. Dec 22
  

  The Berlin Mathematical School (BMS) is accepting applications both for phase I students (requiring equivalent of a Bachelors degree) and phase II students (requiring a Masters degree) who wish to pursue their further mathematical career in Berlin.

  More information

  Berlin Mathematical School (BMS) – Get Your Math PhD in Berlin

  The Berlin Mathematical School is the graduate school of the Cluster of Excellence MATH+ and a joint endeavor of the mathematics departments at the universities in Berlin: Freie Universität (FU), Humboldt-Universität (HU) and Technische Universität (TU).
  We offer an excellent doctoral program taught in English in a broad and active research environment together with mentoring programs, language courses, soft-skills seminars, funding for summer schools and conferences, a buddy program and funding for students with children.
  “Mathematics as a whole“ is a leading principle of the BMS. Its focus encompasses fields that are traditionally termed “pure“ or “applied“ mathematics, though we prefer not to make that distinction. Instead, research topics are grouped into eight parts, each covering a broad, but coherent, part of mathematics:

  1. Differential geometry, global analysis, and mathematical physics
  2. Algebraic and arithmetic geometry, number theory
  3. Stochastics and mathematical finance
  4. Discrete mathematics and optimization
  5. Geometry, topology, and visualization
  6. Numerical analysis and scientific computing
  7. Applied analysis and differential equations
  8. Mathematics of data science

  For applicants with a Bachelor, Phase I offers a basic graduate phase of 3-4 semesters completed by a qualifying exam. Phase II is the research phase and open to candidates with a Master's degree. It lasts 4-6 semesters in which candidates conduct specialized research and attend at least one advanced course per semester.
  All you need to know about applying to the BMS is available online . You can apply here .

  Application Deadlines

  The first round application deadline of 1 December 2022 is for

  • Phase I applicants requiring admission with scholarship
  • Phase II who want to start before August 2023.

  The second round application deadline of 1 April 2023 is for

  • Phase I applicants requiring admission only
  • Phase II applicants who want to start in August, September or October 2023.

  Contact

• Talk at the Dagstuhl Seminar on Computational Social Dynamics

  07. Nov 22
  

  Max Klimm gave the talk Impartial selection problems at the Dagstuhl Seminar on Computational Social Dynamics.

  AbstractSlides

  Impartial selection problems are concerned with situations where a group of agents selects a subset of the agents based on nominations from within the set. The fact that the agents act both as voters and as nominees may give rise to incentive issues when some agents may not be willing to communicate their true opinion about who should be selected in order to influence their own chances of being selected. These issues may arise in a number of applications such as voting in committees, peer review in conferences where committee members also submit papers, and peer grading. One way to circumvent these incentive issues is to use impartial mechanism that have the property that the selection probability of each agent is independent of its nominations. In this talk, I will give an overview on impartial selection mechanisms and point to some open problems in this area.

• Paper accepted at Mathematics of Operations Research

  29. Oct 22
  The paper Reduction of Potential-Based Flow Networks by Max Klimm, Marc Pfetsch, Rico Raber, and Martin Skutella has been accepted at Mathematics of Operations Research.

  Abstract

  We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties such as voltages or pressures are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks such as electricity, gas, or water networks. In contrast to Kron's reduction for electrical networks, we prove that, in general, potential-based flow networks with at least three terminals cannot be reduced to smaller networks whose size only depends on the number of terminals. On the other hand, we show that it is possible to represent a special class of potential-based flow networks by a complete graph on the terminals, and we establish a characterization of networks that can be reduced to a path network. Our results build on fundamental properties of effective resistances proved in this paper, including explicit formulae for their dependence on edge resistances of the network and their metric properties.

• PostDoc position available

  13. Oct 22
  The research Center MATH+ is looking for a candidate as the new head of the MATH+ Junior Research Group “Optimization under Uncertainty”. The application deadline is November 11, 2022.

  More information

  We are looking for a candidate with extensive experience and independent research results in the field of “Optimization under Uncertainty”, for example, in the field of Robust Optimization, Data-driven Optimization, Online Algorithms, and Algorithmic Game Theory.

  Requirements

  • Dissertation in Mathematics, Computer Science or related disciplines
  • Research experience in “Optimization under Uncertainty”, publications in top-tier journals, and conference proceedings
  • Excellent written and spoken English
  • Applicants should be interested in cooperations with other scientific disciplines as well as with industry and commercial enterprises. Moreover, they should be distinguished by an excellent doctorate and their own research results in this area and should have achieved initial international visibility.

  Please contact the MATH+ Managing Director, Ms. Nadja Wisniewski if you have any questions.
  You can find the official job announcement and information about the application procedure here. The application deadline is 11 November 2022.

• PhD position available

  13. Oct 22
  A PhD position is available in our group in a joint project with the Combinatorial Optimization and Graph Algorithms group. The application deadline is November 18, 2022.

  More information

  A PhD position is available in the Discrete Optimization group at TU Berlin with ties to the Combinatorial Optimization and Graph Algorithms group. The successful applicant will participate in research project A07 in the frame of the DFG-funded Transregio TRR 154. The task of the successful applicant is to study combinatorial optimization problems that arise, for example, in the construction and operation of new hydrogen networks or other gas networks. The opportunity to prepare a PhD thesis will be provided.

  Requirements

  • succesfully completed university degree (Master, Diplom or equivalent) in Mathematics, Computer Science or related fields; clearly above-average grades are desired
  • profound knowledge in Discrete Mathematics, Algorithm Design and Algorithm Analysis are desirable
  • knowledge in the field of Optimization or related areas is desirable
  • good command of German and/or English required; willingness to learn either English or German is expected

  Please send your application with the reference number II-654/22 and the usual documents (letter, CV, relevant certificates and degrees, combined in a single pdf file, max 5 MB) by email to Dorothea Kiefer. The official job posting can be found here.
  The application deadline is: November 18, 2022. Informal inquires about the position can be directed at any time to Max Klimm. Please also send a mail if you would like to apply but have difficulties in meeting the application deadline or are still missing your final exam but expect to obtain it soon.
  Besides its many cultural attractions, Berlin offers a strong scientific landscape including three major universities, the DFG funded mathematics research center MATH+ as well as the international graduate program Berlin Mathematical School; these offer opportunities for joint research and support for PhD students (e.g., meetings, lecture series, international summer schools etc.).

• Paper accepted at SIAM Journal on Applied Algebra and Geometry

  30. Sep 22
  

  The paper Generalized Permutahedra and Optimal Auctions by Michael Joswig, Max Klimm, and Sylvain Spitz has been accepted at SIAM Journal on Applied Algebra and Geometry.

  Abstract

  We study a family of convex polytopes, called SIM-bodies, which were introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-called Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for the Straight-Jacket Auctions among certain deterministic auctions. Third, we employ computer algebra methods and mathematical software to explicitly determine optimal prices and revenues.

• Talk at the APPROX 2022

  21. Sep 22
  

  Martin Knaack gave the talk Maximizing a submodular function with bounded curvature under an unknown knapsack constraint at the APPROX 2022.

  Abstract

  We study the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $c$ of the submodular function. For the extreme cases $c=0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c=1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$.

• Talk at the DMV Annual Meeting 2022

  16. Sep 22
  

  Svenja M. Griesbach gave the talk Public Signals in Network Congestion Games at the DMV Annual Meeting 2022.

  Abstract

  We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times. Travel times are subject to stochastic uncertainty resulting from various parameters such as weather condition, occurrences of road works, or traffic accidents. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate within any non-trivial bounds, even for affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. We tightly characterize the class of single-commodity networks, in which full information revelation is always an optimal signaling strategy. Moreover, we construct a reduction from optimal signaling to computing an optimal collection of support vectors for the Wardrop equilibrium. For two states, this insight can be used to compute an optimal signaling scheme. The algorithm runs in polynomial time whenever the number of different supports resulting from any signal distribution is bounded to a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity parallel link networks with a constant number of commodities, even when we have a constant number of different states of nature. (Joint work with Martin Hoefer, Max Klimm, and Tim Koglin)

• Talk at the DMV Annual Meeting 2022

  14. Sep 22
  

  Sylvain Spitz gave the talk Generalized permutahedra and optimal auctions at the DMV Annual Meeting 2022.

  Abstract

  We study a family of convex polytopes, called SIM-bodies that were introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-calles Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for Straight-Jacket Auctions among certain deterministic auctions. Third, we emply computer algebra methods and mathematical software to explicitly determine optimal prices and revenues.

• Paper accepted at WINE 2022

  07. Sep 22
  

  The paper Optimal Impartial Correspondences by Javier Cembrano, Felix A. Fischer, and Max Klimm has been accepted at WINE 2022.

  Abstract

  We study mechanisms that select a subset of the vertex set of a directed graph in order to maximize the minimum indegree of any selected vertex, subject to an impartiality constraint that the selection of a particular vertex is independent of the outgoing edges of that vertex. For graphs with maximum outdegree $d$, we give a mechanism that selects at most $d+1$ vertices and only selects vertices whose indegree is at least the maximum indegree in the graph minus one. We then show that this is best possible in the sense that no impartial mechanism can only select vertices with maximum degree, even without any restriction on the number of selected vertices. We finally obtain the following trade-off between the maximum number of vertices selected and the minimum indegree of any selected vertex: when selecting at most $k$ of vertices out of $n$, it is possible to only select vertices whose indegree is at least the maximum indegree minus $\lfloor(n-2)/(k-1)\rfloor+1$.

• Talk at the EC 2022

  14. Jul 22
  

  Javier Cembrano gave the talk Impartial selection with additive guarantees via iterated deletion at the EC 2022.

  Abstract

  Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $\mathcal{O}(n^{(1+\kappa)/2})$ in a setting with $n$ individuals where each individual casts $\mathcal{O}(n^\kappa)$ nominations, where $\kappa \in [0,1]$. For $\kappa=0$, i.e. when each individual casts at most a constant number of nominations, this bound is $\mathcal{O}(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\kappa=1$ the bound is $\mathcal{O}(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

• Talk at the EC 2022

  13. Jul 22
  

  Svenja M. Griesbach gave the talk Public Signals in Network Congestion Games at the EC 2022.

  Abstract

  We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times. Travel times are subject to stochastic uncertainty resulting from various parameters such as weather condition, occurrences of road works, or traffic accidents. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate within any non-trivial bounds, even for affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. We tightly characterize the class of single-commodity networks, in which full information revelation is always an optimal signaling strategy. Moreover, we construct a reduction from optimal signaling to computing an optimal collection of support vectors for the Wardrop equilibrium. For two states, this insight can be used to compute an optimal signaling scheme. The algorithm runs in polynomial time whenever the number of different supports resulting from any signal distribution is bounded to a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity parallel link networks with a constant number of commodities, even when we have a constant number of different states of nature.

• Paper accepted at APPROX 2022

  22. Jun 22
  

  The paper Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint by Max Klimm and Martin Knaack has been accepted at APPROX 2022.

  Abstract

  This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $c$ of the submodular function. For the extreme cases $c = 0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c = 1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$.

• Paper accepted at Optimization Methods and Software

  20. Jun 22
  

  The paper Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium by Julia Grübel, Olivier Huber, Lukas Hümbs, Max Klimm, Martin Schmidt, and Alexandra Schwartz has been accepted at Optimization Methods and Software.

  Abstract

  Motivated by examples from the energy sector, we consider market equilibrium problems (MEPs) involving players with nonconvex strategy spaces or objective functions, where the latter are assumed to be linear in market prices. We propose an algorithm that determines if an equilibrium of such an MEP exists and that computes an equilibrium in case of existence. Three key prerequisites have to be met. First, appropriate bounds on market prices have to be derived from necessary optimality conditions of some players. Second, a technical assumption is required for those prices that are not uniquely determined by the derived bounds. Third, nonconvex optimization problems have to be solved to global optimality. We test the algorithm on well-known instances from the power and gas literature that meet these three prerequisites. There, nonconvexities arise from considering the transmission system operator as an additional player besides producers and consumers who, e.g., switches lines or faces nonlinear physical laws. Our numerical results indicate that equilibria often exist, especially for the case of continuous nonconvexities in the context of gas market problems.

• Talk at the 31st European Conference on Operational Research

  13. Jul 21
  Maximilian J. Stahlberg gave the talk Robust conic optimization in Python at the 31st European Conference on Operational Research.

  Abstract

  The Python ecosystem, despite being a leading programming environment for scientific computing and rapid prototyping that offers multiple mathematical optimization frameworks to choose from, has so far provided little support for solving robust and distributionally robust optimization models. To address this, we present an extension of the Python-embedded optimization modeling language PICOS that covers key results from both fields and provides a platform for the implementation of additional models where the robust counterpart of a problem has a conic representation. We start the talk with a brief introduction to the modeling interface provided by PICOS, then we discuss some of its new features concerned with optimization under uncertainty. In particular, we present an illustrative application in linear signal estimation where Wasserstein-robust stochastic programming yields a significantly lower generalization error than L2-regularized least squares regression.