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 s1 grams of iron to produce; widget 2 needs s2
grams of iron. You can sell a widget 1 for a profit p1 dollars,
and a widget 2 for a profit of p2 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
p1x1 + p2x2, where x1 is the number of type 1 widgets you’ll produce, and x2 is the number
of type 2 widgets.
- x1 + x2 ≤ W. (You can’t produce more than W widgets.)
- s1x1 + s2x2 ≤ G. (This is
the constraint imposed by the amount of iron you have available to produce
- x1 ≥ 0, x2 ≥ 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 x1 and x2, 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 “s1x1 + s2x2 ≤ G” to a row [s1,s2] in the coefficient matrix,
and “G” as a row in the result matrix. This rendering of the inequalities
is show below.
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 x1 + x2≤W, you
can convert that to an equality by adding a variable representing
W-(x1+x2): x1+x2+xslack=W, where xslack≥0.
So we take the constraint equations, and add slack variables to all of them,
which gives us the following:
- Maximize: p1x1 + p2x2
- x1 + x2 + x3 = W.
- s1x1 + s2x2 + x4 = G.
- x1 ≥ 0, x2 ≥ 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 “p1x1 + p2x2“,
we represent that with an equation “Z-p1x1-p2x2=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.
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.