Document

**Published in:** Dagstuhl Reports, Volume 12, Issue 5 (2022)

Traffic assignment models are crucial for transport planners to be able to predict the congestion, environmental and social impacts of transport policies, for example in the light of possible changes to the infrastructure, to the transport services offered, or to the prices charged to travellers. The motivation for this series of seminars - of which this seminar was the third - is the prevalence in the transportation community of basing such predictions on complex computer-based simulations that are capable of resolving many elements of a real systems, while on the other hand, the theory of dynamic traffic assignments (in terms of equilibrium existence, computability and efficiency) had not matured to the point matching the model complexity inherent in simulations.
Progress has been made on this issue in the first two seminars (Dagstuhl Seminar 15412 and 18102), by bringing together leading scientists in the areas of traffic simulation, algorithmic game theory and dynamic traffic assignment. We continued this process this seminar. Moreover, we started to address the growing real-life challenge of new kinds of 'mobility service' emerging, before the tools are available to incorporate them in such planning models. These services include intelligent/dynamic ride-sharing and car-sharing, through to fully autonomous vehicles, provided potentially by a variety of competing operators.

Martin Gairing, Carolina Osorio, Britta Peis, David Watling, and Katharina Eickhoff. Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192). In Dagstuhl Reports, Volume 12, Issue 5, pp. 92-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{gairing_et_al:DagRep.12.5.92, author = {Gairing, Martin and Osorio, Carolina and Peis, Britta and Watling, David and Eickhoff, Katharina}, title = {{Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192)}}, pages = {92--111}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {5}, editor = {Gairing, Martin and Osorio, Carolina and Peis, Britta and Watling, David and Eickhoff, Katharina}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.5.92}, URN = {urn:nbn:de:0030-drops-174441}, doi = {10.4230/DagRep.12.5.92}, annote = {Keywords: Algorithms and Complexity of traffic equilibrium computations, Dynamic traffic assignment models, Simulation and network optimization} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

We study the existence of approximate pure Nash equilibria (α-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously it was known that d-approximate equilibria always exist, while nonexistence was established only for small constants, namely for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have Θ̃(√d)-approximate PNE, which provides the first super-constant lower bound.
Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, deploying this technique we are able to show that deciding whether a weighted congestion game has an Õ(√d)-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions.
The circuit gadget is of independent interest and it allows us to also prove hardness for a variety of problems related to the complexity of PNE in congestion games. For example, we demonstrate that the question of existence of α-PNE in which a certain set of players plays a specific strategy profile is NP-hard for any α < 3^(d/2), even for unweighted congestion games.
Finally, we study the existence of approximate equilibria in weighted congestion games with general (nondecreasing) costs, as a function of the number of players n. We show that n-PNE always exist, matched by an almost tight nonexistence bound of Θ̃(n) which we can again transform into an NP-completeness proof for the decision problem.

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, and Clara Waldmann. Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ICALP.2020.32, author = {Christodoulou, George and Gairing, Martin and Giannakopoulos, Yiannis and Po\c{c}as, Diogo and Waldmann, Clara}, title = {{Existence and Complexity of Approximate Equilibria in Weighted Congestion Games}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.32}, URN = {urn:nbn:de:0030-drops-124392}, doi = {10.4230/LIPIcs.ICALP.2020.32}, annote = {Keywords: Atomic congestion games, existence of equilibria, pure Nash equilibria, approximate equilibria, hardness of equilibria} }

Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

In this paper, we study the problem of deciding the winner of reachability switching games. We study zero-, one-, and two-player variants of these games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP n coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. We also study the structure of winning strategies in these games, and in particular we show that exponential memory is required in both the one- and two-player settings.

John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani. Reachability Switching Games. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 124:1-124:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fearnley_et_al:LIPIcs.ICALP.2018.124, author = {Fearnley, John and Gairing, Martin and Mnich, Matthias and Savani, Rahul}, title = {{Reachability Switching Games}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {124:1--124:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.124}, URN = {urn:nbn:de:0030-drops-91282}, doi = {10.4230/LIPIcs.ICALP.2018.124}, annote = {Keywords: Deterministic Random Walks, Model Checking, Reachability, Simple Stochastic Game, Switching Systems} }

Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer d we construct rather simple games with cost functions of degree at most d which have a PoS of at least Omega(Phi_d)^{d+1}, where Phi_d ~ d/ln d is the unique positive root of equation x^{d+1}=(x+1)^d. This essentially closes the huge gap between Theta(d) and Phi_d^{d+1} and asymptotically matches the Price of Anarchy upper bound. We further show that the PoS remains exponential even for singleton games. More generally, we also provide a lower bound of Omega((1+1/alpha)^d/d) on the PoS of alpha-approximate Nash equilibria, even for singleton games. All our lower bounds extend to network congestion games, and hold for mixed and correlated equilibria as well.
On the positive side, we give a general upper bound on the PoS of alpha-approximate Nash equilibria, which is sensitive to the range W of the player weights and the approximation parameter alpha. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most (d+3)/2; the equilibrium's approximation parameter ranges from Theta(1) to d+1 in a smooth way with respect to W. Secondly, we show that for unweighted congestion games, the PoS of alpha-approximate Nash equilibria is at most (d+1)/alpha.

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis. The Price of Stability of Weighted Congestion Games. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 150:1-150:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ICALP.2018.150, author = {Christodoulou, George and Gairing, Martin and Giannakopoulos, Yiannis and Spirakis, Paul G.}, title = {{The Price of Stability of Weighted Congestion Games}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {150:1--150:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.150}, URN = {urn:nbn:de:0030-drops-91541}, doi = {10.4230/LIPIcs.ICALP.2018.150}, annote = {Keywords: Congestion games, price of stability, Nash equilibrium, approximate equilibrium, potential games} }

