Uniform Mixed Equilibria in Network Congestion Games with Link Failures
研究了网络拥塞博弈中链路故障下的均匀混合均衡，证明了加权代理且延迟函数为仿射时均衡存在并刻画了无政府价格，对无权重代理则扩展至任意延迟函数。
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 [Formula: see text], a ρ-uniform mixed strategy is a mixed strategy in which an agent plays exactly ρ edge-disjoint paths with uniform probability; therefore, a ρ-uniform mixed equilibrium is a tuple of ρ-uniform mixed strategies, one for each agent, in which no agent can lower her cost by deviating to another ρ-uniform mixed strategy. For games with weighted agents and affine latency functions, we show the existence of ρ-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. Funding: This work was partially supported by the INdAM-GNCS and the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Markets.”