It is a well-known fact that selfish behavior degrades the performance of traffic networks. A popular model to study these effects is the traffic model of Wardrop. Here, the road network is modeled as a directed graph where each edge of the graph corresponds to a road segment. The travel times in the graph are modeled as cost functions on the edges where the cost of an edge is a function of the total flow on that edge.
In this project, we study a generalization of the model where the travel time of each edge also depends to a state of the world $\theta \in \Theta$ that is unknown to the traffic participants. However, the traffic participants share a common belief regarding the state of the world. In real-world traffic networks, the state $\theta$ may model certain weather or traffic scenarios. We put ourselves in the shoes of a benevolent mediator who knowns the true state of the world before any flow is routed. In practice, this corresponds to a traffic service provider before the rush hour.
The mediator may now strategically reveal information about the state of the world regarding the true state of the world in order to induce a good traffic equilibrium, i.e., an equilibrium with a low overall travel time. It is interesting to note that in order to obtain a good equilibrium it may be beneficial for the system designer to not reveal the full information about the state of the world. Instead, it may be good to only partially reveal the knowledge in order to have more control on the user behavior.
In this project, we study the mathematical problem of computing the optimal information structures that induce best-possible equilibria in these settings.
State-dependent offsets
Consider a single-commodity setting with affine cost functions $c_e(x) = a_e x + b_e^{\theta}$ for each edge $e$, where the offset $b_e^{\theta}$ depends on the realized state $\theta$.
Let us first illustrate the concepts and the problem in the following simple example which is also illustrated in Figure 1.
Example 1
Consider a single-commodity network with two vertices $V=\{s,t\}$ and three parallel edges. There are two states $\theta_1$ and $\theta_2$. There is a single commodity with a volume of $1$. The cost functions are given in Figure 1.
Figure 1. Cost functions for state $\theta_1$; cost functions for state $\theta_2$; cost of the resulting Wardrop equilibrium as a function of the prior $\mu$.
We analyze the Wardrop equilibrium for all distributions $\mu \in \Delta(\Theta)$, where $\Delta(\Theta)$ is interpreted as the unit interval for $\mu_2 = 1-\mu_1 \in [0,1]$. For $\mu_2 \in [0,1/4]$, the equilibrium only uses the lowest edge, since the total cost for a volume of $1$ is at most $3$, whereas both other edges have an offset of at least $3$. For $\mu_2 \in [1/4, 2/5]$, the equilibrium uses only the two lower edges, since the upper edge has an offset of at least $3$. For $\mu_2 \in [2/5, 3/4]$ the equilibrium uses all three edges. Then, for $\mu_2 \in [3/4, 4/5]$, the equilibrium uses only the two upper edges, since the offset of the lowest edge is at least three and therefore too high. Finally, for $\mu_2 \in [4/5, 1]$, only the upper edge is used. Figure 1(c) shows the cost $C(\mu)$ of the resulting Wardrop equilibrium for all $\mu \in \Delta(\Theta)$ in blue. Clearly, we see that $C(\mu)$ is piecewise linear and concave over $\Delta(\Theta)$.
A signaling scheme $\Phi$ is a convex decomposition of $\mu$ into distributions $\mu(\sigma) \in \Delta(\Theta)$, and $C(\Psi)$ is a convex combination of $C(\mu(\sigma))$. Since the cost is concave over $\Delta(\Theta)$, we know that $C(\mu_2) \geq \mu_2 C(1)+(1-\mu_2)C(0)$ for all $\mu_2 \in [0,1]$
as indicated by the orange function in Figure 1.
This shows that, instead of mixing states into a signal with some interior distribution $\mu \in (0,1)$, we rather want to send signals with $\mu \in \{0,1\}$ that fully reveal the information about the state of nature. This can only improve the overall cost of $C(\Phi)$. Therefore, there is an optimal signaling scheme in which the principal sends an exclusive signal $\sigma$ for each state $\theta$.
A main result of our work is the following.
Theorem 1
For a single-commodity network $G$ with affine costs and unknown offsets, full information revelation is always an optimal signaling scheme if and only if $G$ is series-parallel.
In fact, if $G$ is not series-parallel, there always exist cost functions, such that full information revelation is not an optimal signaling scheme. Such a graph is given in the following example.
Example 2
Consider the graph shown in Figure 2.
Figure 1. Cost functions for state $\theta_1$; cost functions for state $\theta_2$; cost of the resulting Wardrop equilibrium as a function of the prior $\mu$.
The cost functions are shown in Figure 2. Note that only the cost of the middle edge changes in the different states. We claim that full information revelation is suboptimal in this example.
Consider the two different supports: $A_1$ consist of all edges except the middle edge, and $A_2$ contains all edges.
For support $A_1$, we obtain the Wardrop equilibrium where the flow is equally split among the upper and the lower path for all $\mu \in \Delta(\Theta)$. For support $A_2$ we obtain the Wardrop equilibrium where flow of size $1-\mu_2$ goes via both the upper and lower path while flow of size $1-2\mu_2$ is routed via the zig-zag-path for all $\mu \in \Delta(\Theta)$.
This yields the following cost for the supports:
$C(A_1(\mu))=2\cdot \frac{1}{2} \cdot \frac{1}{2} + 2 \cdot \frac{1}{2} =\frac{3}{2}$
$C(A_2(\mu))=2\cdot (1-\mu_2)(1-\mu_2) + 2\mu_2 + (1-2\mu_2)\mu_2 = 2-\mu_2$.
However, for any $\mu_2 < 1/2$, the flow defined by support $A_1$ is not a Wardrop equilibrium for the whole graph, since deviating to the zig-zag-path would reduce private costs. Furthermore, for any $\mu_2 >1/2$, the flow defined by support $A_2$ is not a Wardrop equilibrium for the whole graph since the flow on the middle edge were negative.
Hence, the pointwise minimum is not a concave function, as illustrated in Figure 3(c). For a prior of $\mu^* = (1/2,1/2)$, full information revelation would yield a cost of $\frac{1}{2} \cdot 2 + \frac{1}{2}\cdot \frac{3}{2}= \frac{7}{4}$. In contrast, sending a single signal in all states does not reveal any information about the state, so that the Wardop equilibrium with cost of 3/2 emerges. Hence, full information revelation is not optimal.
@inproceedings{GriesbachHommelsheimKlimm+2023, author = {Svenja M. Griesbach and Felix Hommelsheim and Max Klimm and Kevin Schewior}, title = {Improved Approximation Algorithms for the Expanding Search Problem}, booktitle = {ESA 2023 – Proc. 31st European Symposium on Algorithms}, year = {2023}, accepted = {23.06.2023}, pages = {54:1--54:15}, doi = {10.4230/LIPIcs.ESA.2023.54}, }
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.
@inproceedings{GriesbachHoeferKlimm+2022, arxiv = {2205.09823}, author = {Svenja M. Griesbach and Martin Hoefer and Max Klimm and Tim Koglin}, booktitle = {EC 2022 – Proc. 23rd ACM Conference on Economics and Computation}, doi = {10.1145/3490486.3538349}, pages = {736}, title = {Public Signals in Network Congestion Games}, year = {2022}, }
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.