王长军- 原子动态流游戏：自适应代理与非自适应代理.pdf

1、Atomic Dynamic Flow Games:Adaptive versus Nonadaptive AgentsZhigang Cao1,Bo Chen2,Xujin Chen3,Changjun Wang31Beijing Jiaotong University2University of Warwick3AMSS,Chinese Academy of SciencesRLChina 2024,GuangzhouZhigang Cao1,Bo Chen2,Xujin Chen3,Changjun Wang3Atomic Dynamic Flow Games:Adaptive vers

2、us Nonadaptive AgentsSelfish routingrelated to classical combinational optimization problems(shortest-path problems,min-cost-max-flow problems)important to traffi c Wardrop 1952important to Algorithmic Game Theory Roughgarden 2007,Roughgarden/Tardos 2002important to game theorya.k.a.congestion gamee

3、quivalent to potential gamesmain drawback:essentially static flows via latency functionsZhigang Cao1,Bo Chen2,Xujin Chen3,Changjun Wang3Atomic Dynamic Flow Games:Adaptive versus Nonadaptive AgentsLatency function:Pigous examplex:number of players using a roadupper road:very wide(but long),with a con

4、stant latencyfunction c(x)=10(mins)lower road:narrow(but very short),with a nonconstant latencyfunction c(x)=x/2(mins)Zhigang Cao1,Bo Chen2,Xujin Chen3,Changjun Wang3Atomic Dynamic Flow Games:Adaptive versus Nonadaptive AgentsLatency function:equilibrium V.S.optimizationsuppose there are 20 players

5、in totalequilibrium:all players choose the lower road(each with cost 10)optimalization:10 choose upper road and 10 choose lower road(lower with cost 5,upper with cost 10)Zhigang Cao1,Bo Chen2,Xujin Chen3,Changjun Wang3Atomic Dynamic Flow Games:Adaptive versus Nonadaptive AgentsLatency function:two d

6、rawbacksoverly symmetric:later players can also impede earlier playerson the same roadstatic(steady)flows:cannot capture the dynamic featuresZhigang Cao1,Bo Chen2,Xujin Chen3,Changjun Wang3Atomic Dynamic Flow Games:Adaptive versus Nonadaptive AgentsDynamic routing gamesHave been studied over 50 yeas