Post by jia on Sept 27, 2020 15:48:03 GMT
Ex16.2: Consider an atomic selfish routing game with m edges and cost functions taking values in {1, 2, 3, . . . , H}. Prove that best-response dynamics converges to a PNE in at most mH iterations.
Suppose there are only 2 edges, where one has cost c(x)=H and the other has cost c'(x)=1. Suppose all k agents were initially on the edge with cost c(x)=H. So every agent has the incentive to deviate. The equilibrium occurs when all agents are on the edge with cost c'(x)=1. Since there are k agents, the best-response dynamics need to take k iterations to converge to a PNE. If k>2H (we suppose m=2 at the beginning), the converge will take more than 2H iterations. Based on this example, why is the bound not dependent on the number of agents?
Thanks!
Suppose there are only 2 edges, where one has cost c(x)=H and the other has cost c'(x)=1. Suppose all k agents were initially on the edge with cost c(x)=H. So every agent has the incentive to deviate. The equilibrium occurs when all agents are on the edge with cost c'(x)=1. Since there are k agents, the best-response dynamics need to take k iterations to converge to a PNE. If k>2H (we suppose m=2 at the beginning), the converge will take more than 2H iterations. Based on this example, why is the bound not dependent on the number of agents?
Thanks!
