Routing Algorithm Countermeasures

Introducing the traffic network into graph theory, this article studied human choices while considering the maximum flow, the shortest path, the minimum cost flow based on graph theory. We have made further research in the network on how the human choose their own route in the game. All details are as the following sections:The first part, to begin with the network flow model, we explored the problems of optimal flow and the Nash equilibrium flow and offered an effective algorithm. In the limited capacity network, we could fetch the maximum flow by introducing side-path model, and caught a conclusion that the maximum flow is exit but not unique. Depending on the maximum flow model of the network, we can quickly judge whether the given network flow is a feasible flow or not. When given a feasible network flow stream, we can use the effective algorithm to get optimal flow and Nash equilibrium flow of the feasible flow and prove the problem that the effective algorithm of how to get Nash equilibrium flow is NP-complete problems.The second section, we study the price of anarchy (PoA) in information symmetry and selfish routing network. When the cost of each edge of the network is a linear function, we can get a conclusion that the PoA of the network that the flow is not atoms can not exceed4/3but the PoA is at most2.618when the flow is atoms. PoA impact on network routing largely, it can impact the interests of the players who route the network because they only consider the interests of themselves expect the social costs. At the same time, PoA illustrates that the Nash equilibrium flow is not always the best choice stream to route the network.In section three, due to the optimal flow as the optimal choice of the network to social, however, it would damage the interests of some players in extent. In this section, we study the unfairness of the optimal flow that between many commodities and each commodity. At the same time, we derive a conclusion that the routing cost is at most1of linear function cost of each edge.At the last section, introducing routing between a pair of commodity in a certain city and multi-commodity among many cities to study routing games. To different routing, players choose the best route to themselves based on their own route models under complete information of the traffic. Without considering the cost of the social, players choose the strategy would obtain a Nash equilibrium of routing strategy, which none of the players would change their strategies.