GAMUT Generators
Name Description How to Generate Actions Extensible? Players extensible?
Arms Races Two countries are choosing levels of arms. Payoffs are based on the cost of the level of arms and the relationship between the country's level and the level of the opponent country. Give players some fixed choices for arms levels by parameterizing on upper and lower bounds of choices.

Award payoffs based on the sum of two functions:
- a negative cost function which is a function of your own level of arms, which must be smooth
- a smooth, concave function which is a function of the difference between your own level and your opponent's
Yes No
Battle of the Bismarck Sea Elaborate story designed to introduce interated-dominant eq:

"Set in the South Pacific in 1943. Rear Admiral Kimura has been ordered to transport Japanese troops across the Bismarck Sea to New Guinea, and Admiral Kenney wants to bomb the troop transports. Kimura must choose between a shorter northern route or a longer southern route to New Guinea, and Kenney must decide where to send his planes to look for the Japanese. If Kenney sends his planes to the wrong route he can recall them, but the number of days of bombing is reduced."

May not be any special reason to generate this game instead of other zero-sum games, but including it since it was mentioned seperately.
Generate a payoff matrix

b, -b b, -b
c, -c a, -a

such that a > b > c
No No
Battle of the Sexes Models a situation in which two players wish to coordinate their behavior, but have conflicting interests. For a two-player version, generate a table:

A, B C, C
C, C B, A


C, C B, A
A, B C, C

such that either (C < A < B) or (C < B < A)

Can use the formula in Compound Games to generate version with more players, although not sure how meaningful this would be
No Yes
Bertrand Oligopoly Models situation of two rival firms choosing how to price their competing goods at the same time.

Firm i's utility is given by

(pi)(D(pi)/m) - Ci(D(pi)/m) if firm i is one of the m firms with the lowest price

0 otherwise


Ci(n) is the cost function for producing n goods
D(n) is the demand function, i.e. the number of goods the public will want at price n
m is the number of firms offering the product at the lowest price
pi is the price chosen by firm i
Parameterize on number of players and functions.

At each outcome, assign each player offering the object at the lowest price p a payoff of p*(D(p)/m) - C(D(p)/m) where D is the demand function, C is the cost function, and m is the number of players who offered the object at this price. Assign each other player a payoff of 0.
Yes Yes
Bertrand Oligopoly with Constant Unit Cost and Linear Demand Functions Just as in regular Bertrand Oligopoly, firms each choose a price pi from some range

Firm i's utility is given by

(pi)(D(pi)/m) - Ci(D(pi)/m) if firm i is one of the m firms with the lowest price

0 otherwise


Ci(n) is the cost function for producing n goods
D(n) is the demand function, i.e. the number of goods the public will want at price n
m is the number of firms offering the product at the lowest price
pi is the price chosen by firm I

In the unit cost and linear demand function version, functions are simplified:

Can use a unit cost function Ci(n) = (c)(n) for some c

Can use D(n) = a - n for n <= a and D(n) = 0 for n > a, and assume c < a
Parameterize on players and actions.

Can generate a constant c in order to create cost function, and generate a constant a in order to create demand function, both as shown in the description.

Then set payoff for each player to

(pi)(D(pi)/m) - Ci(D(pi)/m) if firm i is one of the m firms with the lowest price

