Analyze Nash equilibria of 2x2 games 

GitHub repo link: https://github.com/petereso/TwoByTwoNash

Standalone app embedded above: https://petereso.github.io/TwoByTwoNash

Iterated Strict Dominance solver for two-player games

(text by Peter Eso, app written by Thomas Eso)

Fill in the payoff table below or choose a game from the pre-set examples. Then click on the button "Next step" repeatedly for the application to iteratively eliminate each strictly dominated strategy as long as there is such strategy for either player. Note that a pure strategy may be dominated by a mixed one. 

Payoffs are locked when the process is underway; to change them either click on the "lock" button or choose a new example. You may add rows and columns by clicking on the "+" buttons and remove a strategy by clicking on its label. Scroll down for more detail on Iterated Strict Dominance in two-player games.

A two-player strategic game with finitely many strategies for each player is represented by a payoff table just like the one above. Player 1 (blue) chooses row, player 2 (red) chooses column. A player may mix, that is, pick a strategy at random using arbitrary probability weights. The players' independent and simultaneous strategy choices determine the outcome: one payoff for each player. Row's payoff is in the bottom left, column's is in the top right corner of each cell corresponding to a "pure" outcome. If mixed strategies are used, and hence the outcome is random, then a player's payoff is the mathematical expected value of their payoff across multiple cells. That is, payoffs are expressed in utility terms that already incorporate risk attitudes, so a straightforward, probability-weighted average of the payoffs can be used for the payoff of a random outcome.

Naturally, players have to think about the strategy their opponent is likely to choose. A simple observation is that a rational player would never choose a strategy that is strictly dominated. For example, a column is strictly dominated for player 2, if each payoff for player 2 in this column is strictly lower than the corresponding payoff in another column (entry by entry, that is, for all possible strategies of the opponent). It would be irrational for player 2 to play the former strategy as the latter one pays strictly more no matter what  the opponent plays. Knowing that player 2 is rational, player 1 would also eliminate this column from consideration. It is important that only strictly dominated strategies are eliminated by appealing to the opponent's rationality. 

If both players are rational, both know that the opponent is rational, both know that both know this fact, and so on, then strictly dominated strategies can and should be iteratively eliminated in as many rounds as possible. Note that a strategy may be strictly dominated by a mixed strategy of the same player, and that eliminating one player's strictly dominated strategies may enable us to eliminate additional strictly dominated strategies for the other player. The order of elimination does not matter for the set of remaining strategies at the end of the iteration. This procedure is called the Iterated Elimination of Strictly Dominated Strategies (IESDS), or Iterated Strict Dominance (ISD). It reduces the players' strategy sets assuming common knowledge of rationality; the remaining strategies are called rationalizable.

This application uses the following algorithm to check whether a given strategy, say, column "b" for player 2, is strictly dominated. Without loss of generality, assume that all payoffs are positive. (Increasing, linear or affine transformations of the payoffs do not change the game as long as payoffs are in expected utility terms, as assumed.) Assign non-negative weights to all columns; call this vector p. It represents a mixed strategy if p's coordinates add up to 1. Consider player 2's payoffs in matrix U; vector b (player 2's possible payoffs when playing strategy b) is one of its columns. Then solve the following Linear Program: minimize 1.p (the sum of the coordinates of vector p) subject to the constraint Up >= b. (This is in matrix notation; p is written as a column vector here so that it is compatible with matrix U for the purposes of multiplication.) The latter inequality system simply means that the p-weighted linear combination of player 2's strategies weakly dominates pure strategy b. The condition is trivially satisfied by vector p that puts unit weight on column b and zero weight on all other strategies. If, in the optimal solution (as the sum of p's coordinates is minimized), the weights add up to strictly less than 1, then column b is strictly dominated. To see this, put all the "missing" weight on any strategy other than b, and due to the fact that all payoffs are strictly positive, the resulting mixed strategy strictly dominates b. 

The algorithm repeats the above step as long as there is a pure strategy dominated by some pure or mixed strategy for either player. Each step (a possible way to dominate a strictly dominated strategy, there might be others) as well as the conclusion of the iteration are reported by the application under "Outputs".

GitHub repo link: https://github.com/tb0wen/isd

Standalone app embedded above: https://tb0wen.github.io/isd