In my last post on game theory, I said that you could find an optimal

probabilistic grand strategy for any two-player, simultaneous move, zero-sum game.

It’s done through something called linear programming. But linear programming

is useful for a whole lot more than just game theory.

Linear programming is a general technique for solving a huge family of

optimization problems. It’s incredibly useful for scheduling, resource

allocation, economic planning, financial portfolio management,

and a ton of of other, similar things.

The basic idea of it is that you have a linear function,

called an *objective function*, which describes what you’d like

to maximize. Then you have a collection of inequalities, describing

the constraints of the values in the objective function. The solution to

the problem is a set of assignments to the variables in the objective function

that provide a maximum.

For example, imagine that you run a widget factory, which can

produce a maximum of W widgets per day. You can produce two

different kinds of widgets – either widget 1, or widget 2. Widget one

takes s_{1} grams of iron to produce; widget 2 needs s_{2}

grams of iron. You can sell a widget 1 for a profit p_{1} dollars,

and a widget 2 for a profit of p_{2} dollars. You’ve got G grams of iron

available for producing widgets. In order to maximize your profit, how

many widgets of each type should you produce with the iron you have

available to you?

You can reduce this to the following:

- You want to maximize the objective function

p_{1}x_{1}+ p_{2}x_{2}, where x_{1}is the number of type 1 widgets you’ll produce, and x_{2}is the number

of type 2 widgets. - x
_{1}+ x_{2}≤ W. (You can’t produce more than W widgets.) - s
_{1}x_{1}+ s_{2}x_{2}≤ G. (This is

the constraint imposed by the amount of iron you have available to produce

widgets.) - x
_{1}≥ 0, x_{2}≥ 0. (You can’t produce a

negative number of either type of widgets.)

The fourth one is easy to overlook, but it’s really important. One of the tricky things about linear programming is that you need to be sure that you

really include all of the constraints. You can very easily get non-sensical

results if you miss a constraint. For example, if we left that constraint out

of this problem, and the profit on a type 2 widget was significantly higher

than the profit on a type 1 widget, then you might wind up producing a *negative* number of type 1 widgets, in order to allow you to produce

more than W widgets per day.

Once you’ve got all of the constraints laid out, you can convert the

problem to a matrix form, which is what we’ll use for the

solution. Basically, for each constraint equation where you’ve got

both x_{1} and x_{2}, you add a row to a coefficient

matrix containing the coefficients, and a row to the result matrix containing the right-hand side of the inequality. So, for example, you’d convert

the inequality “s_{1}x_{1} + s_{2}x_{2} ≤ G” to a row [s_{1},s_{2}] in the coefficient matrix,

and “G” as a row in the result matrix. This rendering of the inequalities

is show below.

Maximize:

where

Once you’ve got the constraints worked out, you need to do something

called *adding slack*. The idea is that you want to convert the

inequalities to equalities. The way to do that is by adding variables. For

example, given the inequality x_{1} + x_{2}≤W, you

can convert that to an equality by adding a variable representing

W-(x_{1}+x_{2}): x_{1}+x_{2}+x_{slack}=W, where x_{slack}≥0.

So we take the constraint equations, and add slack variables to all of them,

which gives us the following:

- Maximize: p
_{1}x_{1}+ p_{2}x_{2} - x
_{1}+ x_{2}+ x_{3}= W. - s
_{1}x_{1}+ s_{2}x_{2}+ x_{4}= G. - x
_{1}≥ 0, x_{2}≥ 0.

We can re-render this into matrix form – but the next matrix needs

to includes rows and columns for the slack variables.

Now, we need to work the real solution into the matrix. The way that we

do that is by taking the solution – the maximum of the objective function – and naming it “Z”, and adding the new objective function equation into the

matrix. In our example, since we’re trying to maximize the

objective “p_{1}x_{1} + p_{2}x_{2}“,

we represent that with an equation “Z-p_{1}x_{1}-p_{2}x_{2}=0″. So the

final matrix, called the *augmented form matrix* of our

linear programming problem is:

Once you’ve got the augmented form, there are a variety of techniques that

you can use to get a solution. The intuition behind it is fairly simple: the

set of inequalities, interpreted geometrically, form a convex polyhedron. The

maximum will be at one of the vertices of the polyhedron.

The simplest solution strategy is called the simplex algorithm. In the

simplex algorithm, you basically start by finding an arbitrary vertex

of the polyhedron. You then look to see if either of the edges incident to that point slope upwards. If they do, you trace the edge upward to the next

vertex. And then you look to see if the other edge from that vertex slopes

upwards – and so on, until you reach a vertex where you can’t follow an edge to a higher point.

In general, solving a linear programming problem via simplex is pretty

fast – but it’s not necessarily so. The worst case time of it is

exponential. But in real linear programming problems, the

exponential case basically doesn’t come up.

(It’s like a wide range of problems. There are a lot of problems that are,

in theory, incredibly difficult – but because the difficult cases are

very rare and rather contrived, they’re actually very easy to solve. Two

examples of this that I find particularly interesting are both NP complete.

Type checking in Haskell is one of them: in fact, the general type

inference in Haskell is worse that NP complete: the type validation is

NP-complete; type inference is NP-hard. But on real code, it’s effectively

approximately linear. The other one is a logic problem called 3-SAT. I

once attended a great talk by a guy named Daniel Jackson, talking about

a formal specification language he’d designed called Alloy.

Alloy reduces

its specification checking to 3-SAT. Dan explained this saying: “The bad news

is, analyzing Alloy specifications is 3-SAT, so it’s exponential and NP-complete. But the good news is that analyzing Alloy specifications is 3-SAT,

so we can solve it really quickly.”)

This is getting long, so I think I’ll stop here for today. Next post, I’ll

show an implementation of the simplex algorithm, and maybe talk a little bit

about the basic idea behind the non-exponential algorithms. After that, we’ll

get back to game theory, and I’ll show how you can construct a linear

programming problem out of a game.