0 otherwise
Yes Yes
Bidirectional Local-Effect Game Local-effect game, with the restriction that F_{a,a'} = F_{a',a} for all {a,a'}

Has property PSNE if all F are linear
like normal LEG except generate only one function for each pair of edges (a, b) and (b, a) and store at both Yes Yes
Bidirectional Local-Effect Game with all F linear Local-effect game, with the restriction that F_{a,a'} = F_{a',a} for all {a,a'}

Equivalent to potential game, and has PSNE.
Same as bidirectional local-effect game except use only linear functions. Yes Yes
Centipede Game This description doesn't quite meet the game as it is generally pictured, but gives an idea of context: "There is a pile of pounds on the table. X and Y take it in turns to take either one or two coins from the pile, and they keep the coins they take. However, as soon as either of them takes two coins, the game stops, and teh rest of the coins are cleared away. So long as they each take only one coin when their turn comes, the game continues till the pile is exhausted."

"Standard backwards-induction argument concludes that X will take two coins at her first move, thereby ending the game."

Including this game in our generator because it can be treated as a timing game where each player chooses on which move he will take two coins if given the chance up front.
Parameterize on maximum number of turns the players can take if they do not choose to stop.

If X stops the game before Y and does it on his nth turn, he gets 2n-1 and Y gets 2n-2.

If Y stops the game before X and does it on her nth turn, she gets 2n+1 and X gets 2n-2.

If the game continues until the end, the player whose move ends the game on their nth turn gets 1 less than they would have by stopping the game that turn, and the other player gets 1 (or 3?) more than they would have. The final payoffs if the game continues forever seem to vary among different descriptions.
Yes No
Chicken Two players. Each may contribute or not contribute. Each player has preferred outcome of not contributing while opponent contributes, and second preferred outcome of both players contributing.

"Players extensible" version is N-Player Chicken game listed individually.
Generate a matrix with payoffs

b, b c, a
a, c d, d

Where a > b > c > d

Certain variations can also be generated as mentioned in Hawk and Dove. These have more restrictions.

Generating for more than 2 players is under n-player chicken.
No Yes
Collaboration Games Collaboration games are a subset of coordination games.

There is a footnote in Cooper et al. to Thomas Schelling, The Strategy of Conflict, which states that he used the term coordination games to refer to games in which the multiple Nash eq yielded identical payoffs, and also called these "collaboration games."

Since we are using the less restrictive definition of coordination games, we will use collaboration games to refer to these coordination games with all Nash eq yielding equal payoffs.
Generate a payoff matrix for one player (common payoff so all others will be receive the same payoffs) with the highest payoffs down the diagonal all of equal value.

Notice this does not require the game to be symmetric which is not always part of the definition.
Yes Yes
Common Preference Dispersion Games Dispersion game in which n agents independently and simultaneously choose between n actions and the agents prefer only the outcomes in which they all choosen distinct actions. (These outcomes are called maximal dispersion outcomes.) Parameterize on n = number of players = number of actions.

Generate a symmetric game in which the highest payoffs are at those outcomes in which all n players are playing different actions.

Fill in all other payoffs ordered such that a more dispersed outcome with always have a higher payoff for all players than a less dispersed outcome. How dispersed an outcome is can be measured in different ways, for example by calculating entropy or calculating standard deviation.
Yes Yes
Compound Games Symmetric 2x2 games extended to N+1 (by this notation..) players.

Assume the original 2x2 game had choices we will call C (cooperate) and D (defect) and was of the form

R, R S, T
T, S P, P

with no restrictions on the values of P, R, S, and T.

For any player let N be the number of other players in the game, and x be the number of other players who cooperate. Then the payoff function for this player is as follows:

P(C) = Rx + S(N-x)
P(D) = Tx + P(N-x)

T > S > R > P is multi-person Leader
S > T > R > P is multi-person Battle of the Sexes
T > R > S > P is multi-person Chicken
R > T > P > S is multi-person maximizing difference game
Randomly generate values for P, R, S, and T, and also N such that N > 1. Generate payoff functions for each player as

P(C) = Rx + S(N-x)
P(D) = Tx + P(N-x)

where C and D are the player's two action choices
No Yes
Congestion Games Equivalent to potential games


In congestion games, each player picks a subset of available facilities. For each facility the player chooses, he receives a payment based only on the number of players choosing the facility. The payoff for each player is the sum of these payments over all chosen facilities.

Most definitions of congestion games involve (directly or indirectly) four properties (outlined by Voorneveld et al):
P1) exists a finite facilty set
P2) "Independence of irrevelant choices"
P3) "anonymity" (although not necessarily symmetry, players can have different utility functions from each other)
P4) "partial rivalry", i.e. you will never hurt from having someone who has chosen the same facility as you choose something else
Parameterize on the functions to be used (can use one for each player for each facility, or one common function for all players for each facility) and the number of facilities available to choose from.

Set up a mapping between action numbers and subsets of facilities chosen.

At each outcome, calculate the number fo players who chose each facility. Assign payoffs to players as the sum over all facilities chosen by that player of the function for that player/facility given the number of players who chose the facility.
Yes Yes
Contribution Games Games which have three equilibria:
- two asymmetric equilibria in pure strategies
- one symmetric equilibrium in mixed strategy
Generate a payoff matrix

a, w b, x
c, y d, z

such that:
c > a
b > d
x > w
y > z
b > c
y > x
No No
Convergence No description given except payoff matrix. Looks like point is that both players have dominant strategies and converge on their second highest payoffs. Generate payoff matrix for 2 player game

b, b a, d
d, a c, c
No No
Coordination Games According to Cooper at al. they are (symmetric) games "which exhibit multiple Nash eqilibria which are Pareto-rankable"

However, there is a footnote to Thomas Schelling, The Strategy of Conflict, which states that he used the term to refer to games in which the multiple Nash eq yielded identical payoffs. Also called "collaboration games."

We will use the Pareto-optimal def and also make "collaboration games" available


Agents have common payoffs or should coordinate to get their highest payoffs.

In 2x2 games, have three equilibria:
- two symmetric equilibria in pure strategies
- one symmetric equilibrium in mixed strategies
Generate a matrix of payoffs for one player (common payoff so all others receive the same) where all of the highest payoffs occur on the diagonal (but the payoffs on the diagonal may not all be the same)..

Notice this does not require the game to be symmetric, which is not always part of the definition

For two players, can generate a payoff matrix

a, w b, x
c, y d, z

such that
a > c
d > b
w > x
z > y
Yes Yes
Cournot Duopoly Models situation of two rival firms choosing quantity of competing goods to produce at the same time

If Ci is the cost function of firm i and P is an inverse demand function, then when firm 1 produces y1 goods and firm 2 produces y2 goods, the payoffs to firm 1 and firm 2 will be

firm 1 payoff = P(y1 + y2) y1 - C1(y1)

firm 2 payoff = P(y1 + y2) y2 - C2(y2)

Is generally modeled as a two person game in this way, but can be easily extended to more players.
Parameterize on the inverse demand function P and the two cost functions C1 and C2.

If Ci is a cost function for player i and P is the inverse demand function, then for each outcome, if each player j chooses action yj then the payoff for player i is P(y1+y2)yi - Ci(yi).


