The ideas of Section 9.4.1 easily generalize to any number of players. The main difficulty is that complicated notation makes the concepts appear more difficult. Keep in mind, however, that there are no fundamental differences. A nonzero-sum game with players is formulated as follows.
The Nash equilibrium idea generalizes by requiring that each experiences no regret, given the actions chosen by the other players. Formally, a set of actions is said to be a (deterministic) Nash equilibrium if
For , any of the situations summarized at the end of Section 9.4.1 can occur. There may be no deterministic Nash equilibria or multiple Nash equilibria. The definition of an admissible Nash equilibrium is extended by defining the notion of better over -dimensional cost vectors. Once again, the minimal vectors with respect to the resulting partial ordering are considered admissible (or Pareto optimal). Unfortunately, multiple admissible Nash equilibria may still exist.
It turns out that for any game under Formulation 9.9, there exists a randomized Nash equilibrium. Let denote a randomized strategy for . The expected cost for each can be expressed as
Let denote the space of randomized strategies for . An assignment, , of randomized strategies to all of the players is called a randomized Nash equilibrium if
As might be expected, computing a randomized Nash equilibrium for is even more challenging than for . The method of Example 9.20 can be generalized to -player games; however, the expressions become even more complicated. There are equations, each of which appears linear if the randomized strategies are fixed for the other players. The result is a collection of -degree polynomials over which optimization problems must be solved simultaneously.
Now some costs will be defined. For convenience, let
There are two deterministic Nash equilibria, which yield the costs
and . These can be verified using
(9.79). Each player is satisfied with the outcome given
the actions chosen by the other players. Unfortunately, both Nash
equilibria are both admissible. Therefore, some collaboration would
be needed between the players to ensure that no regret will occur.
Steven M LaValle 2012-04-20