Chapter 1:
Introduction
What's a Game?
Every child understands what a game is.
However, mathematical games, which are the content of this online book
have a slightly different meaning.
Let us describe the ingredients of a mathematical game.
Rules:
Games have strict rules. These rules specify what is allowed and what isn't.
Though many real-world
games allow for creativity of discovering new "moves", new ways to act, those games that
can be analyzed mathematically have a very rigid set of possible moves, usually all of
them known in advance to all involved. But keep in mind---in real world decisions,
you always have one more option than you are aware of!
It's not just a game:
In everyday language, games are characterized by the lack of seriousness.
However, it was the purpose of Game Theory, from its beginning in 1928,
to be useful also to serious situations in economics, politics, business, and others.
Even war can be analyzed by mathematical Game Theory.
Outcome and payoffs: Children (and also many grown-ups)
play for hours just for the fun. In contrast to this, a mathematical game must have an
outcome. Moreover, each such outcome has payoffs
for the different players attached, which may be monetary or may just
express the satisfaction of that outcome for that player.
You want to win money, or at least be declared the winner.
Uncertainty of the Outcome:
Games should have a "thrill" insofar as the outcome cannot be predicted in advance.
Since the rules are usually fixed, this implies that a game must either involve
some randomness or more than one player.
Make decisions: A game where you don't make decisions might be boring,
at least for the mind. Running 100 meter as fast as you can doesn't require mathematical skills,
it just requires fast legs. However, most sport games also involve making decisions,
and can therefore, at least partly be analyzed by Game Theory.
Cheating: Almost every game knows cheating. Cheating means not playing by the rules,
doing something which is not considered a possible move. When your chess opponent is distracted,
you take your queen and put it on a better suited field. Or in poker, you exchange your "8" in your hand
with an Ace in your sleeve. Note that Game Theory doesn't even acknowledge the existence of cheating.
We will learn how to win without cheating.
Game, Play, Move: Some Definitions
The complete set of rules describes a game.
This should be distinguished from a play,
which is a certain instance of the game. In certain situations, called positions,
a player has do make a decision. This decision is called a move
or an action.
This should not be confused with strategies. A strategy is a
plan that tells the player what move to choose in every possible position where the player has
to move.
Rational Behavior is usually assumed for all players.
It means that every player has well-defined preferences, has beliefs about the world
(including the other players) and tries the best to maximize his or her individual payoff.
Moreover, it also means that every player is aware that all other players are trying to
maximize their payoffs, and that they are aware that he or she is trying to maximize his or her,
and that he or she is aware that they are ... and so on.
Classification of Games
Games can be categorized under several categories:
- Number of Players: The most obvious feature of games
is the number of players involved. Usually there should be more than one player.
However, you can play Roulette alone---the casino doesn't count as a player
since it doesn't make any decisions. It takes or gives the money, if necessary.
Most monographs on game theory don't include one-player games, but in this text
I will allow them, provided they contain elements of randomness.
- Simultaneous, sequential, and other games: In a simultaneous
game, each player has only one move, and all these moves are done simultaneously.
In a sequential game, no two players move at the same time, and players may have to move
several times. Obviously there are games that are neither simultaneous nor sequential.
- Randomness: Games may contain some random events
which would influence the outcome of the game. These events are called random moves.
- Perfect information: A sequential game has perfect information
if every player, when about to move, knows all moves
done by the other players and all random moves so far.
- Complete information means that all players know the structure
of the game---the order in which the different players move, all possible moves in each situation,
and the payoffs for the different players for all possible outcomes.
Although these requirements often fail in real-world games, we assume complete information
in most cases, since games of incomplete information are more difficult to analyze..
- Zero-sum Games have the property that for every possible outcome
of the game the sum of the payoffs of all players equals zero.
Then a player can only win, have a positive payoff, if some other loses, has a negative payoff.
Poker and chess are examples of zero-sum games. Real-world games are rarely zero-sum.
- Communication: Sometimes communication between the players is allowed before
the game starts and between the moves, sometimes it is not.
- Cooperative versus non-cooperative games:
Even if communication is allowed,
the real question is whether the results of these negotiations can be enforced.
If not, a player can always move different to what he or she promised in the negotiation.
Then this communication is called "cheap talk".
A cooperative game is one where the results of the negotiations can be
put into a contract, and where there is some institution enforcing these contracts.
Moreover there must be some means of distributing the won payoff between the members
of the coalition after the game.
Class Activity: Play 10 rounds in the following applets
for each one of the games
LisaGame,
Quatro Uno, and
Auction.
In the first two you can play against a (well-playing) computer, but in the third one
the computer only serves as auctioneer and you need to find another human player.
For each game, please tell whether the game is simultaneous, sequential, or other,
whether randomness is involved, whether it has perfect information, and whether it is zero-sum or not.
Discuss also the seemingly obvious question about the number of players in each game,
and give reasons.
Modeling 1: Introduction
Analyzing games like parlor games or casino games, with strictly defined rules and
outcomes, may for some be enough motivation to develop a theory of games. However,
Game Theory aims higher, and did so from the beginning. It promises to provide tools
that can be applied in many real situation, any situation where two or more persons make
decisions influencing each other.
A model is an abstract, in our case mathematical, view of reality.
In our cases, a model is a certain game, which is supposed to yield some insight
into a real-world situation. ...
It is very important that you never confuse the model with reality---in reality there are almost
never totally strict rules, and in reality players almost always have more options than they
thinks, and than is modeled in the model.
In this text we will also try to model some real-world situations by games,
but the approach taken by this text is a very cautious one. Whenever we try a model
for a real-life situation, we will discuss the assumptions of the model and whether or not
the conclusion from the model are relevant in great detail. Whether or not
Game Theory can be useful for life is for each reader to decide.
We will start investigating simultaneous games.
References
Exercises
- In English Auction, an item is auctioned. People increase bets in increments of $10, and
the player giving the highest bet gets the item for that amount of money. Describe reasons
why the auctioneer would be considered a player of the game, or reasons why he or she would not be considered to
be a player. Does the game contain random moves? Is it a zero-sum game or not?
Discuss whether a real-world art auction would have complete information or not.
The auctioneer has a payoff, therefor he may be considered a player. On the other hand,
the auctioneer does not have any move, since noticing bets is a task, but not a decision.
There are no random moves and the game is not zero-sum. Usually the players would not know
what the item is worth to the others, therefore it does not have complete information.
- Consider the casino game Roulette. Would the croupier be considered to be a player or not?
Does the game contain random moves?
Is it zero-sum or not? Can the outcome of roulette be improved if some players form a coalition
and discuss how to play before each round?
The croupier doesn't make any decisions, therefore it is best not to call him a player.
Of course, there are random moves.
If the casino is considered to be a player, then the game is zero-sum, but not otherwise.
Coalitions are useless, since no move of a player influences the payoffs of the other players.
A payoff of a player is only determined by his own choice/bet and the random move.
- Look at the game ROCK-SCISSORS-PAPER. How many players are there?
Is it simultaneous, or sequential, or neither,
and if it is sequential, does it have perfect information?
Usually two players play it. It is simultaneous, and has to be.
Only sequential games can have perfect information.
- For poker, discuss number of players, whether it is sequential or simultaneous,
or neither, and if it is sequential, whether it has perfect information.
Discuss whether there are random moves. Is communication allowed in poker?
There are at least two players. It is sequential with non-perfect information---although everything
the players do is open, the cards (the random moves) are not. I don't think communication
is against the rules, but revealing cards may be.
- Discuss number of players, whether it is sequential or simultaneous, or neither,
and if it is sequential, whether it has perfect information for Black Jack.
Discuss whether there are random moves. Is communication allowed in Black Jack?
It may be best to consider the dealer not as a player, since the dealer doesn't make decisions.
Viewing it this way, Black Jack has at least one player. As poker it is sequential,
but different to poker it also has perfect informations, since all cards are open.
However it has randomness. I don't know whether communication is allowed, but it would not
help much. The players can not cooperate---each one plays alone against the house.
- It's late afternoon and you are sitting in a train traveling along a coastline.
From time to time the train stops in villages, some of them nice, some of them
ugly, but what's important is that you can evaluate the niceness of the village immediately.
Moreover, the benefit of the evening and night spent at that night
depends only on the niceness of the village.
For this reason you want to wait for the nicest village before you leave.
Unfortunately you don't know how many villages are still to come,
and you know nothing about how villages in this country "normally" look like.
What makes things worse is that you are not able to ask anybody,
since you don't speak the language of the country.
You also know that some (unknown) time in the evening the train
will reach its final destination---then you have to stay there whether it is nice or not.
Explain the different features of this game, with emphasis on the informational
issues. How would you play it? Give some reason for your strategy.
(Initially I formulated this example in terms of marriage in a catholic society,
where divorce is impossible, but have been convinced that this is a different game.
Could you give some arguments why?)
Comment on whether we have complete or incomplete information here, and why.
...........
- In this slightly more realistic version of the game above
you know that the train will stop in 10 villages before it reaches its
final destination. How would you play now?
Comment on whether we have complete or incomplete information here, and why.
...