Speaker:

Bainian Hao (University of Wisconsin-Madison)

Time:

• 16:20-17:20 Beijing Time
• Nov 8, 2024 (Friday)

Venue:

518, Research Building 4

Abstract:

Congestion games are commonly used to model problems in large-scale networks and represent a simple, yet powerful paradigm for selfish resource sharing. These games belong to the larger class of potential games where the pure Nash equilibria is guaranteed to exist. However, the cost of pure Nash equilibria could still be far from minimizing some prescribed measure of social cost. The Price of Anarchy (PoA), which is the largest ratio between the cost of pure Nash equilibria and the cost of the social optimum, is a classic measure of inefficiency in game theory. In this work, we study the PoA of congestion games over special combinatorial structures, specifically series-parallel networks and matroids.

First, we consider symmetric congestion games in series-parallel networks with affine edge delays. For arbitrary networks, Correa et al. (2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, Fotakis (2010) showed that restricting to the class of extension-parallel networks makes the worst-case PoA decrease to 4/3. We prove that, for the larger class of series-parallel networks, the PoA is at most 2, and that it is at least 27/19 in the worst case, improving both the best-known upper bound and the best-known lower bound.

Next, we consider symmetric congestion games with edge delays that are polynomial functions with highest degree p. We construct a family of symmetric congestion games over arbitrary networks which achieves the same worst-case PoA of asymmetric network congestion games given by Aland et al. (2006). We then establish that in games defined over series-parallel networks the PoA cannot exceed 2^{p+1} – 1, which is considerably smaller than the worst-case PoA in arbitrary networks. We also prove that the worst-case PoA, which is sub-linear in extension-parallel networks (Fotakis, 2010), dramatically degrades to exponential in series-parallel networks.

Finally, we study the PoA of congestion games in matroids. We derive new upper bounds on the PoA of symmetric congestion games defined over k-uniform matroids and paving matroids with polynomial delay functions of highest degree p. Specifically, we show that by restricting the matroid structure to k-uniform or paving matroid, there is also a significant improvement of the PoA.

This is a joint work with Dr. Carla Michini.

Speaker Bio:

Bainian Hao (郝柏年) has received the Ph.D. degree in Industrial Engineering from University of Wisconsin-Madison, advised by Dr. Carla Michini. He will join the School of Economics and Management at the Chang’an University in Spring 2025.

Bainian is interested in the areas of algorithmic game theory, integer optimization, combinatorial optimization and their applications in the real-world problems. His works has been published in the international journals and conferences such as Mathematical Programming, WINE, and SAGT.