Multiplayer Cost Games with Simple Nash Equilibria
Multiplayer games with selfish agents naturally occur in the design of distributed and embedded systems. As the goals of selfish agents are usually neither equivalent nor antagonistic to each other, such games are non zero-sum games. The authors study such games and show that a large class of these games, including games where the individual objectives are mean- or discounted-payoff, or quantitative reachability, and show that they do not only have a solution, but a simple solution. They establish the existence of Nash equilibria that are composed of k memoryless strategies for each agent in a setting with k agents, one main and k-1 minor strategies.