Game Theory-Two person Zero Sum game, Algebraic method

Game theory describes the situations involving conflict in which the payoff is affected by the actions and counter-actions of intelligent opponents. Two-person zero-sum games play a central role in the development of the theory of games.

Game theory is indeed about modeling for winning business in a competitive environment: For example, in winning a large bid, there are factors that are important. These factors include: Establishing and maintaining a preferred supplier position, developing a relationship of trust with the customer, the offering itself, and the price.

In order to develop the game theory concepts, consider the following game in which player I has two choices from which to select, and player II has three alternatives for each choice of player I. The payoff matrix T is given below:

In the payoff matrix, the two rows (i = 1, 2) represent the two possible strategies that player I can employ, and the three columns (j = 1, 2, 3) represent the three possible strategies that player II can employ. The payoff matrix is oriented to player I, meaning that a positive tij is a gain for player I and a loss for player II, and a negative tij is a gain for player II and a loss for player I. For example, if player I uses strategy 2 and player II uses strategy 1, player I receives t21 = 2 units and player II thus loses 2 units. Clearly, in our example player II always loses; however, the objective is to minimize the payoff to player I.

Graphical representation of the games may be viewed as a Tournament game played on a directed network. In this setting, there are two kinds of nodes: terminating and continuing. Terminating nodes lead to no other node, and player I receives the payoff associated with his/her own arcs. Continuing nodes lead to at least one additional node. The two players simultaneously choose one node each. For the numerical example, the corresponding graph is given in the figure below. In this directed network the edge goes from vertex u to vertex w, and if one player chooses w while the other chooses u, the player who selects w, which is at the head of arc connecting the two nodes, receives payoff tuw

An "equilibrium decision point", that is a "saddle point", also known as a "minimax point", represents a decision by two players upon which neither can improve by unilaterally departing from it.

When there is no saddle point, one must choose the strategy randomly. This is the idea behind a mixed strategy. A mixed strategy for a player is defined as a probability distribution on the set of the pure strategies. Our numerical example is such a case. Player I can assure the payoff to be maxi minj tij = 2, while player II plays in such a manner that player I receives no more than min max tij = 3. The problem of how the difference [minj maxi tij] - [max min tij] ³ 0 should be subdivided between the players thus remains open. In such cases, the players naturally seek additional strategic opportunities to assure themselves of the largest possible share of this difference. To achieve this objective, they must select their strategies randomly to confuse each other.

We will use a general method based on a linear programming (LP) formulation. This equivalency of games and LP may be surprising, since a LP problem involves just one decision-maker, but it should be noted that with each LP problem there is an associated problem called the dual LP. The optimal values of the objective functions of the two LPs are equal, corresponding to the value of the game. When solving LP by simplex-type methods, the optimal solution of the dual problem also appears as part of the final tableau. So we get v, Y*, and X* by solving one LP. LP formulation and the simplex method is the fastest, most practical, and most useful method for solving games with a large matrix T. Suppose that player II is permitted to adopt mixed strategies, but player I is allowed to use only pure strategies. What mixed strategies Y = (y1, y2, y3) should player II adopt to minimize the maximum expected payoff v? A moment's thought shows that player II must solve the following problem:

			   Min v = y
subject to: 		T.Y £ y
					Ut.Y = 1

The minimization is over all elements of the decision vector Y ³ 0, the scalar y is unrestricted in sign, and U is an n- dimensional column vector with all elements equal to one. The left hand side of the first n constraints, by definition, is player II's expected return against player I's pure strategies. It turns out that these mixed strategies are still optimal if we allow player I to employ mixed strategies. Mixed strategies are also known as "saddle point" strategies. Of course, a game with a saddle point can be solved by this method as well. The standard formulation in the simplex method requires that all variables be non-negative. To achieve this condition one may substitute the difference of two new variables for y.

The optimal strategy for player I is the solution to the dual problem of player II's problem. The simplex method of linear programming provides optimal strategies for both players.

The social games and fairness norm is a convention that evolved to coordinate behavior on an equilibrium of a society's Game of Life. According to this view, the metaphysics of Emmanuel Kant for the naturalistic approach, and the morality of David Hume could be abandoned.

Numerical Examples The LP formulation for player II's problem in a game with payoff matrix T given above, is:

Min v

subject to:

The optimal solution for player II is: y1 = 1/2, y2 = 1/2, y3 = 0. The shadow prices are the optimal strategies for player I. Therefore, the mixed saddle point is: x1 = 1/4, x2 = 3/4; y1 = 1/2, y2 = 1/2, y3 = 0, and the value of the game equals 5/2. Note that the essential strategies for Player I are i = 1, i = 2; for Player II they are j = 1, j = 2 while j = 3 is non-essential.

It is customary to discard the dominant rows or columns in finding optimal strategies. This assumes, however, that the payoff matrix is fixed. If you are interested in the stability analysis of the essential (and non-essential) strategies with respect to changes in payoffs, read the following article:

Investment Decisions: Optimal Portfolio Selections
Consider the following investment problem discussed in the Decision Analysis site. The problem is to decide what action or a combination of actions to take among three possible courses of action with the given rates of return as shown in the body of the following table.

In decision analysis, the decision-maker has to select at least and at most one option from all possible options. This certainly limits its scope and its applications. You have already learned both decision analysis and linear programming. Now is the time to use the game theory concepts to link together these two seemingly different types of models to widen their scopes in solving more realistic decision-making problems. The investment problem can be formulated as if the investor is playing a game against nature.

Suppose our investor has $100,000 to allocate among the three possible investments with the unknown amounts Y1, Y2, Y3, respectively. That is,

Y1 + Y2 + Y3 = 100,000

Notice that this condition is equivalent to the total probability condition for player I in the Game Theory.

Under these conditions, the returns are:

The objective is that the smallest return (let us denote it by v value) be as large as possible.

Formulating this Decision Analysis problem as a Linear Programming problem, we have:

Max v

Subject to:

and Y1, Y2, Y3 ³ 0, while v is unrestricted in sign (could have negative return).

This LP formulation is similar to the problem discussed in the Game Theory section. In fact, the interpretation of this problem is that, in this situation, the investor is playing against nature (the states of economy).

Solving this problem by any LP solution algorithm, the optimal solution is Y1 = 0, Y2 = 0, Y3 = 100,000, and v = $7000. That is, the investor must put all the money in the money market account with the accumulated return of 100,000´1.07 = $10,7000.

Note that the pay-off matrix for this problem has a saddle-point; therefore, as expected, the optimal strategy is a pure strategy. In other words, we have to invest all our money into one portfolio only.

Buying Gold or Foreign Currencies Investment Decision: As another numerical example, consider the following two investments with the given rate of returns. Given you wish to invest $12,000 over a period of one year, how do you invest for the optimal strategy?

The objective is that the smallest return (let us denote it by X3 value) be as large as possible.

Similar to previous example, formulating this Decision Analysis problem as a Linear Programming problem, we have:

Maximize X3

Subject to:

Again, this LP formulation is similar to the problem discussed in the Game Theory section. In fact, the interpretation of this problem is that, in this situation, the investor is playing against nature (i.e., the states of economy).

Solving this problem by any LP solution algorithm, the optimal solution is a mixed strategy: Buy X1 = $4000 Foreign Currencies and X2= $8000 Gold.

The Investment Problem Under Risk:

The following table shows the risk measurements computed for the Investment Decision Example:

The Risk Assessment columns in the above table indicate that bonds are much less risky than the stocks, while its return is lower. Clearly, deposits are risk free.

Now, an interesting question is: Given all this relevant information, what action do you take? It is all up to you.

Max [v - 0.029Y1 - 0.054Y2 -0Y3]

Subject to:

Solving this Linear Program (LP) model by any computer LP solver, the optimal solution is Y1 = 0, Y2 = 0, Y3 = 100,000, and v = $7000. That is, the investor must put all the money in the money market account with the accumulated return of 100,000´1.07 = $10,7000.

Notice that, for this particular numerical example, it turns out that the different approaches provide the same optimal decision; however one must be careful not to do any generalization at all.

and Y1, Y2, Y3 ³ 0, while v is unrestricted in sign (could have negative return).

Solving this Linear Program (LP) model by any computer LP solver, the optimal solution is Y1 = 0, Y2 = 0, Y3 = 100,000, and v = $7000. That is, the investor must put all the money in the money market account with the accumulated return of 100,000´1.07 = $10,7000.

Notice that, for this particular numerical example, it turns out that the different approaches provide the same optimal decision; however one must be careful not to do any generalization at all.

Note that the above objective function includes the standard deviations to reduce the risk of your decision. However, it is more appropriate to use the covariance matrix instead. Nevertheless the new objective function will have a quadratic form, which can be solved by applying nonlinear optimization algorithms. For more information on decision problem construction, and solution algorithm, together with some illustrative numerical applications, visit the Optimal Business Decisions Web site.

You may use:
Two-Person Zero-Sum Games Theory with Applications for checking your computation and experimentation.

Risk Assessment Process: Clearly, different subjective probability models are plausible they can give quite different answers. These examples show how important it is to be clear about the objectives of the modeling. An important application of subjective probability models is in modeling the effect of state-of-knowledge uncertainties in consequence models. Often it turns out that dependencies between uncertain factors can be important in driving the output of the models. For example, consider two portfolios having random variable R1 and R2 returns; the ratio:

Cov (R1, R2) / Var (R1)

is called the beta of the trading strategy 1 with respect to the trading strategy 2. Various methods are available to model these dependencies, in particular proportional to the Beta values methods.

