Basic terms


A game is determined by its rules. Normally several players take part in a game. A player can be an individual, a company, a group of companies or even a country. In each game situation the player has a choice of different possible actions: He accomplishes a move. A match means that all players in each game situation have completed their moves. A strategy consists of a certain sequence of moves which determines the end of the game. A strategy can be understood as a comprehensive action plan: It gives information about what to do in each game situation. If a player always is going to win with a certain strategy, no matter how the opponent chooses, the player uses a winning strategy.
A strategy set consists of the total number of all possible strategies.

The eleven game

: During the eleven game each player selects a number between 1 and 10 in turns. Move by move these numbers are added.

The first one who reaches the sum of 100 is the loser.

Check: The eleven game as an interactive script.

" The player who knows the ´right solution´ , chooses the following winning strategy:

Set 

          Xi number 1. Player doing move nr i

          Yi number 2. Player doing move nr i

therefore 

          choose Yi = 11 -Xi
.

The sum of all (Xi + Yi) from i = 1 till 9 has the result 99.

The 'knowing' player who starts second can always react to the move of the other player and add up to 11, 22, 33, … till 99 is reached. The first player has to add 1 and loses.

?1 (You will find the answers at the end of this page)
Is it possible for the second player to turn to the winning strategy after some moves?




Last year in Marienbad
(a special kind of take-away game)


In this type of game there are 5 rows of sticks.

The two players take turns in removing sticks out of a row.

                                                                          I 

                                                                         I I 

                                                                        I I I 

                                                                       I I I I 

                                                                      I I I I I

During a turn, they are only allowed to take sticks out of a single row. It does not matter how many sticks they take out of that row. 

The one who (takes the last turn and thereby) takes the last stick, wins.

This game has a winning strategy, too.

The presentation is done in a dual system:

  2^2   2^1   2^0
    1        0       1
    1        0       0 
              1       1
              1       0
                       1

Taking a match out of a row means the following:

-change of no more than one 1 into a 0 or the other way around and that in each column.
-the (decimal) column sum changes by not more than 1.

So the player, who changes all column sums to 0, has won.

Player one incorperates the winning strategy: He creates an even number of 1s in each column. 

Then player 2 must create an odd number of 1s in at least one column.
Check: This game has to be played by two players.

Apollinaris contra Perrier

: Competing on the same market for mineral water Perrier and Apollinaris try to make as much profit as possible with 5000 Euro fix costs.
Both can decide if they take one or two Euro for one bottle. For two Euro they can sell 5000 bottles otherwise 10000 bottles so that they always make 10000 Euro exchange.
If both companies take the same price they divide the exchange otherwise the one with the lower price gets the whole exchange.

! That is a zero-sum game because the exchanges of both companies together are always zero without any importance of how both decide.
The payoffs can be shown in a matrix form. In that matrix there is always a row player and a column player with their possibilities of decision, the strategies of the players. In this game a strategy is one action. For each pair of strategies the matrix illustrates the payoff for the row player. The column player gets the negative value.
Such games are called matrix games.

Apollinaris                                        Perrier

Check: If one strategy is chosen for the row player and the column player the corresponding payoff is shown.

" For this two-person zero-sum game there is one strategy to get to the highest payoff: The minimax strategy.
Each player maximizes the lowest payoff. In this case the lowest payoff for Apollinaris is one Euro no matter which strategies Perrier chooses. For the decision of two Euro the amount is 5000. The same is true for Perrier. Now both players want to reach the highest value. So both decide for one Euro. The chosen strategies are optimal for the players and mean a more attentive behaviour. The consequence is an equilibrium, in which both take one Euro per bottle by zero as payoff . A matrix game with zero as payoff at an equilibrium is called fair. The game Apollinaris contra Perrier is fair. 

Theorem: The maximum of the row minima is less (or smaler) than the minimum of the column maxima. 

?2
Analyse the eleven game in terms of a matrix game! Attention: the strategy set is very big.

Matching pennies


: Both players have to lay down there coins on the table. If both of them show the same side player 1 wins, otherwise player 2.
Payoff matrix of player 1:

Check: Choosing one strategy for each player you get the payoff value.


This zero-sum game has no equilibrium in pure strategies.

?3
Check this statement!

