Section 1.1 Players and Strategies¶
In this book most of the games will be played by two players. Each player must decide how he or she will play the game. In order to study games mathematically, we need to make some assumptions about how the players should play the game. This allows us to be able to better predict what our players should do. The following example illustrates the characteristics we will assume about our players.
Subsection 1.1.1 Example: Cake Division¶
How can two children fairly divide a cake? One classic solution is to have one child cut the cake and have the other child choose a piece.
Why does this work? In other words, why should both children feel they received a fair share of the cake?
What are the underlying assumptions that make this process work?
The goal of each player is to get the largest piece. We can think of this as each player acting in his or her self-interest.
Both players know that the other player has the same goal, and will act to further this goal. Thus, we know that each player is rational. Even more, each player knows the other player is rational.
We need both (1) and (2) to reach the solution that the cake is divided evenly and both children receive equal sized pieces.
The idea that players are self-interested is crucial to game theory. There are lots of other ways to play games, and those might be worth exploring. But to get started with game theory, we must make specific assumptions and develop the mathematical context from these assumptions.
Assumption 1: Players are self-interested. The goal is to win the most or lose the least. But what does it mean to win?
A player's payoff is the amount (points, money, or anything a player values) a player receives for a particular outcome of a game. We say that the player's goal is to maximize his or her payoff. We should note that the maximum payoff for a player might even be negative, in which case the player wants the least negative (or closest to 0) payoff.
It is important to recognize the difference between having the goal of maximizing the payoff and having the goal of simply winning. Here are some examples.
If two players were racing, a player wouldn't just want to finish first, she would want to finish by as large a margin as possible.
If two teams were playing basketball, the team wouldn't want to just have the higher score, they would want to win by the largest number of points. In other words, a team would prefer to win by 10 points rather than by 1 point.
In an election poll, a candidate doesn't just want to be ahead of her opponent, she wants lead by as large a margin as possible, (especially if she needs to account for error in the polls).
It is important to keep in mind the the goal of each player is to win the most (or lose the least). It will be tempting to look for strategies which simply assure a player of a positive payoff, but we need to make sure a player can't do even better with a different strategy.
Assumption 2: Players are perfectly logical. A Player will always take into account all available information and make the decision which maximizes his payoff. This includes knowing that his opponent is also making the best decision for herself. For example, in the cake cutting game a player wouldn't cut one large piece hoping that his opponent will by chance pick the smaller piece. A player must assume that her opponent will always choose the larger piece.
Now you may be wondering what these assumptions have to do with reality. After all, no one's perfect. But we often study ideal situations (especially in math!). For example, you've all studied geometry. Can anyone here draw a perfectly straight line? Yet, you've all studied such an object!
Our Goal: Develop strategies for our perfectly logical, self-interested players.
Subsection 1.1.2 Developing Strategies: Tic Tac Toe¶
Exercise 1.1.1. Play the game.
Play several games of Tic TacToe with an opponent. Make sure you take turns being the first player and the second player. Develop a strategy for winning Tic Tac Toe. You may have a different strategy for the first player and for the second player. Be as specific as possible. You may need to consider several possibilities which depend on what your opponent does.
Who wins? Player 1 or Player 2?
What must each player do in order to have the best possible outcome?
How did you develop your strategy?
How do you know it will always work?
Let us note some characteristics of Tic Tac Toe.
There are two players.
Players have perfect information. This means each player knows what all of his or her own options are, what all of his or her opponent's options are, and both players know what the outcome of each option is. Additionally, players know that both players have all of this information.
This game has a solution. A solution for a game consists of a strategy for each player and the outcome of the game when each player plays his or her strategy. In Tic Tac Toe, if both players play their best, the game will always end in a tie.
The game is finite. This means the game must end after a finite number of moves of turns. In other words, the game cannot go on forever. A game that is not finite is called infinite. Note, an infinite game may end after a finite number of turns, but there is no maximum number of turns or process to ensure the game ends. In Tic Tac Toe, the game must end after 9 or fewer turns.
Exercise 1.1.2. Perfect information, more examples.
Can you think of another example of a game with perfect information? What is an example of a game that does not have perfect information?
Exercise 1.1.3. Finite and infinite, more examples.
Give some examples of finite games and infinite games.
A strategy for a player is a complete way to play the game regardless of what the other player does.
The choice of what a player does may depend on the opponent, but that choice is predetermined before game play. For example, in the cake cutting game, it doesn't matter which piece the “chooser” will pick, the “cutter” will always cut evenly. Similarly, it doesn't matter how the cutter cuts, the chooser will always pick the largest piece. In Tic Tac Toe, Player 2's strategy should determine his first move no matter what Player 1 plays first. For example, if Player 1 plays the center square, where should Player 2 play? If Player 1 plays a corner, where should Player 2 play?
Exercise 1.1.5. Describe your favorite game.
What is your favorite game?
Give a brief description of the game, including what it means to “win” or “lose” the game.
How many players do you need?
Do the players have perfect information for the game?
Is the game finite or can it go on forever?
Give some possible strategies for the player(s). Note, depending on the game, these strategies may not always result in a definite win, but they should suggest a way to increase a player's chances of winning (or not losing).
We have established a few assumptions and looked at how to describe strategies in some familiar games. Not all games easily fit into the context we will be using throughout this text. But you might keep in mind some of your favorite games and see how well the strategies and solutions can be applied to them. In the next section we develop some useful notation for describing most of the games we will study.