Could also parameterize on the number of players to make the game extensible, but really it is only studied in the two player case so we will limit it to that.
Yes No
Dangerous Coordination In this game, the NE is a bad prediction because of the huge risk it involves for one of the players. Generate payoff matrix

b, b c, c
d, c a, a

such that a > b > c and a, b, and c are very signicantly larger than d.

For example:

1, 1 -1, -1
-1000, -1 2, 2

Could extend but may not be as interesting anymore.
Yes Yes
Diamond-Type Search Model Some finite number of players N are exert effort in search for trading partners. Any trader's probability of finding another particular trader is proportional to his own effort and the total effort of others. Effort, of course, comes at some cost. Define payoff for each player to be a constant times his own effort times the sum of the efforts of others all minus the cost of his own effort.

Cost should be smooth, convex, and increasing.

Need to think of best way to generate these functions, and also whether the problem would still be supermodular if we gave a fixed number of effort level choices to each player.
Yes Yes
Discoordination Games Is this idea extensible? What would it mean for more actions or more players?

Two player version has single equilibrium in mixed strategies.
Generate a matrix

a, w b, x
c, y d, z

such that either:
a > c
d > b
x > w
y > z

c > a
b > d
w > x
z > y
No No
Dispersion Games Generalization of the anti-coordination game to arbitrary numbers of agents and actions. Agents prefer outcomes in which the agents are maximally dispersed over the set of all actions. May want to generate separately common preference dispersion games, selfish dispersion games, and partial dispersion games since the payoff structure is very different in all three.

Roughly speaking, fill in all payoffs ordered such that a more dispersed outcome with always have a higher payoff for all players than a less dispersed outcome. How dispersed an outcome is can be measured in different ways, for example by calculating entropy or calculating standard deviation.
Yes Yes
Drilling for Oil Players are two oil firms which own similar tracts of land which may or may not bear oil. Each firm is given a signal at time 0 with some information about the common value v of the land. Drilling costs are c, and the discount factor for waiting for the other firm to drill before drilling is d.

If one firm drills at time 0 then the other can condition whether or not it will drill on the results.

Game ends immediately if neither firm drills at time 0.
Payoff function based on v, c, and d can be set up as a triple integral as detailed in the Milgroms and Roberts paper.

One possible idea for getting this into normal form:
each player has options of "drill immediately" "drill conditioned on whether other player drills immediately" and "do not drill at all" from the start and payoffs are calculated for each combination of these choices according to who would end up drilling and the function given.

Could make a standard function and parametrize on c, v, and d perhaps.
No No
Exponential Game (-2^b, 2^b+1) (0,0)
(0,0) (2,-1)

Interesting in repeated setting
Needs exponential size DFS for NE strategies, but poly-size counting FA
Parametrize by exponential parameter b, generate 2x2 matrix:

(-2^b, 2^b+1) (0,0)
(0,0) (2,-1)
No No
First price auctions formulated as strategic games Each player has a valuation for winning the auction. Payoffs are the valuation - the highest bid for the player whose bid is the highest and 0 for all other players. Discretize amounts that can be bid. Assign each player a valuation for winning the auction. At each outcome, the payoff to the player whose bid/action is the highest is (his valuation - his bid) and the payoff to all other players is 0. Yes Yes
Friends Seems to be a generalization of the battle of the sexes to 5 players.
Not completely clear, but just might be extensible to more.
See the paper, page 14. Description is too complex to type here. (5 players, 2 actions - many entries) No No
Grab the Dollar Time is discrete, if one player grabs dollar first he keeps it, if both grab at once they have to pay a penalty of one dollar each.

Has asymetric eqilibria in pure strategies and symmetric equilibria in mixed strategies.
Paramatrize size with time. Can easily make a payoff matrix where optons are discrerte times and the player decides ahead of time during which time slot he will go for the dollar. Payoffs are a whenever players picks an earlier time slot than opponent, b whenever player picks a later time slot than opponent, and c whenever both pick the same time slot, with a > b > c. Yes Yes
Greedy Game Again, very similar to inspection game.

Let L be a set containing n points, R the collection of all subsets of L containing at most p points, and B the collection of all subsets of L. RED chooses a member of R; BLUE chooses a member of B.

If the intersection of the chosen sets is nonempty, the payoffs are 0.

Otherwise, the payoff to BLUE (from RED) is the size of the set chosen by BLUE.
Similar to simple inspection game except set payoffs differently..

Parametrize on n and p. There will be

(n choose p) +( n choose p-1) + . . . + (n choose 1)

choices for RED and

(n choose n) + (n choose n-1) + . . . + (n choose 1)

choices for BLUE, so the matrix will blow up pretty fast . . .
Yes No
Guess 2/3 of the average All players guess a number between 0 and 100. The one who guesses closest to 2/3 of the total average gets a high payoff, all others get 0.

Only equibrium is for everyone to guess 0.
Associate a number with each action. (Can be 1, 2, 3, . . .) For each outcome, calculate two-thirds the average of the actions chosen by each player and figure out which players have guessed closest to this. Give some payoff amount to the player who has the closest guess (or split this amount between multiple players if there is a tie) and give all other players 0. Yes Yes
Hawk and Dove "Two animals are fighting over some prey. Each can behave like a dove or like a hawk. The best outcome for each animal is that in which it acts like a hawk while the other acts like a dove; the worst outcome is that in which both animals act like hawks. Each animal prefers to be hawkish if its opponent is dovish and dovish if its opponent is hawkish."

