Pruning Algorithms for A Replicator Dynamics Method in Multiple OD Selfish Routing Games

  • Guu Kofujita The University of Electro-Communications
  • Satoshi Takahashi The University of Electro-Communications
Keywords: multi-od selfish routing, pruning method, replicator dynamics


A traffic flow allocation has been studied by many researches. This problem is treated by both urban planning research and game theoretical approaches. We stand on game theory to consider the traffic flow allocation problem by treating a class of congestion games on the network. The traffic flow allocation is called, in context the congestion game, a selfish routing game. In this game, our proposal is to find an equilibria of decision making of the players. The player’s decision is amounts of flows for each origin-destination path. It is known that the equilibrium searching problem as edge based modeling is able to compute easily by using Frank-Wolfe method, however, the edge based model has weak expressiveness. Thus we employ a path based modeling that can treat some complex phenomena. In this model, since we need to handle many paths in a network, it is known that the equilibrium searching problem is difficult.
In this paper, we study a solving method for a multi OD selfish routing game, and a method for solving standard routing games and its high speeding method. Our algorithm employs a replicator dynamics which is one of iterative optimization techniques. In the solution based on the replicator dynamics, the calculation time is very large, since the calculation is also performed for all paths. Therefore, as a preprocessing of solving by replicator dynamics, the policy of the proposed method is to make computation time faster by deleting unused paths. This paper evaluates the algorithm by numerical experiment.


J. Leape: The London Congestion Charge. Journal of Economic Perspectives, 20(4), (2006)157–176.

K.A. Small, E.T. Verhoef, and R. Lindsey: The economics of ueban transporta-tion. Routledge in Tayler & Francis, (2007).

D. Monderer and L.S. Shapley: Potential Games. GAMES AND ECONOMIC BEHAVIOR, 14, (1996)124-143.

T. Roughgarden: Routing Games, Algorithmic Game Theory, Noan Nisan, Tim Roughgarden, Eva Tardos, Cijay V. Vazirani,CAMBRIDGE UNIVERSITY PRESS, (2007)461-484.

K. Yoshida, T. Okamoto and S. Koakutsu: Equilibrium Solution Search on a Selfish Routing Problem with Multiple Constraints using the Variable Metric Gradient Projection Method. 2015 IEEE International Conference on Systems, Man, and Cybernetics, (2015)3023–3029.

S. Fischer and B. Vocking: On the Evolution of Selfish Routing. Algorithms ‒ ESA 2004,(2004)323–334.

M.J. Smith: The existence, uniqueness and stability of traffic equilibria. Transportation Research Part B: Methodological, 13(4), (1979)295–304.

A.K. Ziliaskopoulos: A Liner Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem. Presentation preprint, Transportation Research Boarai, Washington, D. C., (1997).

S. Suri, C.D. Toth, and Y. Zhou: Selfish Load Balancing and Atomic Congestion Games. Algorithmica,47(1), (2007)79–96.

R. Cressman and Y. Tao: The replicator equation and other game dynamics. Proceedings of the National Academy of Sciences of the United States of America, 111, (2014)10810–10817.

P. Schuster and K. Sigmund: Replicator dynamics. Journal of Theoretical Biology, 100(3), (1983)533–538.

K. Yoshida, T. Okamoto and S. Koakutsu: An Efficiency Improvement of the Equilibrium Solution Search on the Selfish Routing Game by Removing Redundant Paths. SICE Journal of Control, Measurement, and System Integration, 9, (2016)234–241.

JPN network. IEICE: PN Homepage, (2018/11/15 Accessed)

A. Taguchi: TIME DEPENDENT TRAFFIC ASSIGNMENT MODEL FOR COMMUTER TRAFFIC IN TOKYO METROPOLITAN RAILWAY NETWORK. Transactions of the Operations Research Society of Japan, 48, (2005)85–108.

T. Larsson and M. Patriksson: Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem. Transportation Science, 26(1), (1992)4–17.

M. Jaggi: Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. Proceedings of the 30th International Conference on Machine Learning, PMLR, 28(1), (2013)427–435.