The input to the algorithm is a 2-player game . Here, is represented by two game matrices and , containing the payoffs for players 1 and 2 respectively, who have and pure strategies respectively. In the following, one assumes that all payoffs are positive. (By rescaling, any game can be transformed into a strategically equivalent game with positive payoffs.) has two corresponding
polytopes (called the
best-response polytopes) and , in dimensions and dimensions respectively, defined as follows: • is in ; let {{math|1= {
x1,...,
xm} }} denote the coordinates. is defined by inequalities , for all {{math|1=
i ∈ {1,...,
m} }}, and a further inequalities B_{1,j} x_1 + \dots + B_{m,j} x_m \le 1, for all {{math|1=
j ∈ {1,...,
n} }}. • is in ; let {{math|1={
xm+1,...,
xm+
n} }} denote the coordinates. is defined by inequalities , for all {{math|1=
i ∈ {1,...,
n} }}, and a further inequalities A_{i,1} x_{m+1} + \dots + A_{i,n} x_{m + n} \le 1, for all {{math|1=
i ∈ {1,...,
m} }}. Here, represents the set of unnormalized
probability distributions over player 1's pure strategies, such that player 2's expected payoff is at most 1. The first constraints require the probabilities to be non-negative, and the other constraints require each of the pure strategies of player 2 to have an expected payoff of at most 1. has a similar meaning, reversing the roles of the players. Each vertex of is associated with a set of labels from the set {{math|1={1,...,
m +
n} }} as follows. For {{math|1=
i ∈ {1, ...,
m},}} vertex gets the label if at vertex . For {{math|1=
j ∈ {1, ...,
n} }}, vertex gets the label if B_{1,j} x_1 + \dots + B_{m,j} x_m = 1. Assuming that is nondegenerate, each vertex is incident to facets of and has labels. Note that the origin, which is a vertex of , has the labels {{math|1={1, ...,
m} }}. Each vertex of is associated with a set of labels from the set {{math|1={1, ...,
m +
n} }} as follows. For {{math|1=
j ∈ {1, ...,
n} }}, vertex gets the label if at vertex . For {{math|1=
i ∈ {1, ...,
m} }}, vertex gets the label if A_{i,1} x_{m + 1} + \dots + A_{i,n} x_{m + n} = 1. Assuming that is nondegenerate, each vertex is incident to facets of and has labels. Note that the origin, which is a vertex of , has the labels {{math|1={
m + 1, ...,
m +
n} }}. Consider pairs of vertices , , . The pairs of vertices is said to be
completely labeled if the sets associated with and contain all labels {{math|1={1, ...,
m +
n} }}. Note that if and are the origins of and respectively, then is completely labeled. The pairs of vertices is said to be
almost completely labeled (with respect to some missing label ) if the sets associated with and contain all labels in {{math|1={1, ...,
m +
n} }} other than . Note that in this case, there will be a
duplicate label that is associated with both and . A
pivot operation consists of taking some pair and replacing with some vertex adjacent to in , or alternatively replacing with some vertex adjacent to in . This has the effect (in the case that is replaced) of replacing some label of with some other label. The replaced label is said to be
dropped. Given any label of , it is possible to drop that label by moving to a vertex adjacent to that does not contain the
hyperplane associated with that label. The algorithm starts at the completely labeled pair consisting of the pair of origins. An arbitrary label is dropped via a pivot operation, taking us to an almost completely labeled pair . Any almost completely labeled pair admits two pivot operations corresponding to dropping one or other copy of its duplicated label, and each of these operations may result in another almost completely labeled pair, or a completely labeled pair. Eventually, the algorithm finds a completely labeled pair , which is not the origin. corresponds to a pair of unnormalised probability distributions in which every strategy of player 1 either pays that player 1, or pays less than 1 and is played with probability 0 by that player (and a similar observation holds for player 2). Normalizing these values to probability distributions, one has a Nash equilibrium (whose payoffs to the players are the inverses of the normalization factors). ==Properties==