The Two-Person, Non-Zero-Sum Game

In a two-person game, there are generally both competitive and cooperative elements: the interests of the players are opposed in some aspects and complementary in others.

Let's regard all two-person games as lying in a continuum,with the zero-sum games (totally competitive) at one extreme, and completely cooperative game at the other extreme.

The payoff matrix tells the whole story in zero-sum games. However, in non-zero-sum games, there are many "rules of the game" that markedly affect the character of the game, and these rules must be spelled out before you can talk about the game intelligently.

• Communication. Generally, the more cooperative the game - the more the players' interests coincide - the more significant is the ability to communicate. However, tacit communication (one player unilaterally adopts an apparently inferior strategy to invite another to cooperate) is generally ineffective because it is generally misunderstood or used. Also it is possible to communicate threats.
• The order of play. The game may be far from trivial even when one player learns the opponent's strategy. What's more, the advantage of having this information may turn out to be a disadvantage.
• The effect of imperfect information. It is often to a player's advantage to see that the partner is well informed (including both real or fake messages). Players can gain if they can convince their opponent that they have certain attitudes or capabilities, whether they really have them or not.
  
• The effect of restricting alternatives. Players are sometimes prevented from using some of their strategies. It is one of the paradoxes of non-zero-sum games that this restriction of a player's choice may be turned to that player's advantage. One can strengthen his position by limiting his alternatives.
  
• Threats. A threat is a statement that you will act in a certain way under certain conditions. Unlike restricted alternatives, this self-imposed restriction isn't binding; you can always change your minds. The purpose of a threat is to change someone's behavior. A threat is effective only to the extent that it is plausible. The greater the price the party making the threat must pay to carry it out, the less plausible the threat.
  
• Binding agreements and side payments. The possibility of making binding agreements (agreement made is enforced by the rules) has a strong influence on the character of the game. In some games it is possible for one player to affect the actions of another by offering a "side payment", a payment made "under the table".
  

The Prisoner's Dilemma

Each player has two basic choices: to act "cooperatively" or "uncooperatively". When all the players act cooperatively, each does better than when all of them act uncooperatively. For any fixed strategy (ies) of the other player(s), a player always does better by playing uncooperatively than by playing cooperatively.

If the game is played only once, players have no choice but to act uncooperatively. But when the game is played repeatedly infinitely, the cooperative strategy comes into practice.

For games repeated for a fixed number of trials, players behave the same as the once-off game. They will behave uncooperatively in the last trial, and thus inferring that the second last, and so on should not be played cooperatively.

The assumption of zero-sum game is that the opponent will act rationally. However, in non-zero-sum game, the assumption is that the partner is cooperative. The difference between the assumptions made in the zero-sum and in the non-zero-sum games is even more clear when they fail. In non-zero-sum games, cooperating with a partner who doesn't cooperative with you leads to disaster; in zero-sum games, the worst that can happen when you play minimax is that you lose an opportunity to swindle your opponent.

Utility Theory

A utility function is simply a "quantification" of a person's preferences with respect to certain objects.

Six conditions that guarantee the existence of a Utility Function

If a player's preferences are to be expressed by a utility function, these preferences must be consistent:

• Everything is comparable.
• Preference and indifference are transitive. That is, if A>B and B>C, then A>C.
• A player is indifferent when equivalent prizes are substituted in a lottery.
• A player will always gamble if the odds are good enough.
• The more likely the preferred prize, the better the lottery.
• Players are indifferent to gambling. A player's attitude toward a compound lottery - a lottery in which the prizes may be tickets to other lotteries - is dependent only on the ultimate prizes and the chances of getting them as determined by the laws of probability; the actual gambling mechanism is irrelevant.

It has even been suggested that these conditions should be used as a definition of rationality in decision making.

Restrictions

In reality, it is easy to show that a person cannot consistently prefer the one type of bet to be the other and still satisfy the six conditions necessary for consistency.

Another souce of difficulty is the variation in people's preferences over a period of time.

Experiments have shown that decisions often depend on seemingly irrelevant variables.

Context of a problem can influence decision making. It was found that most subjects made different decisions in two identical or equivalent situations when these situations were discribed in different ways. The general rule was this: pelple who feel they have won something generally try to conserve their winnings by avoiding risks. In an identical situation, the same people who perceive that they have just lost something will take risks they considered unacceptable before, to make themselves whole. Also people are more sensitive to the percentage of changes, but not the absolute changes.

The General Two-Person, Zero-Sum Game

The games in this chapter have no equilibrium points; if you are to win anything like the amount that you should, you must start second-guessing your opponent in earnest.

A strategy that prescribes the selection of a pure strategy by means of random device is called a mixed strategy.

Once a player resorts to randomizing, not only can he/she not lose (on average), no matter how well an opponent plays; he/she will not gain, however badly an opponent plays. The more capable your opponent, then, the more attractive the randomizing procedure.

von Meumann's Minimax Theorem

One can assign to every finite, two-person, zero-sum game a value V: the average amount that player I can expect to win from player II if both players act sensibly. This predicted outcome is plausible, for three reasons:

1. Player I will not settle for anything less than V.
2. Player I can prevented from getting more than V.
3. Since the game is zero-sum, player II is motivated to limit I's average return to V.

