Combinatorial Optimization & Graph Algorithms group (COGA)Network and Mechanism Design for Metropolitan Infrastructures

# Network and Mechanism Design for Metropolitan Infrastructures

To top

## Funding Information

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

Duration: June 2014 - Mai 2017

Scientific Staff: Antje Bjelde

To top

## 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 patters.

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 \in E}$ that minimizes the sum of routing cost of the induced Wardrop equilibrium and the investment cost, i.e.,

\begin{align}&\tag{1}\min\nolimits_{\mathbf{f},\mathbf{z} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e\Bigl(\frac{f_e}{z_e}\Bigr)\,f_e + l_e z_e\\ &\text{s.t. } \mathbf{f} \text{ is a Wardrop flow}\,,\end{align}

where $l_e \geq 0$ 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}&\tag{2}\min\nolimits_{\mathbf{f},\mathbf{z} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e\Bigl(\frac{f_e}{z_e}\Bigr)\,f_e + l_e z_e\\ &\text{s.t. } \mathbf{f} \in \arg\min\nolimits_{\mathbf{g} \text{ flow}} \sum_{e \in E} \int_0^{g_e} \! c_e(x) \,\text{d}x\,.\end{align}

In Gairing et al. (2014), we show that the problem (2) is $\mathsf{APX}$-hard, i.e., there is a constant $\epsilon>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}&\tag{3}\min\nolimits_{\mathbf{f},\mathbf{z} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e\Bigl(\frac{f_e}{z_e}\Bigr)\,f_e + l_e z_e\\ &\text{s.t. } \mathbf{f} \text{ flow }\end{align}

can be solved straightforwardly by computing one shortest path for each commodity.

In Gairing et al. (2014), we analyze the performance of two algorithms that are based on the solution of the relaxation (3). The first algorithm was proposed by Marcotte for the special case that the function $c_e$ 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 $\mu(\mathcal{S})$ 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 \approx 1.195$.

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}&\tag{4}\min\nolimits_{\mathbf{f},\mathbf{t} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e(f_e)\,f_e \\ &\text{s.t. } \mathbf{f} \text{ is a Wardrop flow w.r.t. } c_e(f_e) + t_e.\end{align}

which is equivalent to

\begin{align}&\tag{5}\min\nolimits_{\mathbf{f},\mathbf{t} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e(f_e)\,f_e \\ &\text{s.t. } \mathbf{f} \in \arg\min\nolimits_{\mathbf{g} \text{ flow }} \sum_{e \in E} \int_0^{g_e} c_e(x) + t_e \,\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 et al. (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}&\tag{6}\min\nolimits_{\mathbf{f},\mathbf{z} \in \mathbb{R}_{\geq 0}^m} \sum_{e \in E} c_e(f_e)\,f_e \\ &\text{s.t. } \mathbf{f} \text{ is a Wardrop flow w.r.t. } c_e(f_e) + t_e\\ &\phantom{\text{s.t.}}t_e = 0 \text{ for all } e \notin T\end{align}

As this problem is $\mathsf{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 = (V,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\} \times 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 et al. (2015), 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.

### Existence of Equilibria

In all of the models above, the existence of a Nash equilibrium in deterministic strategies is granted. For the non-monetary access protocols the existence of an equilibrium is by design; for Wardrop equilibria, the equilibrium conditions can be obtained as the local optimality conditions of a convex optimization problem which implies the existence of an equilibrium.

For other strategic environments, the existence of an equilibrium may be more subtle and we provide general existence results for different models:

• In Harks and Klimm (2015), we study a general class of aggregative games where the players' strategies consists of choosing a location out of a finite set and an intensity out of a compact interval of intensities. Such games model, e.g., multimarket Cournot oligopolies where each player can only serve one market at a time. The combination of discrete and continuous choices renders the strategy space infinite and non-convex such that standard proof techniques for the existence of equilibria do not apply. We give a set of axioms under which the existence of a pure Nash equilibrium can be proven. For a generalization towards multimarket oligopolies where more than one market can be chosen, see Harks and Klimm (2014).
• In Hansknecht et al. (2014) we deal with weighted congestion games which are similar to Wardrop's traffic model but require that all commodities route their flow along a single path. In contrast to Wardrop's model, weighted congestion need not admit an equilibrium. This was shown, e.g., by Goemans et al. (2005) who constructed a weighted congestion game with two players and quadratic latency functions on the edges for which full enumeration of the strategy profiles shows that no equilibrium exists. Quite strikingly, however, the game constructed by Goemans et al. admits a strategy vector from which no player may improve by a factor larger than $61/60 \approx 1.017$. We are interested in determining the minimal $\alpha > 1$ for which an $\alpha$-approximate equilibrium exists. We give different upper bounds on $\alpha$ for latency functions with polynomial latency functions. For quadratic latency functions (as considered by Goemans et al., e.g., we show that there is always a $1.054$-approximate equilibrium for games with two player and a $4/3$-approximate equilibrium for games with an arbitrary number of players, where the former bound is tight. For general concave latency functions, we show the existence of a $3/2$-approximate equilibrium.
• A generalization of weighted congestion games where the demand vector of each player may have a dimension larger than one was considered in Klimm and Schuetz (2014). We give tight characterization for the existence of pure Nash equilibria depending on the classes of cost functions on the resources.

## 2017

Bjelde, A., Disser, Y., Hackfeld, J., Hansknecht, C., Lipmann, M., Meißner, J., Schewior, K., Schlöter, M. and Stougie, L.
Tight bounds for online TSP on the line.
In Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 994–1005, 2017.  [pdf]

## 2016

Disser, Y., Hackfeld, J. and Klimm, M.
Undirected graph exploration with Θ(log log n) pebbles.
In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 25-39, 2016.  [pdf]

Harks, T. and Klimm, M.
Congestion games with variable demands.
Mathematics of Operations Research, Vol. 41, pp. 255-277, 2016.

## 2015

Bjelde, A., Fischer, F. and Klimm, M.
Impartial Selection and the Power of Up to Two Choices.
In Proceedings of the 11th Conference on Web and Internet Economics (WINE), 2015.

Harks, T. and Klimm, M.
Bottleneck Routing with Elastic Demands.
In Proceedings of the 11th Conference on Web and Internet Economics (WINE), 2015.

Harks, T. and Klimm, M.
Equilibria in a Class of Aggregative Location Games.
Journal of Mathematical Economics, Vol. 61, pp. 211-220, 2015.

Disser, Y., Feldmann, A., Klimm, M. and Mihalák, M.
Improving the Hk-bound on the price of stability in undirected Shapley network design games.
Theoretical Computer Science, Vol. 562, pp. 557–564, 2015.  [pdf]

Disser, Y., Klimm, M. and Lübbecke, E.
Scheduling Bidirectional Traffic on a Path.
In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 406-418, 2015.  [pdf]

Fischer, F. and Klimm, M.
Optimal Impartial Selection.
SIAM Journal on Computing, Vol. 44, pp. 1263-1285, 2015.  [pdf]

Harks, T., Kleinert, I., Klimm, M. and Möhring, R. H.
Computing network tolls with support constraints.
Networks, Vol. 65, pp. 262-285, 2015.

Klimm, M. and Schmand, D.
Sharing non-anonymous costs of multiple resources optimally.
In Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC), pp. 274-287, 2015.

## 2014

Hansknecht, C., Klimm, M. and Skopalik, A.
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, 2014.

Harks, T. and Klimm, M.
Multimarket oligopolies with restricted market access.
In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), pp. 182-193, 2014.

Gairing, M., Harks, T. and Klimm, M.
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, 2014.

Harks, T., Klimm, M. and Peis, B.
Resource Competition on Integral Polymatroids.
In Proceedings of the 10th Conference on Web and Internet Economics (WINE), 2014.

Klimm, M. and Schütz, A.
Congestion games with higher demand dimensions.
In Proceedings of the 10th Conference on Web and Internet Economics (WINE), pp. 453-459, 2014.

To top