Artificial
Intelligence

10.4.1.2 Computing Randomized Strategies

We can use the fact that an agent will only randomize between actions if the actions all have the same utility to the agent (given the strategies of the other agent). This forms a set of constraints that can be solved to give a Nash equilibrium. If these constraints can be solved with numbers in the range (0,1), and the mixed strategies computed for each agent are not dominated by another strategy for the agent, then this strategy profile is a Nash equilibrium.

Recall that a support set is a set of pure strategies that each have non-zero probability in a Nash equilibrium.

Once dominated strategies have been eliminated, we can search over support sets to determine whether the support sets form a Nash equilibrium. Note that, if there are n actions available to an agent, there are 2ⁿ-1 non-empty subsets, and we have to search over combinations of support sets for the various agents. So this is not very feasible unless there are few non-dominated actions or there are Nash equilibria with small support sets. To find simple (in terms of the number of actions in the support set) equilibria, we can search from smaller support sets to larger sets.

Suppose agent i is randomizing between actions a_i¹,...,a_i^k_i in a Nash equilibrium. Let p_i^j be the probability that agent i does action a_i^j. Let σ_-i(p_-i) be the strategies for the other agents as a function of their probabilities. The fact that this is a Nash equilibrium gives the following constraints: p_i^j>0, ∑_j=1^k_ip_i^j=1, and, for all j, j'

utility(a_i^jσ_-i(p_-i),i) = utility(a_i^j'σ_-i(p_-i),i).

We also require that the utility of doing a_i^j is not less than the utility of doing an action outside of the support set. Thus, for all a' ∉{a_i¹,...,a_i^k_i},

utility(a_i^jσ_-i(p_-i),i) ≥ utility(a'σ_-i(p_-i),i).