We can treat all two-person, zero-sum games as though they had equilibrium points. The only difference between games with actual equilibrium points and those without them is that in one case you can use a pure strategy and obtain the value of the game with certainty, while in the other case you must use a mixed strategy and you obtain the value of the game on average.

Calculating Mixed Strategies

A strategy may be dominated by either a pure strategy or a mixed one.

1. Calculate the maximin and minimax - if they are equal, this is a game with exact equilibrium point(s). Otherwise, go on to step 2.
2. Eliminate all strategies that are dominated.
3. Assign probabilities to each of your strategies so that the outcome of the game will be the same on average whatever your opponent does. Assume your opponent does the same; if the outcome when you use this mixed strategy is the same as the outcome when your opponent uses his/her mixed strategy and if all probabilities are nonnegative, you have solved the game.

If there is a gap between the outcomes or if some of the probabilities are negative, reexamine the games for dominated strategies; if there are none, then this method failed.

For example,

		Your Opponent
		D	E
	A	15	10
	B	6	15
You	C	5	20
	1/5 A and 4/5 C	7	18
	p A and (1-p)C	15*p + 5*(1-p)	10*p + 20*(1-p)

Your strategy B is dominated by the mixed strategy of A and C, such as play A 1/5 of the time and C 4/5 of the time. Then B is eliminated.

Then let's assume that you play A with probability p and C with (1-p), and your opponent plays D with probability r and E with (1-r). We need 15*p + 5*(1-p) = 10*p + 20*(1-p). Therefore, p = 3/4 and the corresponding payoff is 12.5 on average.

By a similar calculation, you find that your opponent should play each of his/her strategies half the time and the payoff is the same 12.5.

Notes

Player I can be stopped from getting any more; moreover, player II is motivated to stop I from getting more. If I chooses another strategy, he/she is gambling. If II also gambles, there is no telling what will happen. The minimax strategies are attractive in that they offer security. The appeal of security is a matter of personal taste.

If should be emphasized that the minimax strategy is essentially defensive, and when you use it, you often eliminate any chance of doing better.

Experimental studies show that people approach minimax strategies by "learning" during the game. They "learned" how to react effectively to the specific behavior of the experimenter, and adopt defensive strategies when meeting clever opponent or aggressive ones to exploit the others.

The weakest part of the theory is undoubtedly the assumption that a player should always act so as to maximize the average payoff. The justification for the assumption is that, in the long run, not only the average return but the actual return will be maximized. This is because any tricks or pure strategy will be recognized and exploited by the opponent. But if a game is played only once, ofter a strategy that maximizes the average return is not desirable, much less compelling.

In summary,

1. Minimax strategy is secure but defensive, thus not always be the choice of people (depends on the level of the opponent).
2. It relies on the concept of average payoff, which implicitly assumes repeated games. For game just goes once, it may not be suitable.
3. The pre-requirement of zero-sum is strict and not always be the truth in real life. For this issue, refer to the next chapter of utility theory.
   

Some Thoughts

1. Do we really need to eliminate dominated strategies? Maybe after solving the maxtrix, their corresponding probability equals to 0.
2. The method may fail. Then what to do next?
3. The definition of payoff matrix may be a sujective process.

The Two-Person, Zero-Sum Game with Equilibrium Points

Zero-sum means the players have diametrically opposed interests.

Two strategies are said to be in equilibrium (they come in pairs, one for each player) if neither player gains by changing strategy unilaterally. The outcome corresponding to this pair of strategies is defined as the equilibrium point, which is considered stable because a player unilaterally picking a new strategy is hurt by the change.

For two-person, zero-sum games, there may be more than one equilibrium point, but it there is, they will all have the same payoff.

How to find the equilibrium point

Theoretic method

If equilibrium points exist, they are easy to find. For a given payoff matrix (A's choice is represented as rows, while B's as columns):

1. Since B would choose a strategy that yields the minimum value of any row A chooses, A should choose a strategy that yields the maximum of these minimum values; this value is called the maximin.
2. Since A would choose a strategy that yields the maximum value of any column B chooses, B should choose the column that minimizes these maximum values; this value is called the minimax.
3. If the minimax equals the maximin, the payoff is an equilibrium point and the corresponding strategies are an equilibrium strategy pair.

When an equilibrium point exists in a two-person, zero-sum game, it is called the solution. The reasons why equilibrium points are considered solutions are:

1. By playing his/her equilibrium strategy, a player will get at least the value of the game.
2. By playing his/her equilibrium strategy, an opponent can stop a player from getting any more than the value of the game.
3. Since the game is zero-sum, a player's opponent is motivated to minimize the player's payoff.

In games with equilibrium points, payoffs that are not associated with either equilibrium strategy have no bearing on the outcome. That is, the change to these values will not change player's strategies.

Simplification with domination

It is often possible to simply a game by eliminating dominated strategies.

Strategy A dominates strategy B if a player's payoff with A is

• always at lease as much as that of B (whatever other players do)
• at lease some of the time actually better than strategy B.

If all strategies but one are dominated for each player, the equilibrium point(s) can be calculated.

If there is no equilibrium point, a mixed strategy is required. Refer to the next chapter.

An Overview

The theory of games is a theory of decision making. While decision makers are trying to manipulate their environment, their environment is trying to manipulate them.