Document

**Published in:** LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. Users that do not transmit will not receive any feedback. We are interested in equilibrium protocols, where no player has an incentive to deviate.
The limited feedback makes the design of equilibrium protocols a hard task as best response policies usually have to be modeled as Partially Observable Markov Decision Processes, which are hard to analyze. Nevertheless, we show how to circumvent this for the case of two players and present an equilibrium protocol. For many players, we give impossibility results for a large class of acknowledgment-based protocols, namely age-based and backoff protocols with finite expected finishing time. Finally, we provide an age-based equilibrium protocol, which has infinite expected finishing time, but every player finishes in linear time with high probability.

George Christodoulou, Martin Gairing, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis. Strategic Contention Resolution with Limited Feedback. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ESA.2016.30, author = {Christodoulou, George and Gairing, Martin and Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul}, title = {{Strategic Contention Resolution with Limited Feedback}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {30:1--30:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.30}, URN = {urn:nbn:de:0030-drops-63813}, doi = {10.4230/LIPIcs.ESA.2016.30}, annote = {Keywords: contention resolution, acknowledgment-based protocols, game theory} }

Document

**Published in:** LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

We revisit a classical problem in transportation, known as the continuous (bilevel) network design problem, CNDP for short. Given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed, the goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing cost of the induced Wardrop equilibrium and the investment cost for installing the capacity. While this problem is considered as challenging in the literature, its complexity status was still unknown. We close this gap showing that CNDP is strongly NP-complete and APX-hard, both on directed and undirected networks and even for instances with affine latencies.
As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions (Math. Program., Vol. 34, 1986). We derive a closed form expression of its approximation guarantee for arbitrary sets of latency functions. We then propose a different approximation algorithm and show that it has the same approximation guarantee. However, we show that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we derive a closed form expression. For affine latencies, e.g., this algorithm achieves a 49/41-approximation which improves on the 5/4 that has been shown before by Marcotte. We finally discuss the case of hard budget constraints on the capacity investment.

Martin Gairing, Tobias Harks, and Max Klimm. Complexity and Approximation of the Continuous Network Design Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 226-241, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{gairing_et_al:LIPIcs.APPROX-RANDOM.2014.226, author = {Gairing, Martin and Harks, Tobias and Klimm, Max}, title = {{Complexity and Approximation of the Continuous Network Design Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {226--241}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.226}, URN = {urn:nbn:de:0030-drops-46998}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.226}, annote = {Keywords: Bilevel optimization, Optimization under equilibrium constraints, Network design, Wardrop equilibrium, Computational complexity, Approximation algorit} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

In this work, we consider an interesting variant
of the well-studied KP model [KP99] for selfish
routing that reflects some influence from the much
older Wardrop [War52]. In the new model, user
traffics are still unsplittable, while social cost
is now the expectation of the sum, over all links,
of a certain polynomial evaluated at the total
latency incurred by all users choosing the link;
we call it polynomial social cost. The polynomials
that we consider have non-negative coefficients.
We are interested in evaluating Nash equilibria in
this model, and we use the Price of Anarchy as our
evaluation measure. We prove the Fully Mixed Nash
Equilibrium Conjecture for identical users and two
links, and establish an approximate version of the
conjecture for arbitrary many links. Moreover, we
give upper bounds on the Price of Anarchy.

Martin Gairing, Thomas Lücking, Marios Mavronicolas, and Burkhard Monien. The Price of Anarchy for Polynomial Social Cost. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{gairing_et_al:DagSemProc.05011.19, author = {Gairing, Martin and L\"{u}cking, Thomas and Mavronicolas, Marios and Monien, Burkhard}, title = {{The Price of Anarchy for Polynomial Social Cost}}, booktitle = {Computing and Markets}, pages = {1--12}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {5011}, editor = {Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.19}, URN = {urn:nbn:de:0030-drops-2005}, doi = {10.4230/DagSemProc.05011.19}, annote = {Keywords: selfish routing , KP-model , price of anarchy , fully mixed Nash Equilibrium} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail