A probability distribution over joint action profiles implements a convex combination of their two-player payoff vectors. The attainable expected payoffs form the convex hull of the pure joint payoffs. The distribution need not factor into independent mixed strategies, and a freely enforceable lottery need not satisfy the incentive constraints of a Nash equilibrium.
Enumerate pairs of strategy supports, solve the equations making each supported action indifferent, then check strict positivity of supported probabilities and all omitted-action payoff inequalities. These conditions suffice for a Nash equilibrium. Under nondegeneracy of a bimatrix game, only pairs of equal support size need be tested.
A square bimatrix game is symmetric when exchanging players exchanges their payoffs: its payoff matrices are with . If is a Nash equilibrium, then is also a Nash equilibrium. A symmetric bimatrix game can still have asymmetric equilibria, so the two strategy vectors must be kept separate in the Lemke-Howson algorithm.
A bimatrix game is nondegenerate if every mixed strategy with positive coordinates has at most pure best responses for the other player. This condition prevents ties in the leaving-variable choice along the usual Lemke-Howson algorithm path and allows unique continuation once the dropped label has been selected.
A Nash equilibrium is a strategy profile in which no player can increase their expected payoff by changing only their own strategy.
A finite nondegenerate bimatrix game has a finite odd number of Nash equilibria. After shifting to positive payoffs, fully labelled vertex pairs in the bounded best-response polytopes correspond to equilibria plus one artificial zero pair. Dropping a fixed label gives a finite path graph whose endpoints are exactly these pairs. The number of endpoints is even, leaving an odd number of genuine equilibria. This is the endpoint-parity argument underlying the Lemke-Howson algorithm.
A symmetric equilibrium of a symmetric game has every player use the same strategy or the same distribution of strategies. Symmetry between players does not require identical behavior across contests with different prizes.
In a nondegenerate symmetric bimatrix game, player interchange pairs every nonsymmetric Nash equilibrium with a distinct swapped equilibrium. The equilibrium oddness theorem gives an odd total; the remaining fixed points, which are the symmetric equilibria, therefore also number an odd amount.
The continuous gain map takes a probability simplex to itself. The Brouwer fixed-point theorem supplies a fixed point, whose positive gains would contradict the zero strategy-weighted average payoff excess. Thus all gains vanish, giving a strategy that is a best response to itself. In a symmetric bimatrix game, this produces a symmetric equilibrium.
For a symmetric bimatrix game with payoff matrices , any nonzero satisfying these equations gives the symmetric Nash equilibrium . Every positive coordinate attains the same maximal payoff. This one-vector construction differs from a two-vector Lemke-Howson algorithm path, which can return asymmetric equilibria.
The Lemke-Howson algorithm follows an almost completely labeled path in the product of two best-response polytopes of a bimatrix game. Drop one label at the artificial zero pair, then alternately pivot away the duplicated label until the dropped label returns. A nonzero completely labeled endpoint, after normalization, gives a Nash equilibrium. The two players' vectors must be kept separate even in a symmetric game.
Complementary pivoting follows adjacent bases while maintaining all but one label of a complementarity system. The Lemke-Howson algorithm for a bimatrix game follows the duplicated label between two tableaux until it restores the dropped label at a nonzero completely labelled pair. Normalization then gives a Nash equilibrium.
Normalize each player's positive pure-strategy payoff improvements to define a continuous self-map of the product of their mixed-strategy simplices. At a Brouwer fixed point every positive improvement must vanish, giving a Nash equilibrium.
Articles by others on the same topic
A bimatrix game is a type of game in game theory that involves two players, each of whom has a finite set of strategies. The outcomes of their choices are represented in the form of a matrix (or two matrices) that captures the payoffs for each combination of strategies chosen by the players. In a bimatrix game, the strategies of the two players can be represented as follows: - Player 1's strategies are represented in one matrix (let's call it Matrix A).
