How to find perfect equilibria in a finite game?

130 Views Asked by At

If we define a game with $n$ persons as below:

(i) for each player $i$, he has his strategy set $S_i$, $|S_i|=m_i<\infty$, and denote $S=\Pi_iS_i$;

(ii) $u_i:S\rightarrow\mathbb{R}$ is a payoff function of player $i$.

Then we define the mixed extension of this finite game to be a game such that

(i) each player $i$ has his mixed strategy set $\Delta S_i=\{(x_1,\cdots,x_{m_i})\in\mathbb{R}^{m_i}|\Sigma_kx_k=1,x_k\geq0\}$, and denote $\Delta S=\Pi_i\Delta S_i$;

(ii) $u_i':\Delta S\rightarrow\mathbb{R}$ is the expected utility function of player $i$.

With a game defined above, one of definitions of perfect equilibria in a finite game is stated below: (i) $\Delta^\circ S_i=\{(x_1,\cdots,x_{m_i})\in\Delta S_i|x_k\gt0,~k=1,\cdots,m_i\}$

(ii) An $\epsilon$-perfect equilibrium is a strategy profile $(\sigma_1,\cdots,\sigma_n)\in\Delta^\circ S_1\times\cdots\times\Delta^\circ S_n$ such that if $u_i(a_i|\sigma_1,\cdots,\sigma_n)\lt u_i(a_i'|\sigma_1,\cdots,\sigma_n)$, then $\sigma_i(a_i)\leq\epsilon$, for all player $i$, and for all strategies $a_i,a_i'\in S_i$. Here, $u_i(a_i|\sigma_1,\cdots,\sigma_n)$ means player $i$'s payoff when using his pure strategy $a_i$ while other player $j$ uses his mixed strategy $\sigma_j$.

(iii) Then a strategy profile $(\sigma_1,\cdots,\sigma_n)\in\Delta S_1\times\cdots\times\Delta S_n$ is called a perfect equilibrium iff there exist some sequences $\{\epsilon_k\}$ and $\{\alpha_k=(\sigma_{k1},\cdots,\sigma_{kn})\}$ such that

(a) each $\epsilon_k>0$ and lim$_{k\rightarrow\infty}\epsilon_k=0$;

(b) each $\alpha_k$ is an $\epsilon_k$-perfect equilibrium;

(c) lim$_{k\rightarrow\infty}\sigma_{ki}=\sigma_i$, $i=1,\cdots,n$.

With a perfect equilibrium defined above(sorry for writing so long above), my question is simple: given a finite game, how do I compute/find the perfect equilibria?

For example: $\begin{array}{c|c|c} & \beta_1 & \beta_2 \\ \hline \alpha_1 & (1,1) & (0,0) \\ \hline \alpha_2 & (0,0) & (0,0) \\ \end{array}$

I know the properties of perfect equilibria such as they are Nash equilibria and exist. But after finding out the set of Nash equilibria, how do I find the perfect ones by finding such sequences $\{\epsilon_k\}$ and $\{\alpha_k\}$ above?