Week 2

Question 1

Information set

Answer 1

The set of nodes a player could be at given the information it has

Question 2

Action Taken

Answer 2

Must be the same for all nodes in the information set

Question 3

2-player game

Answer 3

A game with 2 players, not counting nature

Question 4

zero sum game

Answer 4

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)

Question 5

A game of perfect information

Answer 5

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.

Question 6

A game without chance

Answer 6

A game in which no node in the tree is controlled by nature. Otherwise, it is a game with chance.

Question 7

Fully specific strategy

Answer 7

For every node associated with player i, a choice of action

Question 8

Pure strategy

Answer 8

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

Question 9

Normal Form representation

Answer 9

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

Question 10

Extensive form representation

Answer 10

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

Question 11

Measures of game size

Answer 11

1. Number of board positions that can occur in a game
2. Number of decision nodes in the game tree. >= Number of board positions
3. Number of possible games = number of terminal nodes
4. Number of strategies (sum of 2. and 3. since every strategic decision leads to a terminal or non-terminal node)
5. Number of pure strategies (produce of number of decisions at node of a given player)

Question 12

Winning Strategy

Answer 12

ensures a positive playoff for the player whatever other players do

Question 13

Draw-ensuring strategy

Answer 13

Ensures a payoff of at least zero for the player, whatever the other players do

Question 14

Important theorem

Answer 14

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

Question 15

Ultra-weak game solution

Answer 15

Proving which player can force a win, or draw for either without providing the strategy (non-constructive proof)

Question 16

Weak game solution

Answer 16

Provides the strategy whereby one player can win or either can draw, starting at the beginning of the game

Question 17

Strong game solution

Answer 17

Providing the strategy which produces perfect player from ANY point in the game, even if mistakes have been made earlier