| Name | Description |
|---|---|
| 2x2 Symmetric Games | Games which are both 2x2 and symmetric are interesting to list as their own set because they are a subset of games with evolutionarily stable strategies |
| Acyclic Graph Games | Graphical games for which the graph is acyclic. It is NP-Complete to find if there exists a pure strategy Nash (or Pareto-Nash) equilibrium. |
| Acyclic-Hypergraph Games | A hypergraph of a game is defined as: each player is a vertex each interaction (p U Neigh(p)) is a hyperedge. These are the games where hypergraph is \alpha-acyclic It is NP-Complete to find if there exists a pure strategy Nash (or Pareto-Nash) equilibrium. |
| All payoffs are unique | Games in which the payoff values for each outcome are unique. |
| Anti-Braithwaite Games | Games in which the gains of each player as he shifts from his maximin to his minimax strategy while the co-player stays with the maximin are both negative. |
| Braithwaite Games | Reference given to "Game Theory as a Tool for the Moral Philosopher" by Braithwaite (1955) Games in which the gains of each player as he shifts from his maximin to his minimax strategy while the co-player stays with the maximin are both positive. "Two Musicians" game is an example -- reference given in "Braithwaite's Arbitration Scheme" to pages 145-146 of Luce and Raiffa's "Games and Decisicions." |
| Classical Matrix Game | This is not really a set of games! This game is described as a matrix. It cannot be scaled to different sizes. |
| Compact Representation | Games that can be represented more compactly than with a matrix |
| Complete Opposition | Games in which opponents are diametrically opposed but the payoffs do not necessarily add up to something constant. |
| Constant-Sum Games | Sum of players' payoffs is constant Admit pure strategy solutions if and only if they have a saddle point |
| Dominance-Solvable Equilibrium | Games in which a strategy profile can be found by deleting a (weakly) dominated strategy from the strategy set of one of the players, recalculating to find which remaining strategies are (weakly) dominated, deleting one of them, and continuing the process until only one strategy remains for each player. Also called "Iterated Dominance Equilibrium" |
| Dominant Strategies for All | Games in which all players have dominant strategies |
| Evolutionarily Stable Strategies | Games which have evolutionarily stable strategies. An evolutionarily stable strategy p is a strategy that meets the following 2 conditions: 1. p is an equilibrium strategy, i.e. it is a best response to itself 2. for every alternative best reply r to p, the following inequality holds: E(p, r) > E(r, r) where E is the payoff function Every 2X2 symmetric game has an evolutionarily stable strategy!! But not every 2 player symmetric game with arbitrary numbers of actions (counterexample: rock paper scissors) |
| Force-Vulnerable Games | Defined only on 2x2 games Games in which one player can make a unilateral shift from the "natural outcome" which will effectively force the other player to shift as well in repeated games in order to avoid a low payoff. The "natural outcome" is defined using the following assumptions: 1. If both players have a dominant strategy, both will use it 2. If only one player has a dominant strategy, he will choose it, and the other will choose the strategy which maximizes his payoff under the assuption that the first player has chosen his dominant strategy 3. If the game has a single Pareto eq, the players will choose the strategy which contains it 4. If neither player has a dominating strategy, and if the game has either no pareto eq or more than one, each player will choose the stragy which contains his maximin outcome (i.e. the strategy which avoids the smallest of the four payoffs) TODO: identify and label subsets |
| Geometric Games | "A geometric game is a game having the following form: Two antagonists, known hereafter as RED and BLUE, choose subsets R and B respectively of a set S. BLUE then receives from RED a payoff which is a function of the triple R, B, and R (intersection) B. The payoff need not be monetary, and for our purposes can be considered merely a score which BLUE wishes to maximize and RED wishes to minimize. . . . In general, RED and BLUE may not choose any subset of S, but rather RED must select from a collection R of admissible pure strategies for RED and BLUE from a collection B. . . . The term 'geometric' is described by specifying S, R, B, and the payoff." There are quite a few more games of various detail and extensibility described in this reference. |
| Graphical Games | Games which can be expressed as graphs in a way that is exponentially more efficient than the matrix form representation |
| Improper Braithwaite Games | Games in which the gains of each player as he shifts from his maximin to his minimax strategy while the co-player stays with the maximin are both zero. |
| Intersection of bounded treewidth and small neighbourhood | As the name suggests, (graphical) games that have both bounded treewidth and small neighbourhood properties. |
| k-Bounded Hypertree-width | Games whose hypergraph tree width (see acyclic hypergraph games) is bounded by constant k. |
| k-Bounded Neighbourhood | A set of graphical games, where the degree of each player is bounded by a constant k. It is NP-complete to tell whether there exists a pure-strategy nash (pareto-nash) equilibrium, even when payoffs are given explicitely as tables. |
| k-Bounded Treewidth Games | Graphical games where treewidth of the graph is bounded by a constant k. |
| Mixed-Motive Games | The interests of players partially coincide in that it is possible both may prefer one outcome to another. (Very broad) |
| Neutrally Stable Strategies | Games which have neutral stable strategies. This is a weakening of evolutionarily stable strategies that accounts for games like rock paper scissors that don't meet the criteria for ESS but seem to be stable. An evolutionarily stable strategy p is a strategy that meets the following 2 conditions: 1. p is an equilibrium strategy, i.e. it is a best response to itself 2. for every alternative best reply r to p, the following inequality holds: E(p, r) >= E(r, r) where E is the payoff function <- the >= instead of > here is how this differs from ESS Other weaker variations of ESS exist as well |
| No dominant strategies | Games in which no players have dominant strategies |
| No Pure-Strategy Equilibria | Never has a PSNE Called "cycle games" in "A Taxonomy of 2x2 games" because "if the players pursue short-term gains, the plays will move around the cycle of outcomes." |
| No pure-strategy Nash when N > 3 | No pure-strategy Nash when the number of players is greater than three. |
| Non-Braithwaite Games | Games in which only one of the gains of a player as he shifts from his maximin to his minimax strategy while the co-player stays with the maximin is positive or zero. |
| Ordinally Symmetric Games | "A game that is symmetric when defined in terms of ordinal payoffs" TODO: identify and label more subsets |
| Pareto ordered / Strictly Better Equilibria Exist | Multiple equilibria (may?) exist such that one yields higher (or equal) payoffs for all players than another |
| Polymatrix Games | Payoff for each player is a sum of payoffs in two-player games against a subset of the other players Can be solved very efficiently by Lemke-Howson |
| Preemption Games | Timing games in which the reward goes to the player whose move ends the game. The term preemption game seems to have different meanings in the literature. For example, in "A Taxonomy of 2x2 Games" it is used to mean games with two Pareto equilibria, for example Chicken. This is not the meaning we want to use for it though, as the timing game definition seems more naturally "preemptive." |
| Pure Coordination | Was: common payoff all agents have the same payoffs |
| Pure-strategy equilibrium | Always has a PSNE |
| Separable Games | TODO: See reference to Hamburger 1969 These games can be presented to experimental subjects to bring out psychological aspects, but unsure of what they are |
| Small Neighbourhood | A set of graphical games, with the property: | Neigh(p) | = O( log(||G||) / log( |Act(p)| ) ) Intuitively, both number of neighbours, and number of actions for each player cannot grow too fast. Related notion of intricacy: i(G) = max_{p\in P} ( |Neigh(p)| log|Act(p)| / log ||G|| ) |
| Strict Equilibrium | deviation from equilibrium makes players strictly worse off. |
| Supermodular Games | "Supermodular games are games in which each player's strategy set is partially ordered, the marginal returns to increasing one's strategy rise with increases in the competitors' strategies (so that the game exhibits 'strategic complementarity') and, if a player's strategies are multidimensional, the marginal returns to any one component of the player's strategy rise with increases in the other components." TODO: Determine f these are actually dominance-solvable. Not sure. |
| Symmetric Games (strong sense) | All players have the same actions available to them. If two players exchange actions, their payoffs are also exchanged and everyone else's payoffs remain the same. |
| Symmetric Games (weak sense) | All players have the same actions available to them. If two players exchange actions, everyone else's payoffs remain the same. |
| Threat-Vulnerable Games | Defined only on 2x2 games Games in which the player receiving a lower-than-optimal payoff in the "natural outcome" can shift unilaterally to a lower payoff which may result in the other player shifting as well if the game is repeated. The "natural outcome" is defined using the following assumptions: 1. If both players have a dominant strategy, both will use it 2. If only one player has a dominant strategy, he will choose it, and the other will choose the strategy which maximizes his payoff under the assuption that the first player has chosen his dominant strategy 3. If the game has a single Pareto eq, the players will choose the strategy which contains it 4. If neither player has a dominating strategy, and if the game has either no pareto eq or more than one, each player will choose the stragy which contains his maximin outcome (i.e. the strategy which avoids the smallest of the four payoffs) TODO: Identify and label subsets |
| Timing Game | Games that are based on choosing a time to act. Choosing a time can be thought of as happening in advance, as nothing that players would learn over that time period could help them. |
| Tractable Pure-Strategy Equilibria | Games, for which it's possible to find a pure-strategy NE in polytime (given efficient graphical game representation as input). |
| Trembling Hand Perfect Equilibria Exist | Equilibrium is robust against slight perturbations in the players' *strategies* Other variations on the typical Nash are listed in the first chapter of the Evolutionary Game Theory book. |
| Unique Equilibrium | Game has only one equilibrium |
| Weak Equilibrium | At least one player can deviate from the equilibrium and receive the same payoff. |
| Weakly Dominant Strategies | At least one player has a strategy that weakly dominates his other strategies. |