ICALP 2023 Workshop - Congestion Games

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.

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.

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.

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.

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.

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.