Week 2 Flashcards
Information set
The set of nodes a player could be at given the information it has
Action Taken
Must be the same for all nodes in the information set
2-player game
A game with 2 players, not counting nature
zero sum game
A game with the property that the sum of the pay-offs for all players is 0, at each leaf of the game tree.
For zero sum games you need only report the payoff to player 1 (player 2 will be minus that)
A game of perfect information
All players know which node of the tree they are on. (All of the information sets are of size 1).
Otherwise, it is a game of imperfect information.
A game without chance
A game in which no node in the tree is controlled by nature. Otherwise, it is a game with chance.
Fully specific strategy
For every node associated with player i, a choice of action
Pure strategy
For every node in the subtree defined by the previous actions, a choice of actions
Note: For every node in the same information set, the same action must be taken
This one is the important one for the course
Normal Form representation
Game represented as a table of strategies
Instead of using a tree, a table of strategies is used
For more than 2 players multiple tables are used
Particularly useful for simultaneous play games
Useful for theory and very small games
Extensive form representation
Representing a game using a game tree
Used for realistic-sized games, a tree can be searched much more efficiently than a list.
Don’t need to store the whole of a game tree, versus need to store the whole normal form
Measures of game size
- Number of board positions that can occur in a game
- Number of decision nodes in the game tree. >= Number of board positions
- Number of possible games = number of terminal nodes
- Number of strategies (sum of 2. and 3. since every strategic decision leads to a terminal or non-terminal node)
- Number of pure strategies (produce of number of decisions at node of a given player)
Winning Strategy
ensures a positive playoff for the player whatever other players do
Draw-ensuring strategy
Ensures a payoff of at least zero for the player, whatever the other players do
Important theorem
For every:
- Two-player
- Zero sum
- perfect information
- no chance
game that ends after a finite number of moves, either:
1. Player 1 has a winning move
2. Player 2 has a winning move
3. Player 1 and Player 2 both have strategies which ensure at least a draw
Ultra-weak game solution
Proving which player can force a win, or draw for either without providing the strategy (non-constructive proof)
Weak game solution
Provides the strategy whereby one player can win or either can draw, starting at the beginning of the game
Strong game solution
Providing the strategy which produces perfect player from ANY point in the game, even if mistakes have been made earlier
