Let us first illustrate the concepts and the problem in the following simple example which is also illustrated in Figure 1.

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.

$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.

- Improved Approximation Algorithms for the Expanding Search Problem ( )

ESA 2023 – Proc. 31st European Symposium on Algorithms, pp. 54:1–54:15.

@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. - Public Signals in Network Congestion Games ( )

EC 2022 – Proc. 23rd ACM Conference on Economics and Computation, pp. 736.

@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.