Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼

Humboldt-Universität zu Berlin -

Metropolitan Infrastructure

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.

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.

This motivates us in Harks, Kleinert, Klimm, and Möhring (2015) to study the problem of computing tolls on a given subset of network edges so at to minimize the routing costs of the induced Wardrop equilibrium, i.e., given a subset $T \subset E$ of tollable edges, 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{6}\\ &\text{ s.t. $\mathbf{f}$ is a Wardrop equilibrium w.r.t. $c_e(f_e) + t_e$}\\ &t_e = 0 \text{ for all $e \notin T$}\end{align} As this problem is NP-hard for general networks, we restrict ourselves to parallel edge networks. We first devise a pseaudo-polynomial algorithm for this case and  extend it to a polynomial algorithm given that a certain technical condition on the cost functions is met. We then conduct a computational study for this problem on real-world traffic networks for which we tested several algorithms based on gradient descend methods. It turns out that already a small number of tollable edges suffices to decrease the travel time significantly. Further theoretical and empirical results for the problem to choose the set of tollable edges subject to cardinality constraints are given.

Non-monetary access control
Monetary incentives are not always possible to control the access to congested resources due to ethical issues. As an example, consider access to positions, funds, or publication venues. In these situations, a popular way to control the access to the resource is a process of peer review, where the users nominate who they think is eligible for access. It is natural to assume that the main interest of each user is to be granted access, so a selection mechanism must take into account that users may misreport their opinion about who they think is eligible for access as long as they can increase their own chances of being granted access. It is a natural question what percentage of the nominations a mechanism must lose in order to be strategyproof , i.e., in order to prevent misreporting of that kind.

Formally, a nomination profile is a directed graph $G=(N,E)$ where an edge $(u,v) \in E$ is interpreted as $u$ nominating $v$. A selection mechanism $f$ is a function that takes a graph $G=(N,E)$ as input an returns a probability distribution on $N$. Impartiality requires that \begin{align} f(N,E)_i &= f(N,E')_ i & &\Leftarrow & E \setminus (\{i\} \times N) =  E' \setminus ({i}×N), \end{align} i.e., that the probability of selecting $i$ is independent of the nomination that $i$ casts on other agents.

We are interested in impartial mechanism that extract a high percentage of the nominations, but are impartial. To this end, we call a mechanism $f$ that selects at most $k$ users $\alpha$-optimal, if \begin{align} \frac{\mathbb{E}_{S \sim f(G)} [ \sum_{i \in S} \text{deg}(i)]}{\max_{S \subseteq N :|S|=k} \bigl\{ \sum_{i \in S} \text{deg}(i) \bigr\}} \geq \alpha \end{align} for all graphs $G$, where $\text{deg}(i)$ denotes the indegree of vertex $i$.

Even in the most basic where $k=1$, i.e., only a single user is to be selected was considered to be very challenging. It was conjectured by Alon et al. that there is a mechanism that selects in expectation a user that receives half the maximum number of nominations any user receives. In Fischer and Klimm (2015), we answered this conjecture to the positive. We were also able to show that when the most popular user receives many nominations, even a fraction of 3/4 of the maximum number of nominations to a user can be extracted by a mechanism. In Bjelde, Fischer, and Klimm (2015, 2017), we also considered the case where more than one agents is to be selected. In turns out that the achievable approximation guarantee depends on whether the mechanism may select a different number of agents for different input. For the problem of always selecting exactly two agents, e.g., we give a 2/3-optimal mechanism. In contrast, a mechanism that selects either one or two agents out of a set of three agents and that is 3/4-optimal is shown on the right.

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 Hk-bound on the price of stability in undirected Shapley network design games
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.