" Usually the game ´matching pennies´ is executed several times in succession. If player 1 knows the strategy of player 2 this player will lose constantly. Player 2 will try to vary his strategy. He can choose his strategy with a certain probability by a random procedure. The opponent cannot find out anymore, which pure strategy the other player uses, because he doesn’t know it either. The same applies to player 1 of course .

! Strategies which are caused by random are known as mixed strategies.
The payoff in mixed strageties:

Player 1 puts 'head' with probability p, according to this 'tail' with probability 1-p follows. Player 2 chooses q for 'head' ( 0 <= p , q <= 1 ).

If you repeat the game about 100 times player 1 will choose strategy ´head´ averagely 100*p and strategy ´head´ 100* ( 1-p ) times.

The payoff of player 1 is calculated in the following way: You have to multiply the payoff value with the correspending probabilities and summarrize all.


Intuitivly you recognize that an equilibrium exists if each player chooses his mixed strategy to ½ with a payoff of zero. A player receives this value as well when the opponent shows ´head´ for example using a pure strategy. The opponent would be rumbled now.

Theorem: For mixed strageties in two-person zero-sum games with finite strategy set there always exists an equilibrium (Theorem by v. Neumann). 

Such a theorem only ensures the existence of an equilibrium.
A equilibrium is found in matrix games by using the method of linear optimizing.

?4
Develop a formula for the payoff.
Here you can analyse the payoff formula.

Tree representations of games, games with complete and incomplete information

! We speak of a game with complete information if every player in each game situation knows about all possible moves of the opponents. Also the player knows the opponent’s strategy set.

For example: Matching pennies, the eleven game, all matrix games.

Games with incomplete information: Most card games (e.g. Poker). You play with hidden cards. A lot of economic conflicts are of that kind!

Possible matches can be illustrated as a tree. Starting from player 1 with his possibilities of moves, represented as edges, the suitable moves from player 2 are illustrated in the arising nodes. At the end of the branch you find the payoffs of the two players. For one match each player chooses an edge without knowledge of the choice of another player!

Tree diagram for matching pennies:

If you try to illustrate the two-person zero- sum game chess by a tree diagram, you will soon reach some limits: 
There are too many possibilities!

Theorem: Each game for n players with finite tree and complete information has at least one equilibrium ( theorem of Kuhn).

Furthermore it is true that each equilibrium has the same payoff.

?5
Chess is exemplified to this theorem. Why the equilibrium payoff isn’t known to day? Is chess a matrix game?

Keep-sell

: The most quoted example of the technical literature is called the prisoners’ dilemma. We have educed an economical equivalent:

There are two players (entrepreneurs) producing the same goods. They are able to produce only in a certain period. At the end of this period they have the choice between keeping and selling their goods later more expensive or to sell them immediately. If one of them sells directly and the other one keeps the good, this one who keeps can’t sell his goods later on, because the market is already saturated by the cheaper products of the other seller.

! Apparently it’s not any longer a zero-sum game. The payoff matrix now consists in pairs of numbers, in which the first component shows the payoff of the row player and the second one the column player’s payoff. The sum of the payoff values for each pair of strategies is not zero any more.
This game is called a nonconstant-sum game!
Despite of their form of representation the nonconstant-sum games cannot exactly be seen as matrix games as defined before.

Folowing table will explain the situation:

Check: Choose row and column strategies.

" If one of the players sells, the payoff of the other player will be 2 if he sells too or 0, if he keeps the goods. In the case that both of them keep the goods, the payoff will be 3 for both of them.
The row player has a higher payoff when he sells independent from the decision of the column player (column player keeps: 4, column player sells: 2).
So he will sell and so does the column player with the same expectation. The strategy 'sell' dominates the strategy 'keep' even though the could get more if they would keep both their goods.
Even if the two players have an agreement, they won’t keep both because each of them can advance his payoff changing the strategy.

! The couple of numbers (2,2) is an equilibrium. It isn’t possible to explain this game with the minimax strategy. An other explanation leads to the aim: Both players choose their optimal strategy and if one of them deviates from his strategy he will detract his payoff. This equilibrium is called: Nash equilibrium.

?6
The equilibrium in the zero-sum game ‘Apollinaris / Perrier‘ is based on the same definition. Prove this sentence.
Is the Nash equilibrium a generalization.

Two aircraft producers: Boeing contra Airbus

