Is there a known way to model the traveling salesman problem (TSP) using non-cooperative game theory?
I only found in the internet cooperative game theory. Why there is no work that solves the TSP using game theory? Is it useless?
Please can anyone suggest an answer. Thank you.
TSP is an optimization problem, the decision version is NP-complete. By optimization, we mean searching for the global minimum total length. We can imagine that there is a central operator who can control the whole stuff.
However, in game theory, usually, it uses different criteria to measure, for example, Nash Equilibrium, it needs to consider the corresponding strategy of the opposite players, as the outcome replies on the interactive behaviors of each players. Thus, you can see, each player can be seen as an operator. It has many local considerations, which may not lead to global optimum. Actually, usually it is not. But we can use some concepts to measure the how far is it from the global optimum in Nash Equilibrium, such as Price of Anarchy, Price of Stability.
Sure, you can also assume each node as a player in the game, design game mechanism and strategy space for each player, then look at the global behavior in equilibrium state. However, it has been different than the original TSP problem.