Using certain definitions of the values of payoffs under certain restrictions, this game can become Prisoner's Dilemma or Chicken.

Has an evolutionarily stable strategy.
Many different but similar definitions have been given. In fact, even in the Osborne and Rubinstein text alone two definitions are given. The one I am choosing to generate is from the first H+D example given in O+R (since the second definition is just a combination of this def and prisoners dilemmas).

Generate a two person symmetric game with payoff matrix

B, B C, A
A, C D, D

with A > B > C > D
More broad definition:

According to Johansson, can generate the following matrix for a 2-player game:

(R-S)/2, (R-S)/2 0, R
R, 0 (R-F)/2, (R-F)/2

Can also mix up table by swapping order of the actions for either player.

If generated with R > F > S > 0 then have a Prisoner’s Dilemma (or near Prisoner’s Dilemma without second condition met). If R < F then have Chicken Game. Can allow S to be 0 sometimes.
No No
Hero Looks very similar to Battle of the Sexes except with different payoffs in the two least preferred squares.

A "hero" is "one who acts to benefit others as well as himself, but others more than himself" which is the case for either player switching from the (c, c) outsome to (a, b) or (b, a). Both players would rather the other switched, but would rather switch themselves than stay at (c, c).
Generate payoff matrix for two players

c, c a, b
b, a d, d