Both aircraft producers have the opportunity to come up with a new type of aircraft. Since the development will get too expensive there is no way that both of them make a profit.

payoff matrix:

                                                       Airbus

Check: Choose a row and a column strategy and calculate some payoffs! 

" There are two Nash-equilibria in pure strategies: (100,0) and (100,0).

There is a third equilibrium in mixed strategies:
Boeing enters the market with a probability of p, Airbus chooses the probability q for its strategy
( 0<= p,q <=1).

The probability that Airbus will not enter the market is 1-q.
BOEING’s payoff if AIRBUS ernters the market:
-5q + 100(1 - q) = 100 – 105q
Payoff if Airbus does not enter the market
0q + 0(1 – q) = 0
The payoff is obviously zero. No risk no fun!

If both pure strategies of the producer imply the same payment we have.
0 = 100 – 105q
100 = 105q
q = 100/105


For probability p the same is valid. The mixed strategy at the equilibrium means, that you should enter the market by probability 100/105, stay away by 5/105.
There are no methods to make a rational choice between mixed and pure strategies.

For practical decision making: Because both of the aircraft producers want to rule the market by themselves,
there is no pure strategy for equilibrium. The solution in mixed strategies could lead to a certain coordination. They could try to enter new markets in change. If Airbus makes a high profit at this time, but Boeing loses, then Airbus could rest on its laurels, while Boeing needs the selling success.


BOEING receives a subvention with the value of 10. The government could stay out of this competition. The third possibility for the government is to raise taxes. BOEING would pay 50 % of the profit and would get 50 % of loss. The welfare for the USA is the profit/loss of BOEING minus the subvention and plus the taxes.

The highest payoff that the USA can reach is 100. If the government of the USA chooses the subvention, the strategy ´market entering´ will be dominant for BOEING. Even if both companies will enter the market, BOEING would make a profit of 5. So BOEING enters the market and AIRBUS will stay out because staying out causes a higher payoff.

The equilibrium:
Government: 'subvention'
BOEING: 'market entering'
AIRBUS: 'no market entering'.

The Protection of the ecological game

: The state is interested in the environment not being contaminated. So it decides that now all used cars must have an exhaust gas cleaning device integrated. The price for the device is about 500 €. If a used car is kept running without the device, it creates an estimated damage of 8000 € (this sum the state will be accused). If the state catches a car without the device, the owner has to install it and to pay for the inspection.
Expense to him:

" This is a non constant-sum game, because the sum of the both values in each cell in unequal zero.

In this case there is no pure strategy leading to an equilibrium. If the car owners decide to install the device, the state doesn't inspect leading to car owners decision not to install the device. Now the inspection is profitable for the state. This argumentation circles with no end.

With a mixed stategy the problem can be solved:

Assuming the state checks with the probability p and the owner of the car installs the device with the probability of q. 

First one has to calculate the point the car owners costs are the same no matter whether they install the device or not. If they install the device it definitely creates an expense of 500 € for them. If they don't they have to pay 4000 € with the probability of p. 
The expenses are equal:

500 = 4000p
p = 1/8
p ~ 12.5 %

If the state checks more than 12.5 % of the cars, the car owners have no interest in breaking the law by not installing the device.

We have a Nash-equilibrium.

Excursion:

Excursion 1

You can join this winning strategy later if the other player didn’t adopt this strategy and chooses the numbers randomly.

Excursion 2

All possible choices of numbers in each stage of the game lead to different strategies. The set of strategies is finite but very large. In principle this is a matrix game. The payoffs are 1 (player 1 wins) and –1 (player 2 wins). This game has many equilibria with the payoff 1. Therefor the game is not fair.

Excursion 3

Similarly to the eleven game the set of strategy is finite, but inconceivably large. The complexity of chess keeps the question about a winning strategy undetermined and we don’t know if the value of the game is 0. In principle chess could be a matrix game just like the eleven game.

Excursion 4

You can take every maximum of the row minima and every minimum of the column minima but the payoffs will never be the same.

Excursion 5 

The payoff is calculated this way:
2*p*q + (-2)*p*(1-q) + (-2)(1-p)*q + 2*(1-p)*(1-q)

Excursion 6

Does Apollinaris starts with the strategy '1 euro'. If Apollinaris deflects from this strategy the payoff will be –5000 euro. This can be also applyd for Perrier.

next