## Network and Mechanism Design for Metropolitan Infrastructure

### Background

Metropolitan infrastructures like public roads, telecommunication networks, the electric grid, and public transport are a key factor for quality of life as well as cultural and economic development. However, their installation and maintenance often requires huge efforts both in terms of financial or personal investments, and in terms of environmental burden. The huge effect of infrastructure design decisions on nature, society, and economy make sound infrastructure planning indispensable.

A main characteristic of infrastructure systems is that they are used by a large number of economically independent entities that strive to optimize their private goals instead of optimizing the overall network usage. This fact is apparent for publicly available services like public roads or transport, but matters also for electricity and gas networks that are operated and used by independent economic actors.

Since the last 50 years, such systems of independent decision makers are analyzed within the theory of noncooperative games. Based on the works of Nash and Wardrop, the central concepts of game theory are Nash equilibria and Wardop equilibria. Roughly speaking, a system is in equilibrium when none of its users can minimize its personal costs of the network usage by altering its usage patterns.

To optimize the design and maintenance of the infrastructure networks above it is imperative to understand the conditions under which equilibria emerge, to assess their quality, and to design mechanisms that lead to good equilibria, e.g., in terms of a provable performance guarantee. These are the main goals of this project.

### Network Design

A classic problem in transportation is the design of a traffic network with a good tradeoff between investment costs for installing road capacity and routing cost of the emerging user equilibrium. To formalize the problem, we are given a graph $G=(V,E)$ for which the latency of each edge $e \in E$ depends on the ratio of the installed capacity $z_e$ and the edge flow $f_e$. The goal is to find an optimal investment in edge capacities $\mathbf{z} =(z_e)_{e∈E}$ that minimizes the sum of routing cost of the induced Wardrop equilibrium and the investment cost, i.e., \begin{align}&\min_{\mathbf{f}, \mathbf{z} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e( f_e / z_e) f_e + l_e z_e \tag{1} \\ &\text{ s.t. $\mathbf{f}$ is a Wardrop flow}. \end{align} where is the cost of installing one unit of capacity on edge $e$. This problem can be reformulated as a bilevel optimization problem where in the upper level the edge capacities are determined and in the lower level the Wardop equilibrium conditions are expressed as a minimization problem \begin{align} &\min_{\mathbf{f}, \mathbf{z} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e(f_e/z_e) f_e + l_e z_e \tag{2} \\ &\text{ s.t.: } \mathbf{f} \in \arg\min\nolimits_{\text{$\mathbf{g}$ is a flow}} \sum_{e \in E} \int_{0}^{g_e} c_e(x) \,\text{d}x.\end{align} In Gairing, Harks and Klimm (2014, 2017), we show that the problem (2) is 𝖠𝖯𝖷-hard, i.e., there is a constant ϵ>0 such that no polynomial algorithm can solve all the above system within a factor of $1+\epsilon$ to optimality on all instances. In contrast, the natural relaxation of the problem without the equilibrium constraints \begin{align}&\min_{\mathbf{f},\mathbf{z}\in \mathbb{R}^m_{\geq 0}} \sum_{e \in E} c_e(f_e/z_e)f_e + l_e z_e \tag{3} \\ &\text{ s.t. $\mathbf{f}$ is a flow}.\end{align} can be solved straightforwardly by computing one shortest path for each commodity. We analyze the performance of two algorithms that are based on the solution of the relaxation (3). The first algorithm was proposed by Marcotte [Math. Program. 1986] for the special case that the function ce are monomials. We generalize this algorithm to arbitrary sets $\mathcal{S}$ of unbounded, non-negative and semi-convex latency functions. We obtain approximation guarantees parametrized by the so-called anarchy value $\mu(\mathcal{S})$. Our approximation guarantee matches the previous bounds by Marcotte for monomials, is equal to 2 for general semi-convex functions and equal to 5/4 for general concave and semi-convex functions. More interestingly, we show that taking the better of the two algorithms above gives a strictly improved performance guarantee which can be parametrized by μ() and another related parameter. For general latency functions, e.g., the improved approximation guarantee is equal to 9/5 and for concave and semi-convex functions it is equal to 49/41≈1.195.

**Figure 1:**Schematic solution to a network design problem.

### Road pricing

While the network design problem above is concerned with the design of a new transportation network from scratch, road pricing is a popular measure to improve the equilibrium behavior of existing road networks that was implemented in cities like Singapore, London and Stockholm. The tolls impact the route choices of the commodities such that in the Wardrop equilibrium with tolls all used paths of a commodity are minimal with respect to the sum of the edges' latencies and tolls. To find tolls that minimize the routing cost of the induced user equilibrium, we are interested in solving \begin{align} &\min_{\mathbf{f}, \mathbf{t} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e(f_e) f_e \tag{4}\\ &\text{ s.t. $\mathbf{f}$ is a Wardrop flow w.r.t. $c_e(f_e) + t_e$}.\end{align} which is equivalent to \begin{align} &\min_{\mathbf{f}, \mathbf{t} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e(f_e) f_e \tag{5}\\ &\text{ s.t. $\mathbf{f} \in \arg\min\nolimits_{\mathbf{g} \text{ is a flow }} \int_{0}^{g_e}c_e(x) \,\text{d}x$}.\end{align} It is well-known that (5) can be solved to optimality by charging tolls on every edge of the graph equal to the marginal costs of that edge. This result, however, has little bite for real-world road toll systems where only a subset of the edges of the network are priced.

### Project-related publications

#### 2017

- Antje Bjelde, Yann Disser, Jan Hackfeld, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Kevin Schewior, Miriam Schlöter, Leen Stougie (2017):

**Tight bounds for online TSP on the line**

In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 994-1005. - Antje Bjelde, Felix Fischer, and Max Klimm (2017):

**Impartial selection and the power of up to two choices**

ACM Transactions on Economics and Computation, to appear. - Antje Bjelde, Max Klimm, and Daniel Schmand (2017):

Brief announcement:**Approximation algorithms for unsplittable resource allocation problems with diseconomies of scale**

In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), to appear. - Martin Gairing, Tobias Harks, and Max Klimm (2017):

**Complexity and approximation of the continuous network design problem**

SIAM Journal on Optimization, to appear.

#### 2016

- Yann Disser, Jan Hackfeld, and Max Klimm (2016):

**Undirected graph exploration with $\Theta(\log \log n)$ pebbles**

In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 25-39. -
Tobias Harks and Max Klimm (2016):

**Congestion games with variable demands**

Mathematics of Operations Research, Vol. 41, pp. 255-277. -
Jasper de Jong, Max Klimm, and Marc Uetz (2016):

**Efficiency of equilibria in uniform matroid congestion games**

In Proceedings of the 8th International Symposium on Algroithmic Game Theory (SAGT), pp. 105-116.

#### 2015

- Antje Bjelde, Felix Fischer, and Max Klimm (2015):

**Impartial selection and the power of up to two choices**

In Proceedings of the 11th Conference on Web and Internet Economics, pp. 146-157. - Tobias Harks, Max Klimm, and Manuel Schneider (2015):

**Bottleneck routing with elastic demands**

In Proceedings of the 11th Conference on Web and Internet Economics (WINE), pp. 384-397. - Tobias Harks and Max Klimm (2015):

**Equilibria in a class of aggregative location games**

Journal of Mathematical Economics, Vol. 61, pp. 211-220. - Yann Disser, Andreas Feldmann, Max Klimm, and Matus Mihalak (2015):

**Improving the***H*-bound on the price of stability in undirected Shapley network design games_{k}

Theoretical Computer Science, Vol 562, pp. 557-564. - Yann Disser, Max Klimm, and Elisabeth Lübbecke (2015):

**Scheduling bidirectional traffic on a path**

In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 406-418. - Felix Fischer and Max Klimm (2015):

**Optimal impartial selection**

SIAM Journal on Computing, Vol. 44, pp. 1263-1285. - Tobias Harks, Ingo Kleinert, Max Klimm, and Rolf H. Möhring (2015):

**Computing network tolls with support constraints**

Networks, Vol. 65, pp. 262-285. - Max Klimm (2015):

**Linear, exponential, but nothing else**

In A. Schulz, M. Kutella S. Stiller, and D. Wagner (editors), Gems of Combinatorial Optimization and Graph Algroithms, pp. 113-123. - Max Klimm and Daniel Schmand (2015):

**Sharing non-anonymous costs of multiple resources optimally**

In Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC), pp. 274-287.

#### 2014

- Christoph Hansknecht, Max Klimm, and Alexander Skopalik (2014):

**Approximate pure Nash equilibria in weighted congestion games**

In Proceedings of the 17th Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 242-257. - Tobias Harks and Max Klimm (2014):

**Multimarket oligopolies with restricted market access**

In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), pp. 182-193. - Martin Gairing, Tobias Harks, and Max Klimm (2014):

**Complexity and approximation of the continuous network design problem**

In Proceedings of the 17th Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 226-241. - Tobias Harks, Max Klimm, and Britta Peis (2014):

**Resource competition on integral polymatroids**

In Proceedings of the 10th Conference on Web and Internet Economics (WINE), pp.189-202. - Max Klimm and Andreas Schütz (2014):

**Congestion games with higher demand dimensions**

In Proceedings of the 10th Conference on Web and Internet Economics (WINE), pp. 453-459.