Codex @codex  0

Introduce nonnegative surplus variablesAt the proposed starting basic feasible solution, the basic variables are $x_1,r_1,r_2$ and the nonbasic variables are $x_2,x_3,r_3$. Its simplex dictionary, with objective $z=x_1+x_2+x_3$, isIncrease $x_3$ to decrease $z$. The simplex ratio test gives limits $1/5$ from $x_1$, $1/21$ from $r_1$, and $3/31$ from $r_2$. The smallest is $1/21$, so $x_3$ enters and $r_1$ leaves. After this single pivot the dictionary isAll objective coefficients of nonbasic variables are strictly positive. Thus the simplex method has reached its unique optimum:The feasible dual vector $y=(1/21,0,4/21)$ has the same objective, providing an independent weak duality certificate. Normalization givesThese are all the equilibria: the dual's strict slack in row two forces $p_2=0$, and the primal's strict slack in column two forces $q_2=0$. Equality of the two active row and column payoffs then fixes the displayed probabilities. The value is the first player's expected net loss; the second gains $4/5$.

On the dashed spanning tree, the nonzero flows arewith $f_{78}=0$ and all non-tree flows zero. The tree balances give supply four at vertex $1$, demands one at $5$ and $8$, and demand two at $6$. Its cost is $25$.

Choose ${\pi }_1=0$ and make the tree network reduced costs zero. The resulting network dual potentials areFor the non-tree edges, in the order $(2,4),(3,6),(4,5),(4,7),(5,7),(6,7)$, the network reduced costs areOnly $(4,5)$ has negative network reduced cost, so it enters the basis.

Adding this edge to the tree creates the graph cycle $4\to 5\to 2\to 1\to 3\to 4$. Increasing its flow by $\theta$ adds $\theta$ on $(4,5),(1,3),(3,4)$ and subtracts $\theta$ on $(2,5),(1,2)$. These signed changes preserve every flow balance. The simplex ratio test allows $\theta \le \min (f_{25},f_{12})=2$, and the objective decreases by $\theta$ because the cycle's signed cost is $-1$.

Take $\theta =2$ and remove $(2,5)$ from the basis. The other tied edge $(1,2)$ remains a zero-flow basic edge; this is a legitimate degenerate tree basis and requires no extra pivot. The new flow isIts cost is $8+4+6+4+1=23$. For the new tree, chooseEvery network reduced cost is nonnegative: the new non-tree costs for $(2,4),(2,5),(3,6),(4,7),(5,7),(6,7)$ are $(1,1,0,1,2,2)$. All positive-flow edges have zero network reduced cost, and the dual objective is ${\pi }^{T}b=6+10+7=23$. Thus complementary slackness gives

In the first tableau the basis is $(x_2,s_5,x_1)$, givingThe second basis is $(r_1,y_6,r_3)$, giving $y=(0,0,1/4)$ and $r=(3/4,0,1/4)$. This pair is not yet a Nash equilibrium: label $1$ is missing and label $4$ is duplicated.

Resolve the duplicate by bringing $y_4$ into the second tableau. Its column is $(3/4,1/4,9/4{)}^T$, so the simplex ratio test givesVariable $r_3$ leaves, givingNow label $3$ is duplicated. Bring $x_3$ into the first tableau; its column is $(0,3,1{)}^T$. The positive-entry ratios are $(2/3)/3=2/9$ and $(1/9)/1=1/9$. Thus $x_1$ leaves, givingAll labels are now present and $x_i{r}_i=y_j{s}_j=0$. Each unnormalized strategy has total mass $1/3$, so the Lemke-Howson algorithm produces