where a > b > c > d
No No
Hotellings Game Original model is for two players and is cts:
Really this is infinite extensive form - NF might blow up :(
We have consumers drawn uniformly from [0,1] interval.
We have two firms
Each firm first chooses location on [0,1]
The locations x_1 and x_2 are then observed.
They really only consider G(x_1, x_2) - so locations need not count as actions.
Then each firm gets to charge the price p_i
Consumers minimize distance+cost when choosing the firm, so this determines payoff - see paper for details.
This desciptions is probably incomplete:
And still needs to be cross-checked with paper
A game is parameterized by x_1 and x_2 drawn from interval [0,1]
#players = 2
#actions = n
each action is a price p_i \in {1,2,..,n}
(i.e. assume integer prices up to n )
let f(x,p_1,p_2) = argmin_i ( |x-x_i| + p_i /n)
let g_i(x,p_1,p_2) = p_i, if f(x)=i, and 0 otherwise
then payoff_i(p_1,p_2) = integral(g_i(x), x=0..1)
Yes No
Inspection Game - player 1 is an agent with strategies shirk or work
- player 2 is a principal with strategies inspect or not inspect
- working costs g for agent and produces v for principal
- inspecting costs h for principal
- principal must pay agent w unless has evidence that the agent did not work (i.e. agent played shirk and principal played inspect)

- mixed strategy Nash: probability agent shirks is h/w, probability that principal inspects is g/w
For two players, generate a matrix:

0, -H W, -W
W-G, V-H-W W-G, V-W

such that W > G > H > 0. (Might make sense to also make restriction V > W + H but this is not mentioned in the definition of the game.)
No No
Linear Cournot Duopoly A simplification of the cournot duopoly game which has unit costs for producing goods, among other things.

Q1 and Q2 are the quantities produced by each firm respectively. The actions of the game consist of setting these.

a and b are variables having to do with market demand.

c is the cost for producing a unit of the good

The utility of firm i is given by:

ui (Q1, Q2) =
(a - b (Q1 + Q2))Qi - cQi for 0 <= Q1 + Q2 <= a/b
-cQi for a/b < Q1 + Q2
Parameterize a, b, and c, and on the range of choices available to the players for how many goods they can produce.

Calculate utility functions as shown in the description.

Generally I don't think more than 2 players are considered in a Cournot Duopoly game, but it seems like there is no reason we couldn't extend it to more by changing (Q1 + Q2) to (Q1 + Q2 + ... + QN) in the utility function.
Yes Yes
Local-Effect Games - agents choose one node in a graph as their action
- payoff function for choosing action a is:
$$ F_{a,a}(D(a)) + \sum_{a' \in neigh(a)} F_{a',a}(D(a')) $$

- expresses context-specific independence between agent's utility functions.
Parameterize with a graph and functions. Label each node and each edge of the graph with a function.

For each outcome, figure out how many players have chosen each node (where each node represents an action). For each player, calculate the payoff function as the sum of the node function of the action he has chosen evaluated on the number of players who chose this node, and all edge functions for edges leading into this node evaluated on the number of players who chose each neighboring node.
Yes Yes
Location Games Two player version from Hotelling's work:

"The buyers of a commondity will be supposed uniformly distributed along a line of length l, which may be Main Street in a town or a transcontinental railroad. At distances a and b respectively from the two ends of this line are places of business A and B. Each buyer transports his purchases home at a cost c per unit distance. Without effect upon the generality of our conclusions we shall suppose that the cost of production to A and B is zero, and that unit quantity of the commodity is consumed in each unit of time in each unit of length of line."


Multiplayer version from a course in game theory:

"Each of n people chooses whether or not to become a political candidate, and if so which position to take. There is a continuum of citizens, each of whom has a favorite position; the distribution of favorite positions is given by a density function f on [0, 1] with f(x) > 0 for all x in [0,1]. A candidate attracts the votes of those citizens whose favorite positions are closer to his position than to the position of any other candidate; if k candidates choose the same position then each receives the fraction 1/k of the votes that the position attracts. The winner of the competition is the candidate who receives the most votes. Each person prefers to be the unique winning candidate than to tie for first place, prefers to tie for first place than to stay out of the competition, and prefers to stay out of the competition than to enter and lose."
For the two player version, which is probably the more correct version to use:

Parameterize on the length of the line l, the length a of the segment on the far side of A, the length b of the segment on the far side of B, and the transportation cost c.
(a + b < l)

if x is player 1's action and y is player 2's action then the payoff to player 1 is USUALLY:

0.5(l + a - b)x - (x^2)/2c + xy/2c

and likewise the payoff to player 2 is USUALLY:

0.5(l - a - b)y - (y^2)/2c + xy/2

However, if y > x + c(l - a - b) then player 2 will get nothing and player 1 will get all (l * x), and likewise if x > y + c(l - a - b) then player 2 will get all (l * y) and player 1 will get nothing.
(The paper has a minus sign instead of a plus here but that seems to be a typo)

Might want to think about range of prices that players are allowed to choose in order to keep the game interesting

Generate random set of positions which could be of arbitrary size.

Generate a (random?) continuous density function for the distribution of citizens over these positions. We could parametrize the density function based on.. something.

Players each have a fixed number of choices and a fixed ordering of outcomes (a = win uniquely, b = tie for first, c = stay out of competition, and d= finally enter and lose where a > b > c > d) so it should be easy to convert this problem to normal form.
Yes No
Majority Voting - three (or more) players 1, 2, 3 vote on three (or more) candidates A, B, C
- each has utility of 2 for first choice player winning, utility 1 for second choice, utility 0 for third choice, and each (at least in this example) have different orderings of the candidates
Generate n player version of game with m candidates. Can assign each of the n voters a utility for each candidate winning, and create n dimensional matrix where each player has m choices and utility is for each player is based on their utility rating of the candidate with the most votes.

No necessary restrictions on player utilities for each candidate.

Can be parameterized based on both number of voters and number of candidates.
Yes Yes
Matching Pennies "Each of two people chooses either Head or Tail. If the choices differ, person 1 pays person 2 a dollar; if they are the same, person 2 pays person 1 a dollar." Generate the following matrix with any value of A:

A, -A -A, A
-A, A A, -A
No No
Minimum Effort Games Payoff for a player is determined by a formula

a + bM - cE

where E is the player's effort and M is the minimum effort of any player.

Game is interesting when the values of a, b, and c are such that players will gain the most by all cooperating and exerting effort, but will be tempted to exert less effort if they think other players will also.
Generate values for a, b, and c (values used in the paper are a = 60, b = 20, c = 10) such that b > c.

Generate random number of effort levels n and let each player have choices 1, 2, ..., n.

Calculate payoff function using a + bM - cE.
Yes Yes
Modeller's Dilemma Similar to Prisoner's Dilemma except that if both prisoner's deny the charges, there is not enough evidence to convict either.

Will still choose a bad NE, but now because of only weakly dominant strategies.
Generate payoff matrix

a, a c, a
a, c b, b

where a > b > c

Instead of creating a separate generator for this, it might be good to add a parameter to Prisoner's Dilemma for whether or not to allow this with some probability.
No No
Modern Manufacturing This version of the problem is from Rationalizability. . but is based on an earlier version of the problem, also proposed by Milgrom and Roberts.

A team of managers run a firm and adapt to changing technology. They all share a common payoff function f which is also the payoff of the firm and also a supermodular function.

The details as given in this paper are fuzzy. Don't really understand beyond this..

Rationalizability paper doesn't give many details, and Modern Manufacturing paper seems to illustrate a very complicated game.
Yes Yes
Morra "At each play, Ruth and Charlie simultaneously extend either one finger or two fingers and call out a number. The player whose call equals the total number of extended fingers wins that many pennies from the opponent. In the event that neither players' call matches the total, no money changes hands."

Four by four matrix of choices for each player. In the finger story, choose a pair of numbers representing the number of fingers you hold out and the number of fingers you think there will be total. Choices are (1, 2), (1, 3), (2, 3), and (2, 4)

Can also do three finger, four finger, etc.
For two-finger morra, generate 2-player 4 by 4 payoff matrix given as (note this is zero sum so player 2's payoffs can be obtained by subtracting these from 0):

0 c -b 0
-c 0 0 b
b 0 0 -a
0 -b a 0

a > b > c > 0
(in book, a = 4, b = 3, c = 2)

Could probably be extended (three finger morra? More players?) but nobody seems to have been interested in extensions.
No No
Network Games A game over a network, each agent wants to send something from a fixed source to a fixed destination.

Interesting question to ask: the ratio between worst NE and the social optimum.

Examples of latency functions (from roughgarden):
polynomials of degree <= p
M/M/1: (u-x)^(-1)
M/G/1: 1/u + (x (1+s^2u^2))/(2u(u-x))
Pick a graph to represent a network topology. For each link pick a function representing delay (function of the traffic).

Set of pure strategies for each agent is the set of paths from source to destination. Payoff = - delay.
Yes Yes
N-Player Chicken All players choose whether or not to contribute to some lobbying effort. If at least k players contribute, the lobbying effort will be successful.

All players prefer that at least k players contribute than that k-1 or less do.

Each player prefers not to contribute rather than to contribute himself as long as k players are contributing.
Players have two actions called C and N.

Parameterize on the number of players who must contribute (i.e. choose action C) in order for all to get reward.

Payoffs for each player are as follows:

C and k-2 or less others choose C: -c
C and k-1 others choose C: b-c
C and k or more others choose C: b-c

N and k-2 or less choose C: 0
N and k-1 choose C: 0
N and k or more choose C: b
No Yes
N-Player Prisoner’s Dilemma Similar to 2x2 version of prisoner's dilemma but extended to n players and n actions.

"More aptly considered as games of chicken." - Game Theory Topics

"Game Theory and Experimental Games" makes reference to three independent discoveries of this game in 1973: Schelling, Hamburger, and Dawes

It also speaks of three situations which can be modeled as N-Player Prisoner's Dilemma games:
- the invisible hand (page 157)
- conservation of scarce resources (158)
- the tragedy of the commons (159)
Let C(i) be the payoff if you cooperate and i others cooperate, and let D(i) be the payoff if you defect while i others cooperate. This is considered a PD if
1) D(i) > C(i) for 0 <= i <= n-1
2) D(i+1) > D(i) and also C(i+1) > C(i) for 0 <= i < n-1
3) C(i) > (D(i) + C(i-1)) / 2 for 0 < i <= n-1

in order to make sure these properties hold, can parameterize on three function parameters X, Y, and Z, and use functions
C(i) = Xc + Y
D(i) = Xc + Z
where 0 < Z - Y < X

alternately, can generate as a compound game
Yes Yes
Parallel Network Games Graph consists of m parallel links from source to destination, all with same capacity. (So m = #actions)

Equivalent to scheduling of some sort. See paper for a more precise description.
This is still incomplete:
Given n players, and m actions.
Let n_i(a) = #players choosing action i
set payoff_i(a_i, a_{-i}) = -n_{a_i} * alpha
(i.e. you incur delay according to the number of players using the same link).
This is very similar to dispersion game.
Yes Yes
Partial Dispersion Games Dispersion games in which agents' preferences may allign with either the dispersion ordering or with a set of exogenous preferences.

For example, an "anti-battle-of-the-sexes" scenario in which a man and his ex-wife both wish to attend one of two parties, one of which is more desirable, but bother prefer not to encounter each other
Not sure exactly what qualifies as partial dispersion since the definition is broad.

Could generate a common payoff dispersion game and perturb some of the payoffs.
Yes Yes
Potential Games Games having a potential function (a mapping from action vectors to real numbers), with the property that the difference between the potential function values for action vectors X and Y that differ only in the action choices of a single agent is equal to that agent's change in utility from the corresponding change in action.

A pure strategy Nash equilibrium of a potential game always exists and is very easy to compute: any strategy vector that maximizes the potential function.

Potential games are equivalent to congestion games. Note that congestion games are not symmetric, and neither are potential games: not every player is allowed to deviate to every action.
To generate a payoff matrix from a potential function, start by picking one strategy profile S, and calling its payoff v. Then take x = P(S) - P(S') for every other strategy profile S' that differs from S in only one action, and the gain from deviating from S to S' is -x. Now do all S'' that differ from S' in only one action, and so on until you have explored every strategy profile.

Incidentally, note that all strategy profiles that maximize P are (pure strategy) Nash.
Yes Yes
Prisoner's Dilemma Two prisoners are caught and asked to confess. Each prisoner chooses to cooperate or defect. Defect is the dominant strategy for both players and thus forms an equilibrium, even though it is the only pure out come which is not Pareto optimal.

Extensible version listed under N-Player prisoners' dilemma.
For two person version, generate
R, R S, T
T, S P, P

such that T > R > P > S and R > (S + T) / 2

For generation with more than 2 players see N-Player prisoner's dilemma.
No Yes
Random Games Pick number of players and actions,
fill the matrix with random numbers drawn from some distribution
Used as a benchmark too often to omit.
Create a matrix of the appropriate size for the number of players and actions and fill in payoffs (uniformly) at random. Yes Yes
Ring structured game Graphical game structured as a ring of rings.

In the paper, random payoffs are used with three actions per agent.
Create a random graphical game using a graph structure which is a ring of rings. Yes No
Road Game A graphical game - players along a road, interact with N,E,S,W neighbours only. Payoffs arbitrary - usually Roshambo style. Have also some economically motivated payoff-structure in Koller/vickrey Create a graphical game using the road structured graph and a subgame either random or Rock, Paper, Scissors. Yes Yes
Rock, Paper, Scissors Rock beats scissors, scissors beat paper, paper beats rock.

Generalized matching pennies
Can't really generate dreastically different versions of this. Generate payoff matrix for two players with three choices.

b, b a, c c, a
c, a b, b a, c
a, c c, a b, b

where a > b > c and a + c = b

Generally, a = 1, b = 0, c = -1 in which case is zero-sum.
No No
SAT Games Games resulting from Conitzer/Sandholm SAT reduction.

Games that come from SAT formulae using their reduction! (Might be an idea for a weird continuation-method-based SAT solver). Symmetric, two-player. Has only symmetric equilibria, with each supported action having equal probability, and one default pure-strategy equilibrium.

Interesting to find non-default equilibria only.
Pick any SAT formula and follow the paper.
Set of strategies for both players is
Union(L,V,C,{f}), where L is the set of literals, V - vars, C -clauses, f - a special default action

The payoff matrix contains entries 1,-2,+2, 2-n,
and payoff(f,f)=0

If SAT assignment exists, there is a symmetric NE, with payoff of 1 for both, and uniform distribution over satisfying _literals_
otherwise, (f,f) is a NE with 0 payoff.
Yes No
Second price auctions formulated as strategic game Each player has a valuation for winning the auction. Payoffs are the valuation - the second highest bid for the player whose bid is the highest and 0 for all other players. Discretize amounts that can be bid. Assign each player a valuation for winning the auction. At each outcome, the payoff to the player whose bid/action is the highest is (his valuation - the second highest bid) and the payoff to all other players is 0. Yes Yes
Selfish Dispersion Games Dispersion games in which agents may be selfish, i.e. they may prefer individually to use a resource with the fewest possible other users, regardless of the welfare of the rest of the group.

These are non-common-preference dispersion games.
Generate a game in which all players have the same actions available. Set the highest payoffs for each player to be on the outcomes in which they are sharing their action with the fewest other agents. Set the payoffs of all other outcomes to be lower whenever there is less dispersion.

Dispersion can be measure using entropy, standard deviation, or some other reasonable method.
Yes Yes
Shapley's Game 0,0 5,4 4,5
4,5 0,0 5,4
5,4 4,5 0,0

This game has a unique equilibrium point [(1/3,1/3,1/3),(1/3,1/3,1/3)] yielding the exectation (3,3). Yet, any deviation by a player, followed by a best reply, yields BOTH players more than (3,3).


When I google this, the results I find mainly seem to say that Shapley's Game is a modifed Rock, Paper, Scissors:

0,0 1,0 0,1
0,1 0,0 1,0
1,0 0,1 0,0

We should get a precise def.
Unclear if this is extensible at all No No
Simple Ambush Game Let L be a rectangular lattic of points:

L = { (i, j) : i = 1, 2, ..., n; j = 1, 2, ..., m}

Let F be the collection of all functions f from {1, 2, ..., n} into {1, 2, ..., m}

SAG is a geometric game in which the set B for the blue player is equal to F, and the set R for the red player consists of all subsets of L with no more than k members.

The payoff to blue if blue plays f in B and red plays r in R is <f, r> which is defined as 1 if (i, f(i)) is in R for no i and 0 if (i, f(i)) is in R for some i.

Also listed are: Ambush Game, Lattice Ambush Game, Multiple Ambush Game, Penetration Game

some example stories and scenarios are given too
Parameterize on n and m and k.

"Blue" agent gets to choose a function from the numbers {1,2,...,n} to the numbers {1,2,...,m}.

"Red" agent gets to choose any subset of {1,2,...,n} with no more than k values.

Payoffs as defined in the description.
Yes No
Simple Inspection Game "Let L be a set containing n points, R the collection of all subsets of L containing at most p points, and B the collection of all subsets of L containing at most q points. RED chooses a member of R; BLUE chooses a member of B."

The payoff to BLUE (from RED) is 1 if the intersection of these chosen sets is empty and 0 otherwise.

RED should always choose the largest set possible and BLUE should always choose the smallest set.

Example scenario: Surveillance. "A suspect will transfer envelopes to six different contacts during the cour
se of a day. Two of these envelopes contain industrial secrets and the rest contain legitimate information. Three investigators are available to observe the contacts. Each investigator can monitor one contact. One observed exchange of industrial secrets will suffice to convict the subject." Here n = 6, q = 2, p = 3.
Parametrize on n, p, and q. There will be

(n choose p) + (n choose p-1) + . . . + (n choose 1)

choices for RED and

(n choose q) + (n choose q-1) + . . . + (n choose 1)

choices for BLUE, so the matrix will blow up pretty fast.
Yes No
Simple Point Catcher Game Exactly like Simple Inspection Game except with different payoffs.

Let L be a set containing n points, R the collection of all subsets of L containing at most p points, and B the collection of all subsets of L containing at most q points. RED chooses a member of R; BLUE chooses a member of B.

The payoff to RED (from BLUE) is the number of points in the intersection of these chosen sets.
Just like simple inspection game except set payoffs differently..

Parametrize on n, p, and q. There will be

(n choose p) + (n choose p-1) + . . . + (n choose 1)

choices for RED and

(n choose q) + (n choose q-1) + . . . + (n choose 1)

choices for BLUE, so the matrix will blow up pretty fast.
Yes No
Simplified Poker This book gives a lot of descriptions of ways that you can have a simplified poker game where each of the two players only draws one card which is either high or low. Most of these versions cannot be represented in normal form because there is a nature player involved in determining which of the two has the high card and which has low.

This version is an averaged version of some of the others. Player 1 has 8 pure strategies which are each combinations of the strategies bet, pass and fold if the other player bets, pass and call if the other player bets. Player 2 has 4 pure strategies which are combinations of folding, betting, and calling.
Generate a payoff matrix with 8 choices for player 1 and 4 for player 2. Since this matrix is zero-sum, I will only list the payoffs for player 1 here .. Subtract these from 0 to get the payoffs for player 2:

a a 0 0
a/2 0 b/2 (b-a)/2
a/2 (a-b)/2 b/2 0
a/2 0 -b/2 (-a-b)/2
0 -a 0 -a
0 (-a-b)/2 0 (-a-b)/2
a/2 (a+b)/2 -b/2 0
0 (b-a)/2 0 (b-a)/2
0 0 0 0
No No
Small Pig Another elaborate story designed to illustrate another dominance-solvable game:

"Two pigs are put in a Skinner box with a special panel at one end and a food dispenser at the other. When a pig presses the panel at a utility cost of two units, ten units of food are dispensed. One pig is dominant, and if he gets to the dispenser first, the other pig will only get his leavings, worth one unit. If, instead, the small pig arrives first, he eats four units, and even if they arrive at the same time the small pig gets three units."

NE is dominent pig presses, other pig waits.
Generate a payoff matrix

b, d c, c
a, f e, e

Such that a > b > c > d > e > f

In example in book, uses

5, 1 4, 4
9, -1 0,0
No No
Stag and Hare Two players, both can either hunt stag or hunt hare. If both hunt stag they will catch a stag together, split it, and have a high payoff. If one hunts stag and the other hare, the one hunting stag alone will not be able to catch it and will have a lower payoff, while the one hunting hare will have a reasonably high payoff. If both hunt hare, they will both catch the hare but not as much as if only one of them hunted hare.

Two (unique?) NE are (stag, stag) and (hare, hare).
Generate a payoff matrix

a, a d, b
b, d c, c

where a > b > c > d
No No
Traveler's Dilemma "Each person must claim a money amount, and the payment is the minimum of the claims, plus a (possibly small) payment incentive to be the low claimant. Both would be better off making identical high claims, but each has an incentive to 'undercut' the other to obtain the reward for having the lower claim."

Introduced by Basu in 1994
Another reference given to Capra et al. 1999

All of chapter 12 is devoted to travelor's dilemma in Recipes for Interactive Learning, lots of empirical results and such


Similar to centipede game in a matrix form.
The only thing that survives dominance elimination is the outcome that nobody likes. Thus, it's easy to find Nash, there is a question of whether a different solution is appropriate.
Generate a range of discrete dollar amounts that the players can choose to claim. Payoff is the minimum amount claimed by any player, plus a small amount for the player with the lowest claim, possibly minus a small amount for other players. Yes Yes
Tree Structured Game Games which can be expressed efficiently as trees.. Generate a random graphical game using a tree structure as the underlying graph. Yes Yes
Unbalanced Game A 2X2 2-player repeated game, exhibiting interesting equilibrium
(0,-1) (0.5, -1)
A single game, fully specified, see description No No
Uniform Local-Effect Game Regular LEG with restriction that F_{a,a'} = F_{a,a''} for all a,a',a''. Generate as other LEGs, but with only one function per node stored at all outgoing edges (or can store at node and have a different function to calculate the payoff). Yes Yes
Uniform Local-Effect Game with clique Regular LEG with restriction that F_{a,a'} = F_{a,a''} for all a,a',a''.

Equivalent to congestion game, and has PSNE.
Generate in same manner as the uniform local-effect game except with F_{a,a'} = F_{a,a''} for all a,a',a'' Yes Yes
War of attrition Two players are involved in a disbute over an object. The value of the object to player i is vi > 0. Time is modeled as a continuous variable (although I don't see why we couldn't model is as a discrete variable to make life simpler) starting at 0. Each player chooses when to concede the object to the other player. If the first player to concede does so at time t, the other player receives the object at that time. If both concede simultaneously the object is split between them and each receives payoff vi / 2.

One unit of utility is subtracted from the payoff of both players for every unit of time that goes by.

Has property that all NE involve one of the players conceding immediately.
Discretize time into some finite number of times steps equal to the number of actions. Generate random valuations v1 and v2 for each of the two players and random payoff units for each player which are subtracted from the players' utilities at each time step. Yes No
Weak Dispersion Games A common preference game in which the set of all maximal outcomes is a subset of the maximal dispersion outcomes (i.e. the outcomes in which no player can move to another action such that this new action will have less players choosing it) Generate a symmetric n-player game. Randomly choose a highest payoff value and place this payoff in some subset of the maximal dispersion outcomes. Set all other outcomes to have lower payoffs. Yes Yes
Welfare Game Government wishes to aid a pauper if he searches for work but not otherwise, and a pauper searches for work only if he cannot receive government aid. Generate payoff matrix

a, b e, a
e, c d, d

such that a > b > c > d > e
No No
Zero-Sum Games Sum of all players' payoffs is zero.

Only interesting in the case of two-player games.
Generate (uniformly) random payoffs for each outcome for player 1 and then negate these to obtain the payoffs for player 2. Yes No