ICALP 2023 Workshop - Congestion Games

Monday, July 10, 2023

Please visit ICALP 2023 Workshops for general information.

Over the last decades, congestion games have played a staring role in the study of non-cooperative resource allocation. They are expressive enough to model many real-world applications where resources are scarse and there is competition for their use. For example, congestion games can be used to model the allocation of airport gates or highway lanes during peak travel times.

Congestion games shed light on the ways in which individuals make decisions in these situations. Understanding this behaviour allows policymakers and planners to make more informed decisions, e.g. by designing tools that improve efficiency. Congestion games also played a pivotal role for the algorithmic game theory community as many concepts such as the efficiency of equilibria, local search procedures, convergence of learning, or coordination mechanism to improve the quality of the equilibria were first studied for this class of games.

This workshop provides a forum for presenting and discussing recent advances and key challenges in congestion games and beyond. It will bring together researchers working on different aspects of congestion games and foster collaborations also with the wider TCS community.

Martin Gairing (University of Liverpool)
Max Klimm (TU Berlin)
Dario Paccagnan (Imperial College London)



Time Session
9:00 - 10:30
  • Svenja M. Griesbach (Technische Universität Berlin)
    Information Design for Congestion Games with Unknown Demand
  • Abstract: This paper considers non-atomic congestion games with affine costs and a single commodity whose demand is unknown to the players of the game, but can be observed by a principal. Prior to observing the demand, the principal commits to a public signaling scheme that governs to which extend (if at all) the information about the realized demand is communicated to the players. Upon receiving the signal, the players update their beliefs about the demand and respond by playing a Wardrop equilibrium for the resulting cost functions. We study the question of how to compute the signaling scheme that minimizes the total cost of the induced Wardrop equilibrium.
    First, we devise a fully polynomial-time approximation scheme (FPTAS) for the case that the demand can only take two values. The FPTAS relies on several structural properties of the cost of the induced Wardrop equilibrium as a function of the updated belief of the distribution of demands. We show that this function is piecewise linear for any number of demands, and monotonic for two demands.
    Second, we give a complete characterization of the graph structures where it is optimal for the principal to fully reveal the information about the realized demand to the players. Specifically, we show that this signaling scheme is optimal for all cost functions and probability distributions over demands if and only if the graph is series-parallel. Third, we propose an algorithm that computes the optimal signaling scheme for any number of demands whose time complexity is polynomial in the number of supports that occur in a Wardrop equilibrium for some demand. Finally, we conduct a computational study that tests this algorithm on real-world instances.
  • Miriam Fischer (Imperial College London)
    Weighted Congestion Games: Hardness and Optimal Approximation Through Taxes
  • Abstract: We consider the problem of minimizing social cost for the widely studied class of weighted congestion games and ask the following central question: How much can efficiently-computable taxation mechanisms help in improving the equilibrium efficiency? We settle this question through two independent contributions.
    • On the negative side, we show that minimizing the social cost is NP-hard to approximate below an explicitly given factor independently of whether players are self-interested or centrally controlled.
    • On the positive side, we show how to derive efficiently-computable taxation mechanisms whose equilibrium efficiency matches the aforementioned hardness factor.
    Taken together, these contributions show that judiciously designed taxes are as a good of a mean to incentivize players as any other approach, including that of centrally controlling their actions. As our hardness factor matches the approximation factor obtained by Makarychev and Sviridenko (2018) for the broader class of optimization problems with a diseconomy of scale, our work also shows that their result is the best possible.
    This is joint work Martin Gairing and Dario Paccagnan.
10:30 - 11:00 Coffee Break
11:00 - 12:30
  • Wouter Fokkema (University of Twente)
    The Price of Anarchy for Matroid Congestion Games
  • Abstract: We consider atomic, symmetric congestion games with linear cost functions, for which it is known that the price of anarchy is at most (5n-2)/(2n+1). It was open if restricting the players strategy spaces to the bases of a matroid allows for improved upper bounds on the price of anarchy. We essentially answer this question negatively. Specifically, we consider the case in which players select edges of a graph to obtain a spanning tree.
    We show that the price of anarchy of this game equals the known upper bound (5n-2)/(2n+1) when the number of players n is equal to 2, 3, 4, or when n tends to infinity. That means that, for these values of n, restricting strategy spaces to bases of a matroid does not impact the price of anarchy of atomic, linear congestion games. It is conceivable that the same is true also for other values of n.
  • Alexander Skopalik (University of Twente)
    Two stage facility location games
  • Abstract: We consider two stage sequential games with two types of players. In the first stage a set of players called facilities decide on which and where resources are provided. In the second stage another set of players called clients compete among each other over the use of these resources. We discuss recent results in which the second stage game corresponds to different types of congestion games. We study the existence, complexity and efficiency of equilibria of the two stage sequential games where the second stages resemble non-atomic congestion games, integer-splittable congestion games, and atomic congestion games.
    This is joint work with Simon Frogman, Pascal Lenzner, Louis Molitor, Marnix Vos, and Marc Uetz.
12:30 - 14:00 Lunch Break
14:00 - 15:30
  • Gleb Polevoy and Jonas Schweichhart (Paderborn University)
    Changing Equilibria Using Control Sets
  • Abstract: Many interactions result in a socially suboptimal equilibrium, while theoretically having socially better equilibria, too. Aiming to achieve the better equilibria, we let a selected group of the (loyal or bribed) participants act in a way that will motivate the rest of the players to act accordingly to the socially optimal equilibrium. Formally, we ask which subset of the players can adopt strategies that will make acting according to the desired equilibrium a best response for the other players. We call such a subset a control set and study its possible sizes and structures.
    We prove that, while the problem of finding such a set is NP-hard, even for constant-factor approximation, we can still solve the problem approximately or even precisely in important special cases. We approximately solve this problem for congestion games, and treat more closely specific potential games, such as symmetric games, coordination games on graphs, routing games, and singleton congestion games.
  • Daniel Schmand (University of Bremen)
    Bicriteria Nash Flows over Time
  • Abstract: Flows over time are a natural way to incorporate flow dynamics that arise in various applications such as traffic networks. In this paper we introduce a natural variant of the deterministic fluid queuing model in which users aim to minimize their costs subject to arrival at their destination before a pre-specified deadline. We determine the existence and the structure of Nash flows over time and fully characterize the price of anarchy for this model. The price of anarchy measures the ratio of the quality of the equilibrium and the quality of the optimum flow, where we evaluate the quality using two different natural performance measures: the throughput for a given deadline and the makespan for a given amount of flow. While it turns out that both prices of anarchy can be unbounded in general, we provide tight bounds for the important subclass of parallel path networks. Surprisingly, the two performance measures yield different results here.
    This is joint work with Tim Oosterwijk and Marc Schröder.