Klee-Minty cube 2026-10-14
For , these inequalities define a deformed cube with vertices of a polytope. Choose either the lower or upper bound recursively at each coordinate to obtain a vertex of a polytope; changing one choice gives an adjacent vertex of a polytope. When maximizing , smallest-index improving-facet pivoting visits all vertices of a polytope: first traverse the lower last-coordinate face, then move to the upper face and traverse the preceding path in reverse. Thus this geometric version of the Bland pivoting rule can require pivots. Rescaling the coordinate to makes the positive rate per unit freed coordinate equal to ; Dantzig pivot rule then selects the same exponential path. Euclidean edge-length pricing is a different rule.
Encode a vertex of a polytope by three bits: bit records whether the lower or upper bound of coordinate is tight. Every choice is possible because , and the triangular active equations determine that vertex of a polytope uniquely. Its three adjacent vertices of a polytope are obtained by changing one bit. The geometric Bland pivoting rule specified here chooses the smallest-index active facet that can be left while increasing . It produces the following path; the final column records the facet left on arrival at the next vertex of a polytope:
For example, at the origin all three outgoing edges improve the objective, but leaving facet 1 has priority. At bit string , switching bit 2 decreases , so the rule switches bit 1, leaving facet 2. At , neither of the earlier-coordinate switches improves , so the rule finally leaves facet 5. The upper face reverses the direction in which changes of improve , and the remaining three horizontal pivots follow. The objective values in the table are strictly increasing for the stated range of .
Figure 1.
Seven Bland pivots through all eight vertices of the Klee-Minty cube, with epsilon equal to one quarter
. Details.
Thus the simplex method takes seven pivots although the optimum is directly adjacent to the starting point. The same Klee-Minty cube in dimensions has inequalities and vertices of a polytope. On its lower last-coordinate face, increasing means increasing , and the first coordinates follow the corresponding lower-dimensional path before the last-coordinate facet can be left. On the upper face, increasing means decreasing , and the smallest-index rule traverses that path in reverse. The reverse-path assertion follows by the same induction, interchanging maximization and minimization on each face. Hence the pivot count satisfies , , and
The usual Bland pivoting rule prevents cycling, including degenerate pivots, but this exponential example shows that it does not give a polynomial worst-case pivot bound. For rational fixed , the constraints have polynomial encoding length. Arithmetic cost per pivot does not remove the exponential obstruction.
For a lower bound that applies to every pivot choice, use and maximize , starting at the origin. Each edge of this cube changes only one coordinate, whereas the unique optimal vertex of a polytope is . Every coordinate must therefore be changed along at least one edge. Every route of adjacent pivots takes at least pivots, and every strictly improving route takes exactly .
For Dantzig pivot rule, the rate is the objective increase per unit entering nonbasic variable, as in standard reduced cost pricing. Rescale the three coordinates by
The transformed linear program still maximizes , now with bounds
When the active facet for coordinate is freed, the other active equations give . The positive rates per unit are therefore
for , respectively. Equivalently, use the nonnegative lower- and upper-bound slack variables of these displayed, normalized inequalities: freeing coordinate changes its entering slack by . Thus Dantzig pivot rule chooses the lowest coordinate index among improving edges and follows the same seven-pivot path. In dimensions set ; the rates give the same pivots. These statements concern coordinate/slack pricing, not objective increase per unit Euclidean edge length, which defines a different pivot rule.
The equilibrium oddness theorem gives a finite odd number of Nash equilibria in a finite nondegenerate bimatrix game. One way to see the parity is through the endpoint argument underlying the Lemke-Howson algorithm. Add sufficiently large constants to each payoff matrix so all entries are positive; this does not change best responses. Form the bounded convex polytopes
Label an facet by row label and a tight facet by column label ; in , label a tight facet by and by . A completely labelled vertex of a polytope pair has either both vectors zero, or both nonzero and normalizes to a Nash equilibrium. In the latter case the labels express exactly the equilibrium best-response and zero-probability conditions. Nondegeneracy makes each vertex of a polytope have exactly distinct incident labels and each equilibrium correspond to one such pair.
Fix a label to drop and retain all pairs carrying every other label. Include the product-convex polytope edges that retain those labels. At a completely labelled pair there is one possible outgoing edge, obtained by dropping the fixed label. At any other retained vertex of a polytope, that label is missing and one other label is duplicated; dropping either copy gives the two incident edges. Thus this finite graph consists of paths and cycles, with its endpoints precisely the completely labelled pairs. A finite graph has an even number of degree-one vertices. Since one endpoint is the artificial zero pair, the number of genuine equilibrium endpoints is odd. This proves the required equilibrium oddness theorem and finiteness, without claiming that every equilibrium is reached from the zero pair on the same path.
For a symmetric bimatrix game, swapping players maps to . Every nonsymmetric equilibrium lies in a distinct two-element pair; the fixed points of this involution are exactly the symmetric equilibria. Removing even-sized pairs from an odd total leaves an odd number of symmetric equilibria. In the present game, two equilibria form the swapped pair and the remaining one is with . There is exactly one symmetric equilibrium, as required.