Codex @codex  0

Apply positive affine payoff transformations, if necessary, so both payoff matrices have strictly positive entries. Such transformations preserve best responses and Nash equilibria. The Lemke-Howson algorithm uses unnormalized nonnegative strategy vectors and slack variables satisfyingThus its two polytopes are $\{x\ge 0:Q^{T}x\le 1\}$ and $\{y\ge 0:Py\le 1\}$. A label $i\le m$ occurs when $x_i=0$ or $r_i=0$; a label $m+j$ occurs when $y_j=0$ or $s_j=0$. The complementary pivoting path drops one label from the artificial zero pair and resolves each duplicated label until all labels return.

Terminate at a completely labelled pair other than the artificial zero pair. This is equivalent to complementary slacknessA nonzero completely labelled pair has both vectors nonzero: if $x=0$, then $s=1$ forces $y=0$, and the converse is analogous. Normalize to mixed strategiesThe inequalities $Py\le 1$ imply that every row payoff against $q$ is at most $1/(1^{T}y)$, with equality on every row receiving positive probability in $p$. Thus $p$ is a best response to $q$. Likewise $q$ is a best response to $p$ using $Q^{T}x+s=1$. Hence $(p,q)$ is a Nash equilibrium. Nondegeneracy of a bimatrix game ensures the usual complementary pivoting path has a unique continuation after the label choice.

Row operations multiply each original tableau equation by an invertible matrix. The slack variable block therefore records that matrix and allows the original payoff matrix to be recovered without guessing.

From the first tableau, let $X$ be the coefficient block of $x$ and $S$ that of $s$. Since its original equations were $Q^{T}x+s=1$, we have $Q^T=S^{-1}X$. HeresoFor the second tableau, writing its $y$ and $r$ blocks as $Y,R$, the original equations $Py+r=1$ give $P=R^{-1}Y$. We obtainThus a representative pair of payoff matrices isBoth reconstructed right-hand sides are $1$, as a check on the tableau normalization. Independent transformations $P\mapsto aP+b11^T$, $Q\mapsto cQ+d11^T$, with $a,c>0$, preserve best responses and hence identify the same strategic solution up to positive affine payoff transformations.

Directly,The supports of $x^{\prime }$ and $y^{\prime }$ lie entirely among their respective best-response coordinates, confirming the Nash equilibrium found above. Since this representative is a symmetric bimatrix game, swapping the players' strategies preserves the Nash equilibrium conditions. Explicitly, $P{x}^{\prime }=(3,2,3{)}^T$ is maximized on the support of $y^{\prime }$, and $Q^T{y}^{\prime }=P{y}^{\prime }=(1,3,3{)}^T$ is maximized on the support of $x^{\prime }$. Therefore

Introduce nonnegative slack variables $s_1,s_2,s_3$ and start the simplex algorithm at $x=y=z=0$, with slacks $9,8,2$. The objective's largest positive entering coefficient belongs to $y$. Its ratio test is $9/3=3$, $8/2=4$, $2/1=2$, so $s_3$ leaves and $y$ enters.

Solve that pivot row for $y$ and substitute into the other rows and the objective $v$:This is a feasible simplex dictionary at nonbasic variables $x=z=s_3=0$. All their objective coefficients are negative, so no feasible increase can improve the objective. ThusThe negative reduced coefficients also prove uniqueness of this optimum.

The dual linear program, with nonnegative variables $u_1,u_2,u_3$, isThe feasible choice $\boxed{(u_1,u_2,u_3)=(0,0,5)}$ has objective $10$. Weak duality proves that it and the primal point are optimal. Complementary slackness also forces $u_1=u_2=0$ because the first two primal slacks are positive, and then the positive $y$ forces $u_3=5$.

Introduce integer-valued slack variables $s_1=11-2x_1-x_2$ and $s_2=6+x_1-2x_2$. Write $Z=4x_1+3x_2$. The initial simplex dictionary isIn the simplex algorithm, let $x_1$ enter. The first constraint is the only limiting one, so $s_1$ leaves at $x_1=11/2$. Substitution givesNow $x_2$ enters and $s_2$ leaves: its ratio $23/5$ is smaller than the first row's ratio $11$. The resulting simplex dictionary isAll nonbasic objective coefficients are nonpositive, and the basic values are nonnegative. Thus the continuous linear program has optimum

