The price of Anarchy in series-parallel network congestion games

• 成果类型: Article
• 署名作者: Hao, Bainian; Michini, Carla
• 署名单位: University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01803-w
• 发表日期: 2024
• 页码: 499-529
• 关键词: equilibria; INEFFICIENCY; EFFICIENCY; STABILITY; DESIGN; FLOW

摘要

We study the inefficiency of pure Nash equilibria in symmetric network congestion games defined over series-parallel networks with affine edge delays. For arbitrary networks, Correa (Math Oper Res 44(4):1286-1303, 2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, for extension-parallel networks, a subclass of series-parallel networks, Fotakis (Theory Comput Syst 47:113-136, 2010) proved that the PoA is 4/3. He also showed that this bound is not valid for series-parallel networks by providing a simple construction with PoA 15/11. Our main result is that for series-parallel networks the PoA cannot be larger than 2, which improves on the bound of 5/2 valid for arbitrary networks. We also construct a class of instances with a lower bound on the PoA that asymptotically approaches 27/19, which improves on the lower bound of 15/11.