Uniform Mixed Equilibria in Network Congestion Games with Link Failures

• 成果类型: Article
• 署名作者: Bilo, Vittorio; Moscardelli, Luca; Vinci, Cosimo
• 署名单位: University of Salento; G d'Annunzio University of Chieti-Pescara; Gran Sasso Science Institute (GSSI)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.1365
• 发表日期: 2024
• 关键词: price; STABILITY; DESIGN; ANARCHY; bounds

摘要

Motivated by possible applications in fault-tolerant selfish routing, we introduce the notion of uniform mixed equilibrium in network congestion games with adversarial link failures, where agents need to route traffic from a source to a destination node. Given an integer p >_ 1, a p-uniform mixed strategy is a mixed strategy in which an agent plays exactly p edge-disjoint paths with uniform probability; therefore, a p-uniform mixed equilibrium is a tuple of p-uniform mixed strategies, one for each agent, in which no agent can lower her cost by deviating to another p-uniform mixed strategy. For games with weighted agents and affine latency functions, we show the existence of p-uniform mixed equilibria and provide a tight characterization of their price of anarchy. For games with unweighted agents, we extend the existential guarantee to any class of latency functions, and restricted to games with affine latencies, we derive a tight characterization of the price of anarchy and the price of stability.