Numerical Example: Consider our Buying Gold or Foreign Currencies Investment Decision, using the Bivariate Discrete Distributions, JavaScript with equally likelihood (0.25), we obtain:

Beta (Currencies) = -0.457831, and Beta (Gold) = -1.9

Now, one may distribute the total capital ($12000) proportional to the Beta values:

Sum of Beta’s = -0.457831 -1.9 = -2.357831

Y1 = 12000 (-0.457831 /-2.357831) = 12000(0.194175) = $2330, Investing on Foreign Currencies

Y2 = 12000 (-1.9/-2.357831) = 12000(0.805825) = $9670, Investing on Gold

That is, the optimal strategic decision based upon the Beta criterion is: Buy $2330 foreign Currencies, and $9670 Gold.

The above hybrid model brings together the techniques of decision analysis, linear programming, and statistical risk assessments (via a quadratic risk function defined by covariance matrix) to support the interactive decisions for modeling investment alternatives.

A Classification of Investors Relative Attitudes Toward Risk and Its Impact

Decision science does not describe what people actually do since there are difficulties with both computations of probability and the utility of an outcome. Decisions can also be affected by people's subjective rationality, and by the way in which a decision problem is perceived.

Traditionally, the expected value of random variables has been used as a major aid to quantify the amount of risk. However, the expected value is not necessarily a good measure alone by which to make decisions since it blurs the distinction between probability and severity. To demonstrate this, consider the following example:

Suppose that a person must make a choice between scenarios 1 and 2 below:

• Scenario 1: There is a 50% chance of a loss of $50, and a 50% chance of no loss.

• Scenario 2: There is a 1% chance of a loss of $2,500, and a 99% chance of no loss.

Both scenarios result in an expected loss of $25, but this does not reflect the fact that the second scenario might be much more risky than the first. (Of course, this is a subjective assessment). The decision-maker may be more concerned about minimizing the effect of the occurrence of an extreme event than he/she is concerned about the mean. The following charts depict the complexity of the probability of an event, the impact of the occurrence of the event, and its related risk indicator, respectively:

From the previous section, you may recall that the certainty equivalent is the risk free payoff; moreover, the difference between a decision-maker's certainty equivalent and the expected monetary value (EMV) is called the risk premium. We may use the sign and the magnitude of the risk premium in classifying a decision-maker's relative attitude toward risk as follows:

• If the risk premium is positive, then the decision-maker is willing to take the risk, and the decision-maker is said to be a risk seeker. Clearly, some people are more risk-seeker than others.
• If the risk premium is negative, then the decision-maker would avoid taking the risk, and the decision-maker is said to be risk averse.

• If the risk premium is zero, then the decision-maker is said to be risk neutral.

Further Readings
Brooks C., Introductory Econometrics for Finance, Cambridge University Press, 2002.
Eilon S., The Art of Reckoning: Analysis of Performance Criteria, Academic Press, 1984.
Hammond J., R. Keeney, and H. Raiffa, Smart Choices: A Practical Guide to Making Better Decisions, Harvard Business School Press., 1999.
Richter M., and K. Wong, Computable preference and utility, Journal of Mathematical Economics, 32(3), 339-354, 1999.

risk assessment: how good is your portfolio?

without loss of generality, consider our earlier investment example. suppose the optimal portfolio is:

the expected value (i.e., the averages): the expected return is:

where, b_r, s_r, and d_r are the historical averages for b, s, and d, respectively.

expected return alone is not a good indication of a quality decision. the variance must be known so that an educated decision may be made. have you ever heard the dilemma of the six-foot tall statistician who drowned in a stream that had an average depth of three feet?

in the investment example, it is also necessary to compute the 'risk' associated with the optimal portfolio. a measure of risk is generally reported by variation, or its square root called standard deviation. variation or standard deviation are numerical values that indicate the variability inherent to your decision. for risk, smaller values indicate that what you expect is likely to be what you get. what we desire is a large expected return, with small risk; thus, high risk makes the investor very worried.

variance: an important measure of risk is variance:

where var and cov are the variance and covariance, respectively, they are computed using recent historical data.

the variance is a measure of risk; therefore, the greater the variance, the higher the risk. the variance is not expressed in the same units as the expected value. so, the variance is hard to understand and explain as a result of the squared term in its computation. this can be alleviated by working with the square root of the variance, which is called the standard deviation:

both variance and standard deviation provide the same information and, therefore, one can always be obtained from the other. in other words, the process of computing standard deviation always involves computing the variance. since standard deviation is the square root of the variance, it is always expressed in the same units as the expected value.

numerical example: consider our buying gold or foreign currencies investment decision, the above formulas reduce to:

the optimal portfolio is:

  				W = (A -1) / (B -1)

where,

				A = [ (1 - p) / p ] R / U

and

				B = [ (1 - p) / p ] (T+R) / U