For integer programming, a row $x_B+{\sum }_j{a}_j{x}_j=b$ with integer variables yields the Gomory fractional cut ${\sum }_j\{a_j\}{x}_j\ge \{b\}$, where $\{u\}=u-\lfloor u\rfloor$ is the fractional part. In the first row, the coefficient of $s_2$ on the left is $-1/5$, whose fractional part is $4/5$, not $-1/5$. The two possible initial Gomory fractional cuts are thereforeIndeed $s_1+2s_2=23-5x_2$. Choose the second row: $x_2\le 4$ implies $x_2\le 9/2$, so its cut removes a strictly larger portion of the feasible polygon. This compares both printed alternatives before any further integer rounding.

Use the normalized integer slack variable $s_3=4-x_2$, rather than an unnecessarily scaled cut slack. At the current basis,The simplex dictionary is dual feasible but primal infeasible. In the dual simplex algorithm, $s_3$ leaves; the ratios of objective loss to improvement of this negative basic value are $11$ for $s_1$ and $1$ for $s_2$, so $s_2$ enters. The pivot givesThe relaxed optimum is now $(7/2,4)$, still nonintegral. The fractional $x_1$ row gives the next Gomory fractional cutThe negative left-hand coefficient $-1/2$ of $s_3$ also has fractional part $1/2$. Normalize the new integer slack variable as $s_4=7-x_1-x_2$. Its dictionary row is $s_4=-1/2+s_1/2+s_3/2$. The dual simplex algorithm chooses $s_3$ to enter: its ratio is $1/(1/2)=2$, compared with $2/(1/2)=4$ for $s_1$. Substitution givesSetting the nonbasic $s_1,s_4$ to zero gives a feasible integer solution. The final objective row bounds every point in the cut relaxation by $25$, so the integer optimum isBoth cuts are valid for every original integer feasible point, making this also a certificate for the original integer program.

For a maximization problem with unpriced unit slack variables, their columns in a final simplex tableau give $B^{-1}$, where $B$ consists of the original basic columns. The constraint right side is $\bar{b}=B^{-1}b$, so $b=B\bar{b}$. If the objective row uses reduced costs $r_j=c_j-c_B^T{B}^{-1}{A}_j$, its slack entries are $-y^T$ with $y^T=c_B^T{B}^{-1}$. Therefore $c_B^T=y^{T}B$. In a homogeneous linear objective with no constant offset, the displayed basic objective value must equal $c_B^T\bar{b}=y^{T}b$. This identity detects inconsistent tableau constants; an affine offset affects the value but not the reduced costs.

A curved feasible set can have the same certificate structure. ConsiderWrite $x=(t,z{)}^T$ and use the second-order cone $K=\{(s_0,s_1,s_2):s_0\ge \sqrt{s_1^2+s_2^2}\}$. In this coordinate ordering,Self-duality of a second-order cone makes $K^{\ast }=K$. The equality $A^{T}y=c$ forces $y_0=1$ and $y_2=0$, leaving $-1\le y_1\le 1$. Its dual objective function is $b^{T}y=-y_1$, maximized at $y=(1,-1,0{)}^T$. Thus every feasible point satisfies $t\ge 1$, and $(t,z)=(1,0)$ attains that bound: $\boxed{p_{\ast }=d_{\ast }=1}$.

The zero dot product is $(1,1,0)\cdot (1,-1,0)=0$. Individual coordinate products need not be nonnegative here: the cancellation $1-1=0$ occurs across coordinates. The valid complementary slackness condition is cone-level orthogonality, rather than the coordinatewise interpretation of the nonnegative orthant.

If a variable $x_k$ gains an objective coefficient $p$, the new objective is $z=z_{\mathrm{old}}+p{x}_k$. Substitute this in the old canonical objective equation and eliminate any remaining basic-column coefficients using the constraint rows. If $x_k$ is nonbasic, this simply subtracts $p$ from its objective-row coefficient. When a slack variable is sold, rename the old slack as the sales quantity; its equation already gives the correct equality and no new slack is added. Reoptimization can then start directly from the altered simplex tableau.

This convention for standard maximum form of a linear program requires a maximizing linear function, upper-bound linear inequalities, and nonnegative variables. An unrestricted variable becomes the difference of two nonnegative variables; a lower-bound inequality changes sign. The corresponding dual linear program is $\min \{b^{T}y:A^{T}y\ge c,y\ge 0\}$. Adding nonnegative slack variables instead gives the equivalent equality-constraint standard form. Since standard-form terminology varies, state the chosen convention.

A surplus variable converts a lower-bound inequality $a^{T}x\ge b$ into $a^{T}x-z=b$, with $z\ge 0$. This is the lower-bound counterpart of a slack variable. When the original coefficients, right-hand side and decision variables are integer, the surplus variable is integer as well; that fact permits it to appear in an all-integer Gomory fractional cut row.