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.
|9:00 - 10:30||
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.
This is joint work Martin Gairing and Dario Paccagnan.
|10:30 - 11:00||Coffee Break|
|11:00 - 12:30||
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.
|12:30 - 14:00||Lunch Break|
|14:00 - 15:30||
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.