Convergence in a Repeated Non-atomic Routing Game with Partial Signaling
We study the following repeated non-atomic routing game. In every round, nature chooses a state in an i.i.d. manner according to a publicly known distribution, which influences link latency functions. The system planner makes private route recommendations to participating agents, which constitute a fixed fraction, according to a publicly known signaling strategy. The participating agents choose between obeying or not obeying the recommendation according to cumulative regret of the participating agent population in the previous round. The non-participating agents choose route according to myopic best response to a calibrated forecast of the routing decisions of the participating agents. We show that, for parallel networks, if the planner's signal strategy satisfies the obedience condition, then, almost surely, the link flows are asymptotically consistent with the Bayes correlated equilibrium induced by the signaling strategy.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Generalized Mirror Descents in Congestion Games
Different types of dynamics have been studied in repeated game play, and one of them which has received much attention recently consists of those based on "no-regret" algorithms from the area of machine learning. It is k…
Social Learning in Nonatomic Routing Games
We consider a discrete-time nonatomic routing game with variable demand and uncertain costs. Given a routing network with single origin and destination, the cost function of each edge depends on some uncertain persistent…
Urgency-aware Optimal Routing in Repeated Games through Artificial Currencies
When people choose routes minimizing their individual delay, the aggregate congestion can be much higher compared to that experienced by a centrally-imposed routing. Yet centralized routing is incompatible with the prese…
ARCOn the Convergence of No-Regret Learning Dynamics in Time-Varying Games
Most of the literature on learning in games has focused on the restrictive setting where the underlying repeated game does not change over time. Much less is known about the convergence of no-regret learning algorithms i…
Meta-LearningFast Routing under Uncertainty: Adaptive Learning in Congestion Games via Exponential Weights
We examine an adaptive learning framework for nonatomic congestion games where the players' cost functions may be subject to exogenous fluctuations (e.g., due to disturbances in the network, variations in the traffic goi…