We're going to assume that this historical data is a good model for the future behavior of the market in the following precise sense: we assume next year's returns for these instruments will be some convex combination of these five historical years' returns. That is, maybe next year's returns will be the same as in 1982, or maybe the five growth values next year will be 1/3 the corresponding 1983 values plus 2/3 the corresponding 1984 values, etc. (Note that next year's vector will be some convex combination of the previous years' vectors; it's not that each individual instrument's growth value can be a different convex combination of that instrument's previous growth values. Added: If it could use a different convex combination for each column--which it can't--then it could, for each column, choose a convex combination weighting the column's smallest element with 1 and the rest with 0s, in order to obtain a row of the smallest number in each column (in this case all 1s.))

Added: Note also that this is consistent with how things normally are: each component (fraction) Column chooses as a component in its mixed strategy is a coefficient weighting some pure strategy, i.e., one column in the game table; similarly, each component Row chooses weights a row in the table. Fate does not get to choose different weights to compute each individual instrument's growth value in the new year. It can't put weights specifically on cells, only on rows (recall the matrix multiplication $\mathbf{y^\intercal A x}$). The power levels are the same: Row can multiply all the instrument's values in a given year; Row can multiply a given instruments values over all years.

Now, given that model of the market, you as a risk-averse invester are going to seek an investment strategy to maximize your minimum total growth. We model this as a zero-sum two-player game, between you and Cruel Fate, where you want to maximize your profit and Fate wants to minimize it. Now we can interpret the table above as a game matrix, where you the investor are Row Column and Fate is Column Row. Each pure strategy of Row Column corresponds to one of the financial instruments, i.e., the action of investing all the money in that instrument; a mixed strategy for Column is thus a possible investment portfolio: the percentages (possibly zero) of the budget to go into the various investments. Each pure strategy of Column Row corresponds to one year, i.e., the possibility of having next year's market behave exactly like that other year; a mixed strategy for row is a convex combination of (some of) the prior years' markets.

Added: One other wrinkle: we usually speak in terms of mixed strategies randomizing over pure strategies, i.e. of mixed strategies as discrete probability distributions on the set of pure strategies, or in different terminology, a convex combination of their values. Here there's nothing "random" the nature of Column's choices: they're allocation amounts to be invested in the different financial instruments. What that really means, though, is that some amount of money, zero or more, is invested in each instrument, and the sum of the amounts invested must equal the (Fixed) budget--if we normalize that budget to 1, then this again is precisely a convex combination.

Read through this model file. It's written in AMPL's particular syntax, but you should be able to make sense of it, finding the objective, the variables (free and nonnegative), the constraints, and game matrix $A$. Notice that the constraints ensuring that the max-min payoff $V$ is less equal to the total growth for each of the years are called cnstrs, and are indexed by YEARS.

1. You're going to solve the LP using this AMPL website. (Or, if you want to figure out how, you could install the CPLEX solver on your own computer.) Copy the contents of the model file into the model/data text box, and copy the following into the commands text box:

   solve;
   display _varname,_var;
   display _conname,_con;
   

   Then press Send, and the solution should be displayed in a new text box above. In addition to the value of the objective function ($V$), it will display the values of the components of the $x$ vector as well as the values of the dual variables (corresponding to the constraints).

   What values did you get back?

2. What does that output mean? That is, what is the risk-averse investor's optimal max-min investment strategy? And what is Cruel Fate's optimal min-max strategy for limiting the investor's profits?

3. Now let's work out what these being max-min and min-max strategies means. First, from the investor's point of view, assume Fate is following the min-max strategy you just computed. Given this, what are your payoffs under each of the pure strategies in the support of your max-min strategy? What are the payoffs under each of the pure strategies not in the support?

   Now from Fate's point of view, assuming the investor plays the max-min strategy. What are the investor's payoffs under each of the pure strategies in the support of Fate's min-max strategy? What are the investor's payoffs under each of the pure strategies not in the support?

4. The complementary slackness conditions must be satisfied by all primal and dual optimal solutions. What are the slackness conditions (both kinds: the ones the primal variables $x$ being nonzero and the ones with the dual variables corresponding to the constraints $cnstrs$ being nonzer) in the case of this particular LP?

5. Now, explain. What is the relationship 1) between the optimal solution value and the payoffs of the strategies in the investor's max-min strategy's support on the one hand, and 2) between the solution value and the the payoffs of the strategies not in the support? Similarly, what is the relationship between the solution value and the payoffs of the strategies 3) in and 4) not in the support of Fate's min-max strategy?

6. Now let's experiment a little. Suppose you changed the historical value of A[1984,Bonds] A[1984,TBills] from 1 to 10. (You can edit in place in the model/data text box and press Send to have it solve your updated LP.) Why did Fate's strategy change the way it did?

7. Finally, can you find one additional entry of $A$ to change (maintaining A[1984,Bonds]=10 A[1984,TBills]=10) so that the game will have a pure max-min/min-max/NE? (Hint: remember saddle points.)

$\max \sum e_{uv} x_{uv}$
s.t.
$\sum_u x_{uv} \le 1 \quad \forall v$
$x_{uv} \ge 0$

A variation on the maximum matching problem is minimum-cost perfect matching, where the goal is to find a perfect matching (a disjoint collection of edges covering all nodes), but in particular a perfect matching of lowest total cost (i.e., the sum of the costs of the chosen edges, where $e_{uv}$ is now interpreted as the cost of choosing edge $\{u,v\}$). Give an LP formulation of this problem. (Modify the LP above so that it accurately describes this new problem.)

$\min \sum x_{uv}$
s.t.
$\sum_u x_{uv} \ge 1 \quad \forall v$
$x_{uv} \ge 0$

Notice the difference between this problem and matching: here the edges chosen are not necessarily disjoint, although they ideally they would be.

1. Give the dual of this LP.

2. What does this dual LP mean, assuming that in both the primal and dual problems the variables are "intended" to be 0/1? Try to figure out and describe in your own words what problem the dual LP is solving. (In order to see what's going on, it might help to draw a small example graph with, say, five nodes and a few edges and seeing what feasible solutions would look like, and what sort of solutions the objective is preferring.)