CHAPTER 10
APPLICATION OF LINEAR PROGRAMMIG
          
Linear programming has found many applications in business and economics.  Even a summary of important applications would require several pages.  Economic models of the firm, theory of production, and others have been reformulated using linearity assumptions and linear programming techniques.  Two major areas in which linear programming  has made significant impacts are input-output analysis and  the theory of games.  In this chapter input-output systems and the theory of games are studied.

TOOL BOX
Mathematica Commands				Function

ConstrainedMax[2x1+3x2,		Solves the linear programming problem Max: Z =2x1+3x2,
{x1+2x2 <= 7,3x1+x2 <= 6},{x1,x2}]	Subject To:  x1+ 2x2 < 7 and  3x1 + x2 <  6.            
 
Solve[{D[z, x]==0, D[z, y]==0},{x,  y}]	Solves ∂(Z/∂)x=0 and ∂(Z/∂)y= 0 for x and y simultaneously.

N[MatrixForm[(({{a11, a12}, {a21, a22}}))*(({{1/a1, 1/a2}, {1/a1, 1/a2}}))]	  Finds (({{(a11/a1), (a12/a2)}, {(a21/a1), (a22/a2)}}))
Note that, star product of matrices using "*" is different from dot product using "."  (See, Chapter 4)

I.   Input-Output Systems: The ConstrainedMax Command 
The Leontief's input-output system was designed to be a simplified model of the economy, describing the interrelationships within the producing sectors and the relationships between producing and consuming sectors of the economy. (See, Wassily W. Leontief, The Structure of American Economy 1919-1939, 2nd ed., Oxford University Press, Fair Lawn, N.J., 1951.)

Every industry in  the economy buys variable inputs from other industries and sells variable inputs to other industries and final goods to the consuming sector.  The producing sector also sells to government and to the foreign countries.  The main objective of the input-output analysis is to determine the level of output that each industry should produce in order to satisfy the total demand for the product of the industry in the economy.  

The following table illustrates the input-output model of an economy producing n goods with an available labor force of (Subscript[L, o]) units.  For the simplicity of exposition, however, sales to the government and foreign countries will be regarded as consumer goods. ( Input-output models represent considerable simplifying assumptions, such as treating consumer demand as exogenous; the industry, rather than the firm being the unit of production; and  assuming simple production technology so that each industry uses a single linear production process to produce a single output.)

Table 1.   Input-Output Model of the Economy   
                                             To Industry: 
({{From Industry:, 1, 2, ., ., j, ., ., n, Unsold Inventory, Consumption, Total}, {1, x11, x12, ., ., x1j, ., ., x2n, u1, c1, x1}, {2, x21, x22, ., ., x2j, ., ., x2n, u2, c2, x2}, {., ., ., ., ., ., ., ., ., ., ., .}, {., ., ., ., ., ., ., ., ., ., ., .}, {i, xi1, xi2, ., ., xij, ., ., xin, ui, ci, xi}, {., ., ., ., ., ., ., ., ., ., ., .}, {., ., ., ., ., ., ., ., ., ., ., .}, {n, xn1, xn2, ., ., xnj, ., ., xnn, un, cn, xn}, {Labor, (Subscript[L, 1]), (Subscript[L, 2]), ., ., (Subscript[L, j]), ., ., (Subscript[L, n]), (Subscript[L, un]), C, (Subscript[L, o])}})
                                           
In this table, (Subscript[x, ij]) represents the quantity of goods sold by industry i to industry j;  (Subscript[u, i]) is the unsold inventory of industry i; (Subscript[C, i]) is the quantity of goods sold by industry i to consumers; and (Subscript[x, i]) is the total output of industry i.  Labor input of the industry i is denoted by (Subscript[L, i]), and (Subscript[L, un]) represents unemployment.

Let (Subscript[a, ij]) = (xij/xj),  for j = 1, ......., n.  (Subscript[a, ij]) is the amount of good i needed to produce a unit of good j.  The (Subscript[a, ij]) coefficients, which are called input-output coefficients, are assumed to be constant and do not change over time, unless, there is a significant technological change in the industry.  Therefore, table1 can be converted to table 2, below, where the  (Subscript[a, ij])'s are input-output coefficients, and (Subscript[l, i]) is the amount of labor needed to produce a unit of good i, (Subscript[l, i]) = (Li/xi).

Table 2.   Input-Output Model of the Economy  with Input-Output Coefficients 
                                             To Industry: 
({{From Industry:, 1, 2, ., ., j, ., ., n, Unsold Inventory, Consumption, Total}, {1, a11, a12, ., ., a1j, ., ., a2n, u1, c1, x1}, {2, a21, a22, ., ., a2j, ., ., a2n, u2, c2, x2}, {., ., ., ., ., ., ., ., ., ., ., .}, {., ., ., ., ., ., ., ., ., ., ., .}, {i, ai1, ai2, ., ., aij, ., ., ain, ui, ci, xi}, {., ., ., ., ., ., ., ., ., ., ., .}, {., ., ., ., ., ., ., ., ., ., ., .}, {n, an1, an2, ., ., anj, ., ., ann, un, cn, xn}, {Labor, (Subscript[l, 1]), (Subscript[l, 2]), ., ., (Subscript[l, j]), ., ., (Subscript[l, n]), (Subscript[L, un]), C, (Subscript[L, o])}})


In this form, the Leontief's input-output system is a useful tool for planning and resource allocation.  The model is mostly a descriptive and predictive model of the economy and does not have a criteria for optimization.  However, if combined with linear programming techniques, it can be used to optimize an objective function subject to certain constraints.

Using the matrix notations of the chapter 4, the production and consumption activity of table 2 can be summarized as,  Ax + U + C = x  or  (I - A)x = U + C, and the labor activity (the last row of the table) can be summarized as l'x + (Subscript[l, un]) = (Subscript[L, o]), 

where A = (({{a11, a12, ., ., a1n}, {a21, a22, ., ., a2n}, {., ., ., ., .}, {., ., ., ., .}, {an1, an2, ., ., ann}})),   x =  (({{x1}, {x2}, {.}, {.}, {xn}})),  U = (({{u1}, {u2}, {.}, {.}, {un}})),   C = (({{c1}, {c2}, {.}, {.}, {cn}})), l = (({{l1}, {l2}, {.}, {.}, {ln}})), and (Subscript[L, un]) and (Subscript[L, o]) are scalars.

The following example illustrates the use of input-output analysis to predict the total output and resource requirements for a given change in consumer demand.

Example:  The input-output table of a two-sector economy is given as,

                                 To Industry:
({{From Industry, 1, 2, Consuption, Total}, {1,  15 ,  10 , 25, 50}, {2, 20, 8, 12, 40}, {Labor , 30, 10, □, 40}})

it is expected that the demand for the products of industries 1 and 2 to increase by 5% and 15% respectively.  Find the level of output that will just be sufficient to satisfy the consumer demand (no inventory).  Find also the required labor input.
Solution:  The input-output coefficients can be derived by finding (Subscript[a, ij]) = (xij/xj).  This will give the input-output coefficients as (({{(15/50), (10/40)}, {(20/50), (8/40)}})) = (({{.30, .25}, {.40, .20}})).  The labor input requirements per unit of output is (({{(30/50), (10/40)}})).  Therefore, the input-output model can be written as,
                                  To Industry:
({{From Industry, 1, 2, Consuption, Total}, {1,  .30 ,  .25 , 25, 50}, {2, .40, .20, 12, 40}, {Labor , .60, .25, □, 40}})

with the expected increase in demand for the products of the two industries, the consumption will change to C* =  (({{25*1.05}, {12*1.15}})) or (({{26.25}, {13.80}})).  Therefore, the total production to satisfy the increased demand and to feed the inter-industry needs can be derived by solving  (I - A).x = C*  or  [(({{1, 0}, {0, 1}})) - (({{.30, .25}, {.40, .20}})).(({{x1}, {x2}}))] = (({{26.25}, {13.80}})).  The solution of this equation results in (({{x1}, {x2}})) = (({{116.30}, {115.65}})).  To find the labor requirement for the new production level, multiply the per unit labor requirement by total output, L = l'x = (({{.60, .25}})).(({{116.30}, {115.65}})) = 98.70.  That is, to satisfy the new consumption level, 116.30 units of x1 and 115.65 units of x2 is needed with a labor input of 99 units. 

To solve the problem using Mathematica, define the variables and solve the (I - A)x = C* equation for x1 and x2 as follows, 
Clear[x1,  x2,  A] 
A =(({{15, 10}, {20, 8}}))*(({{1/50, 1/40}, {1/50, 1/40}}));
sol = Solve[(IdentityMatrix[2] -  A)  .  {x1,  
                  x2} ==  {50*1.05,  40*1.15},  {x1,  x2}] 
to find the labor requirement find  l'.x as follows, 
(({{.60, .25}})). (({{x1}, {x2}}))/.{sol}
ReplaceAll::reps: {{sol}} is neither a list of replacement rules nor a valid dispatch table, and so cannot be used for replacing.
{{0.6 x1+0.25 x2}}/.{sol}
The necessary and sufficient conditions for the existence of a general solution to an input-output system is provided by the Hawkins-Simon conditions. (See,  David Hawkins and  Herbert A. Simon, "Note: Some Conditions of Macroeconomic Stability," Econometrica, Vol. 17 (July-October, 1949), PP. 245-48.)  The Hawkins-Simon conditions require that all of the principal minors of the coefficient matrix  (I - A) to be non negative. That is, (1 - a11) > 0, Det(({{1 - a11, -a12}, {-a21, 1 - a22}})) > 0, Det(({{1 - a11, -a12, -a13}, {-a21, 1 - a22, -a23}, {-a31, -a32, 1 - a33}})) > 0, ..., and Det[(I - A)] > 0.  The first and subsequent inequalities above require that (Subscript[a, ii]) < 1, (i = 1, ...., n).  If (Subscript[a, ii]) > 1 for some i, one or more units of i would be required to produce one unit of i.  No output can take place under such conditions.   

The preceding example illustrates the descriptive and predictive features of the input-output analysis.  Combined with the linear programming technique, the input-output analysis can be used to include the optimizing criteria.  

Allowing for the possibilities of inventories and unemployment, the two equations of the input-output system can be written as, 

      (I - A).x > C           
           l'.x < (Subscript[L, o])       

These two equations are the constraints based on the inter-industry input requirements, final consumer demand, and the 
 resource requirements.  The objective can be set as maximizing gross national product, GNP = P'.x, where P is a vector of n average prices for outputs of the industries, P' = (({{p1, ., ., ., pn}})).  Therefore, the optimization problem can be written as:
Maximize:      GNP = P'.x
Subject to:     (I - A).x > C           
                            l'.x  <  (Subscript[L, o])      
                               x > 0

Example:  Suppose that a simple economy is described by the following input-output model.

                                    To Industry:
({{From Industry:, 1, 2, 3, Consumption, Unsold Inventory, Total}, {1, 24, 10, 14, 30, 2, 80}, {2, 32, 20, 7, 40, 1, 100}, {3, 40, 5, 14, 10, 1, 70}, {Labor, 60, 80, 42, □, 18, 200}})

It is expected that demand for the three products will increase by 10% for the next year, while the labor input will increase by 1%.  If the unit prices for the products are $15, $25, and $10 respectively, set up the problem of maximizing GNP subject to the constraints, and test for the existence of a solution.

Solution: Find the input-output coefficients by finding (Subscript[a, ij]) = (xij/xj) to convert the input-output table to the table of input-output coefficients.  The conversion yields a matrix of input-output coefficients A = (({{(24/80), (10/100), (14/70)}, {(32/80), (20/100), (7/70)}, {(40/80), (5/100), (14/70)}})) = (({{.30, .10, .20}, {.40, .20, .10}, {.50, .05, .20}})) and a vector of per unit labor requirements l' = (({{(60/800), (80/100), (42/200)}})).  The input-output model can be written as, 

                                    To Industry:
({{From Industry:, 1, 2, 3, Consumption, Unsold Inventory, Total}, {1, .30, .10, .20, 30, 2, 80}, {2, .40, .20, .10, 40, 1, 100}, {3, .50, .05, .20, 10, 1, 70}, {Labor, .75, .80, .60, □, 18, 200}})

For the coming period, demand is expected to be  C*  = 1.10*C = (({{33, 44, 11}}))and the labor force is expected to be (Subscript[L, o]) = 202.  The problem can be formulated as: (Note that Inventories are not explicitly included in the formulation.  However, they are included implicitly by setting inequalities (I - A)x > C, rather than (I - A)x = C.) 

Maximize:  (({{15, 25, 10}})).(({{x1}, {x2}, {x3}}))
Subject To:  ((({{1, 0, 0}, {0, 1, 0}, {0, 0, 1}})) - (({{.3, .1, .2}, {.4, .2, .1}, {.5, .05, .2}}))).(({{x1}, {x2}, {x3}})) > (({{33}, {44}, {11}}))
     
                        (({{.75, .8, .6}})).(({{x1}, {x2}, {x3}})) <  202              
                          x1, x2, x3 > 0
This is a linear programming problem that can be solved through Simplex method discussed in the previous chapter.  The solution yields x1 = 85.07, x2 = 117.06, and x3 = 74.24, with a GNP of 4949.07.   

Testing for the existence of a solution, the three principal minors of the (I - A) matrix are, (1 - .3) = .7 > 0, Det(({{.7, - .1}, {- .4, .8}}))= .52 > 0, and Det[(I - A)] =  .323 > 0.  Since all the three principal minors are positive, the system has a solution with all three outputs positive.


To solve the problem using Mathematica, set up the linear programming problem, define the variables, and use the  ConstrainedMax command.

Clear[x1,  x2,  x3,  A]
A = (({{24, 10, 14}, {32, 20, 7}, {40, 5, 14}}))*(({{1/80, 1/100, 1/70}, {1/80, 1/100, 1/70}, {1/80, 1/100, 1/70}}));
MatrixForm[IdentityMatrix[3] - A]

(({{(7/10), -(1/10), -(1/5)}, {-(2/5), (4/5), -(1/10)}, {-(1/2), -(1/20), (4/5)}}))

ConstrainedMax[15x1+25x2+10x3,{.7x1-.1x2-.2x3>=33,-.4x1+.8x2 -.1x3>=44,-.5x1-.05x2+.8x3>=11, .75x1+.8x2+.6x3<=202}, {x1, x2, x3}]
{4945.07,{x1->85.0771,x2->117.061,x3->74.2395}}
Problems

1-  For the following input-output system,  find the input-output coefficients and determine whether the system has a general solution.  Suppose that consumers will be increasing their consumption of the three goods by 8% .  Determine the output levels and the labor needed to produce them.
 
                                       To Industry:
({{From Industry:, 1, 2, 3, Consumption, Unsold Inventory, Total}, {1, 160, 100, 420, 100, 20, 800}, {2, 400, 400, 70, 120, 10, 1000}, {3, 80, 400, 140, 50, 30, 700}, {Labor, 500, 600, 400, □, 100, 1600}})

2- The following input-output model represents an economy that the consumption for goods is growing at an annual rate of 5% and the labor force is growing at an annual rate of 1.5% .  Given that prices are, P1 = 3, P2 = 8, and P3 = 4, find the GDP, production levels and the consumption levels of the three goods for the next year.

                                       To Industry:
({{From Industry:, 1, 2, 3, Consumption, Unsold Inventory, Total}, {1, 360, 200, 360, 250, 30, 1200}, {2, 600, 100, 180, 100, 20, 1000}, {3, 360, 300, 90, 140, 10, 900}, {Labor, 1000, 850, 700, □, 50, 2600}})


 3-  The following input-output model represents an economy that the consumption of good 1 is growing at an annual rate of 5% and the consumption of good 2 is growing at a rate of 15%.  The labor force is growing at an annual rate of 1.5% .  Given that prices are, P1 = 24, and P2 = 18,  find the GDP, production levels and the consumption levels of the three goods for the next year.

			To Industry:
({{From Industry:, 1, 2, Consumption, Unsold Inventory, Total}, {1, 640, 225, 700, 35, 1600}, {2, 480, 150, 100, 20, 750}, {Labor, 800, 325, □, 25, 1150}})
  

 4-  The following input-output model represents an economy that the consumption for good 1, 2 , and 3 are growing at an annual rate of 5%, 8%, and 12%, respectively.  The labor force is growing at an annual rate of 1.8% .  Given that prices are, P1 = 10, P2 = 8, and P3 = 14, find the GDP, production levels and the consumption levels of the three goods for the next year.

                                       To Industry:
({{From Industry:, 1, 2, 3, Consumption, Unsold Inventory, Total}, {1, 340, 180, 320, 220, 18, 1078}, {2, 540, 85, 160, 80, 20, 885}, {3, 340, 320, 80, 130, 12, 882}, {Labor, 960, 850, 720, □, 54, 2584}})


II.  Theory of Games: The Solve[{D[z, x]==0, D[z, y]==0},{x,  y}] Command
In 1944, Von Neumann and Morgenstern published their Theory of Games and Economic Behavior.  (See, Von Neumann, J. and O. Morgenstern, 1964, Theory of Games and Economic Behavior, 3rd ed., Science Edition, Wiley, New York.)   The main topic of the book was to determine standards of "rational behavior" in situations in which the outcomes depend on the actions of interdependent players.  The players may behave cooperatively or competitively.  In each case, the concept of solution is a set of rules for each player which tells the player how to behave in every situation which may arise.

Experience with game theory models shows that the theory of games is more relevant to the study of specific business and economic problems than the classical approach and solutions.  One of the topics in economics in which the interaction of decisions has an important role is imperfect competition, situations such as bilateral monopoly, duopoly, and oligopoly.

Two-Person, Zero-Sum Games:   Every  game consists of a number of strategies on the part of each of its participants.  A strategy is the specification of a particular move for one of the participants.  Each player has a finite number of strategies under her control.  The outcome of a game, i.e., the profit or the utility earned by each participant, is determined by the interaction of the selected strategies by participants.  A game may be a one-person, two-person, or n-person game.  It may also be a zero-sum game or non-zero-sum game.  

A zero-sum game is one in which the algebraic sum of the outcomes for all the participants equals zero for every possible combinations of strategies.  That is, the gain of one player equals the loss of other players.  If the net outcome of a game is other than zero for at least one strategy combination, it is called a non-zero-sum game.  The analysis below is restricted to two-person zero-sum games.

Suppose that the payoff matrix for player I is given  by the following table, 

                                                          Payoff Matrix of Player I                                   
                                                                           Player II
Player I	({{□, B1, B2, ., ., Bj, ., ., Bm, Min .  Row}, {A1, a11, a12, ., ., a1j, ., ., a1m, a1}, {A2, a21, a22, ., ., a2j, ., ., a2m, a2}, {., ., ., ., ., ., ., ., ., .}, {Ai, ai1, ai2, ., ., aij, ., ., aim, ai}, {., ., ., ., ., ., ., ., ., .}, {An, an1, an2, ., ., anj, ., ., anm, an}, {Max .  Column, b1, b2, ., ., bj, ., ., bm, □}})

player I chooses from strategies A1, ......, An, and player II chooses from strategies B1, ......, Bm.  (Subscript[a, ij]) is the payoff to player I if he chooses Ai strategy when player II selects Bj strategy.  The last column in the table shows the minimum value across row i and the last row shows the maximum value down column j.

The game is said to have a saddle point, if there is a strategy for each player at which the game settles. If the game has a
saddle point, the value of the game is determined by the minimax criterion.  The minimax criterion is based on the following relationship,  a* = (Subscript[Max, i]) ((Subscript[Min, j])(Subscript[a, ij])) < Z < (Subscript[Min, j]) ((Subscript[Max, i])(Subscript[a, ij])) = b*, where, a* is the maximum value among (Subscript[a, i]), b* is the minimum value among (Subscript[b, j]), and Z is the value of the game.

This relationship holds because (Subscript[Min, j])(Subscript[a, ij]) is a vector of the smallest values, of which the largest is (Subscript[Max, j]) ((Subscript[Min, j])(Subscript[a, ij])).  On the other hand, (Subscript[Max, i])(Subscript[a, ij]) is a vector of the large values, of which the smallest is (Subscript[Min, j]) ((Subscript[Max, i])(Subscript[a, ij])).  If a* = b*, (Subscript[Max, i]) ((Subscript[Min, j])(Subscript[a, ij])) = Z = (Subscript[Min, j])((Subscript[Max, i])(Subscript[a, ij])) and the game has a saddle point, with the value of the game equal to Z.

Example:  The payoff matrix in dollars for player I is given by the following table.  Find the player I's payoff.  


	                                     Payoff Matrix of Player I
                                                             Player II
Player I	({{□, B1, B2, B3, Min .  Row}, {A1, 8, 6, 5, 5}, {A2, 9, 7, 8, [7]}, {A3, 6, 5, 4, 4}, {Max .  Column, 9, [7], 8, □}})

Solution:  By the minimax criterion, the solution exists and the saddle point is at the intersection of strategies A2 and B2, with a payoff of $7 for player I.

This solution is arrived at by the minimax criterion.  However, if different options of player I are tested for, the solution will be no different from that of the minimax criterion.  For example, player I may  select strategy A1 to receive a payoff of 8, the largest payoff in that strategy.  However, player II's reaction will be to select B3, to give the player I a payoff of 5, the smallest payoff in row 1.  Player II's strategy of B3 will force player I to select strategy A2, to get a payoff of 8.  This will make player II move to strategy B2 to give player I a payoff of 7.  With player II taking strategy B2, player I will not have any incentive to move away from strategy A2.  Any further move by player I will hurt that player and will benefit player II.  Any further move by player II will also not benefit that player.  It will hurt player II and will benefit player I.  Therefore, A2B2 is the saddle point.

Example:  The payoff matrix in market shares for player I is given by the following table.  Find the solution of the game. 

	                          Payoff Matrix of Player I
                                                             Player II
Player I	({{□, B1, B2, B3, Min .  Row}, {A1, .7, .3, .5, .3}, {A2, .6, .4, .8, .4}, {A3, .5, .6, .9, .5}, {Max .  Column, .7, .6, .9, □}})

 
Solution:  This game does not have a saddle point.  However, a solution may be found using the mixed strategies of the next section.

Mixed Strategies:  Players may select pure strategies and play.  The game,  however, may or may not have a solution.  If the game does not have a saddle point, players will select their strategies on a probabilistic basis.  Each player will randomize the strategy selection by assigning  probabilities to strategies.  The players are now concerned with the expected, rather than the actual payoff.  The following example illustrates the case.

Example:  The payoff matrix for a game is given below.   Find the solution of the game.

                 Payoff Matrix of Player I
                                                       Player II
Player I	({{□, B1, B2, Min .  Row}, {A1, 4, 2, 2}, {A2, 1, 3, 1}, {Max .  Column, 4, 3, □}})

Solution:  This game does not have a saddle point.  Now, suppose that player I selects strategy A1, x% of times, and strategy A2, (1 - x)% of times.  Player II selects strategy B1, y% of times, and strategy B2,  (1 - y)% of times.  Since strategies are selected randomly, player I can not anticipate player II's choice of strategy, even if she knows y, and vice versa.

Based on the given probabilities, each payoff depends on the joint probability of selected strategies by the two players.  The following table shows the payoffs and their probabilities.

                                                         Payoff Matrix of Player I
                                                                              Player II
Player I	({{., ., B1, B2}, {., Probabilities, y, (1 - y)}, {A1, x, ({{4}, {xy}}), ({{2}, {x (1 - y)}})}, {A2, (1 - x), ({{1}, {(1 - x) y}}), ({{3}, {(1 - x) (1 - y)}})}})

The expected payoff to player I is the sum of the payoffs times their corresponding probabilities, 

 Z(x,y) = 4xy + 2x(1 - y) + (1 - x)y + 3(1 - x)(1 - y)

Player I's objective is to maximize Z(x,y) with respect to x, and for a given y.  This is achieved by finding derivative of Z(x, y) with respect to x, setting it equal to zero, and solving it for y.

((∂Z )/∂)x =  4y + 2(1 - y) - y -3(1 - y) = 0,   or  y = (1/4)

Player II's objective is to minimize Z(x,y) with respect to y, and for a given x.  This is achieved by finding derivative of Z(x, y) with respect to y, setting it equal to zero, and solving for x.

((∂Z )/∂)y = 4x - 2x + (1 - x) -3(1 - x) = 0,    or  x = (1/2)

Substitute for x and y in Z(x, y) to get the payoff  Z = (5/2).   

The solution implies that player I will adopt strategy A1 50% of times and strategy A2 50% of times in a given period to maximize her payoff, regardless of what strategies player II selects.   To minimize player I's payoff, player II will adopt strategy B1 and B2 at the rates of 25% and 75%, respectively, regardless of what strategy player I selects.  

To solve the problem using Mathematica, define the payoff equation, set its derivatives with respect to x and y equal to zero, and solve the resulting equations simultaneously for x and y.   To find the payoff for player I, evaluate Z for the solution.
Clear[x, y, z, game]
z = 4x y + 2x (1-y) + (1-x) y + 3(1-x) (1-y);
game = Solve[{D[z, x]==0, D[z, y]==0},{x,  y}]
{{Null (x -> (1/2)), Null (y -> (1/4))}}
z/.{game}
{{(5/2)}}
The mixed strategies solution is the maximum that player I will receive if player II plays optimally and both players have complete information.  The solution assures player I of a minimum level of return no matter how player II plays.  However, if player II does not play optimally, then player I will receive more.  

Example:  The game in the following table does not have a saddle point.  Solve the mixed-strategy game and find the payoff of player I.

	                                                          Payoff Matrix of Player I
                                                                                         Player II
Player I	({{., ., B1, B2, B3, Min .  Row}, {., Probabilities, y1, y2, (1 - y1 - y2), .}, {A1, x1, 5, 2, 3, 2}, {A2, x2, 1, 3, 4, 1}, {A3, (1 - x1 - x2), 2, 6, 3, 2}, {Max .  Column, ., 5, 6, 4, .}})


Solution:  To find the mixed strategies solution, assume that player I selects A1, A2, and A3 with probabilities x1, x2, and (1 - x1 - x2), respectively, and player II selects B1, B2, and B3 with probabilities y1, y2, and (1 - y1 - y2), respectively.  The payoff for the player I is  Z(x1, x2, y1, y2) = 5x1y1 +2x1y2 +  3x1(1 - y1 - y2) + x2y1 + 3x2y2 + 4x2(1 - y1 - y2) + 2(1 - x1 - x2)y1 + 6(1 - x1 - x2)y2 + 3(1 - x1 - x2)(1-y1-y2).   Player I maximizes Z assuming given levels of y1 and y2.  That is, she sets ((∂Z )/∂)x1 =((∂Z )/∂)x2 = 0 and solves them for y1 and y2.  That is,

∂(Z/∂)x1 = 3y1 - 4y2 = 0

∂(Z/∂)x2 = 1 - 2y1 - 4y2 = 0

Solving these two equations together results in y1 = (1/5) and y2 = (3/20).  Player II minimizes  Z  assuming given levels of x1 and x2.  That is, she sets ((∂Z )/∂)y1= ((∂Z )/∂)y2 = 0 solves them for x1 and x2.  That is,

∂(Z/∂)y1 = -1 + 3x2 + 2x2 = 0

∂(Z/∂)y2 = 3 - 4x2 - 4x2 = 0

Solving the above two equations together results in x1 = (1/2) and x2 = (1/4).  The mixed strategies solution to the game is found by substituting for x1, x2, y1, and y2 in the Z equation,.  The payoff of player I is found to be Z = (13/4).  

To solve the problem using Mathematica, formulate Z, find its derivatives with respect to x1, x2, y1, y2, and set them equal to zero.  Solve the equations simultaneously for x1, x2, y1, and y2.
Clear[x1, x2, y1, y2, z, game2]
z = 5x1 y1 + 2x1 y2 + 3x1 (1-y1-y2) + x2 y1  + 3x2 y2 + 4x2 (1-y1-y2)  + 2(1-x1-x2)  y1 + 6(1-x1-x2) y2 + 3(1-x1-x2) (1-y1-y2);
game2 = Solve[{D[z, x1]==0, D[z, x2]==0, D[z, y1]==0, D[z, y2]==0}, {x1, x2, y1, y2}]

{{Null (x1 -> (1/2)), Null (x2 -> (1/4)), 
          Null (y1 -> (1/5)), Null (y2 -> (3/20))}}
To find Z,evaluate Z at the solution set of the equations. 
z/.{game2}
{{(13/4)}}
The mixed strategies solution to the game is where the player I adopts strategies A1,  50% of times, A2,  25% of times, and A3,  25% of times.  The payoff for player I is Z = (13/4).  This is the maximum that player I will receive if player II plays optimally, taking B1, B2, and B3 with probabilities of 20%, 15%, and 65%,  respectively.  However, if player II does not play optimally, say for example adopts B1and stays with that strategy only, then player I can play the pure strategy A1 and receive a payoff of 5, which is more than the mixed strategies payoff of Z = (13/4).

It is important to note that the payoff of the mixed strategies solution ((13/4))lies between the minimax solution (4), which is the minimum payoff in the "Max. Column" of the payoff matrix above and the maximin solution (2), which is the maximum payoff in the "Min. Row" column of the payoff matrix above. 
 
Dominated Strategies:  Occasionally, the solution of a mixed strategies game can be simplified by deleting dominated or inferior strategies.  A dominated strategy for player I is the one for which all the elements of the strategy are no more than the corresponding elements of some other strategy.  A dominated strategy for player II is the one that all elements of the strategy are no less than the corresponding elements of some other strategy.

It is obvious that player I's objective is to select strategies that will maximize her payoff.  Therefore, if all elements of a strategy are less than or equal to the corresponding elements of another strategy, player I will never play or select the strategy with lower payoffs.  On the contrary, player II's objective is to adopt strategies that will minimize player I's payoff.  Therefore, if all elements of a strategy are more than or equal to the corresponding elements of other strategy, player II will never select the strategy with higher payoffs for player I.  

Deleting dominated strategies will not effect  the saddle point or the solution of mixed strategies games.  The following example illustrates the point.

Example:  The payoff matrix of a game is given below.  Find the solution of the game.

	                             Payoff Matrix of Player I
                                                             Player II
Player I	({{□, B1, B2, B3, B4, Min .  Row}, {A1, 10, 16, 20, 13, 10}, {A2, 16, 18, 19, 18, 16}, {A3, 13, 1, 0, 8, 0}, {A4, 17, 6, 9, 8, 6}, {Max .  Column, 17, 18, 20, 18, □}})

 Solution:  This game does not have a saddle point.  A mixed strategies solution without deleting the dominated strategies will be cumbersome.  However, a close look at the table reveals that all the elements of strategy A3 are less than or equal to the corresponding elements of A4.  For player I this strategy is dominated by strategy A4 and can be deleted.  Once A3 is deleted, all the elements of B3 turn out to be greater than B4.  Therefore, player II will never play strategy B4.  For player II, strategy B3 is a dominated strategy and can be deleted.  The reduced payoff matrix will be as follows,
 
 
	                  Reduced Payoff Matrix of Player I
                                                             Player II
Player I	({{□, B1, B2, B4, Min .  Row}, {A1, 10, 16, 13, 10}, {A2, 16, 18, 18, 16}, {A4, 17, 6, 8, 6}, {Max .  Column, 17, 18, 18, □}})

The reduced payoff matrix can be reduced further more.  All elements of A1 are less than A2.  For player I strategy A1 is dominated by A2 and can be deleted.  Once A1 is deleted, elements of B4 become greater than or equal to elements of B2.  Therefore, for player II strategy B4 is a dominated strategy and can be deleted.  The reduced game matrix and the probabilities of each payoff are as follows, 
 
                                 Payoff Matrix of Player I
                                                       Player II
Player I	({{., ., B1, B2}, {., Probablities, y, (1 - y)}, {A2, x, 16, 18}, {A4, (1 - x), 17, 6}})

assuming that player I selects strategies A1 and A2 with probabilities x and (1 - x) respectively, and player II selects strategies B1 and B2 with probabilities y and (1 - y) respectively, the payoff matrix can be found as: 

Z = 16zy + 16x(1 - y) + 17y(1 - x) + 6(1 - x)(1 - y)

To find the optimal solution, maximize z with respect to x by setting ∂(Z/∂)x = 12 - 13y = 0, or y = (12/13) and minimize Z with respect to y by setting ∂(Z/∂)y = 11 - 13x = 0, or  x = (11/13).  Substitute for x and y in the payoff equation Z to find Z = (210/13).  

To solve the problem using Mathematica, formulate Z and find the optimal solution as follows, 
Clear[x, y, z, game3]
z= 16x y + 18x (1-y) + 17(1-x) y + 6(1-x) (1-y); 
game3=Solve[{D[z,x]==0, D[z, y]==0}, {x, y}]
{{Null (x -> (11/13)), Null (y -> (12/13))}}
z/.{game3}
{{(210/13)}}
Problems

1- For the following game matrices,  find the  saddle point and strategies that provide the  saddle point.   Find the payoff of each game.

 a-         Payoff Matrix of Player I
                                 Player II
Player I	({{□, B1, B2}, {A1, 4, 8}, {A2, 3, 5}})


b-                Payoff Matrix of Player I
                                        Player II
Player I	({{□, B1, B2, B3, B4}, {A1, 12, 7, 9, 12}, {A2, 8, 6, 11, 22}})

                     
c-             Payoff Matrix of Player I
                                    Player II
Player I	({{□, B1, B2, B3}, {A1, 8, 4, 2}, {A2, -2, 1, -1}, {A3, 10, 5, 3}})


d-               Payoff Matrix of Player I
                                    Player II
Player I	({{□, B1, B2, B3, B4}, {A1, 1, 2, 3, 12}, {A2, 7, 8, 6, 10}, {A3, 5, 11, 4, 3}})

                   
2-  For the following games, the saddle point can not be determined if the players select pure strategies.  Find the probabilities of mixed strategies which will provide a saddle point.  Find the payoff of the games.

 a-         Payoff Matrix of Player I
                                 Player II
Player I	({{□, B1, B2}, {A1, 6, 3}, {A2, 2, 8}})


b-             Payoff Matrix of Player I
                                    Player II
Player I	({{□, B1, B2, B3}, {A1, 19, 23, 11}, {A2, 15, 19, 20}, {A3, 27, 18, 19}})
                        
c-             Payoff Matrix of Player I
                                    Player II
Player I	({{□, B1, B2, B3, B4}, {A1, 12, 8, 9, 12}, {A2, 8, 9, 11, 7}})