MI06: Equilibria of Shortest Paths

This research is carried out in the framework of Matheon supported by Einstein Foundation Berlin

Project Members

Project Head: Michael Joswig
Research Staff: Benjamin Schröter


Internal: Bernd Sturmfels Einstein Visiting Fellow
External: Ngoc TranHausdorff Center for Mathematics, Bonn


ECMath - Einstein Center for Mathematics Berlin

ECMath Matheon


The most basic techniques in network optimization are methods to find shortest paths between pairs of nodes in a directed graph. Classical examples include the algorithms of Dijkstra and Floyd–Warshall. These are among the core tools used, e.g., in devices which help a car driver to navigate a road network. Since efficient algorithms are available the corresponding shortest–path problems can be solved almost instantly, even on cheap hardware, and even for fairly large networks. Yet the situation for the network provider is quite different from the perspective of the network user. One reason is that the provider’s objective does not necessarily agree with the one of the user: While the individual driver might be interested in short travel times, the traffic authorities of a metropolitan city might want to, e.g., minimize the total amount of pollution. More importantly, the traffic authorities seek to achieve a system optimum, whereas the driver cares for an individual objective. Typically, in relevant cases it is next to impossible to even describe a system optimum. To help circumventing this problem, this project will focus on developing mathematical tools to assess the impact of local changes to a network a priori. Our prime application will be toward the computation of shortest paths. However, it is expected that some results can also be transferred to other network optimization problems. The optimization of networks is a central theme in combinatorial optimization. Hence the literature is abundant, and the 600 pages of the first volume of Schrijver’s monograph only form the tip of the iceberg. Modern concepts in this area include online techniques as well as robustness and randomization and dynamic algorithms. There are methods which can deal with partial or even incorrect information, and these can also be useful for analyzing modifications to a network to some extent. Further, in practice simulation plays an important role, possibly even on a microscopic level with agents modeling individual drivers. Here we propose to take a somewhat different view on this subject. We will make use of methods from polyhedral geometry to allow for addressing the relevant combinatorial optimization problems in a parameterized fashion.
Network modifications can be very costly. The authorities can implement, e.g., speed limits or road blocks to modify the network. However, it is often a major challenge to understand the overall impact of such changes prior to their implementation. It is the purpose of this project to provide the mathematical foundations for supporting sound decisions. In addition to their practical usefulness the Kleene stars play a fundamental role in tropical geometry. For instance, they arise as tropical analogs of eigenspaces, and their tropical convex hulls are convex in the ordinary sense, i.e., they are polytropes. It is known that they form the building blocks of tropical convexity. Parametric solutions to the shortest path problem correspond to families of polytropes. Thus, in addition to its applicability outside of mathematics, this work is also beneficial for inner-mathematical applications.


The key goals are:

  • Understanding the fibers of the map that sends a matrix to its Kleene star in polyhedral terms, where only few of the entries in the matrix are indeterminats. Develop an efficient implementation for this situation.
  • Develop a generalization of the previous which still works in a scenario with multiple objectives or non-cooperative agents.