The Foundations of Applied Mathematics

Suppose we take “applied mathematics” in an extremely broad sense that includes math developed for use in electrical engineering, population biology, epidemiology, chemistry, and many other fields. Suppose we look for mathematical structures that repeatedly appear in these diverse contexts — especially structures that aren’t familiar to pure mathematicians. What do we find? The answers may give us some clues about how to improve the foundations of mathematics!

This is what I’m talking about at the Category-Theoretic Foundations of Mathematics Workshop at U.C. Irvine this weekend.

You can see my talk slides here. You can click on any picture or anything written in blue in these slides to get more information — for example, references.

Petri Net Programming (Part 3)

guest post by David Tanzer

The role of differential equations

Last time we looked at stochastic Petri nets, which use a random event model for the reactions. Individual entities are represented by tokens that flow through the network. When the token counts get large, we observed that they can be approximated by continuous quantities, which opens the door to the application of continuous mathematics to the analysis of network dynamics.

A key result of this approach is the “rate equation,” which gives a law of motion for the expected sizes of the populations. Equilibrium can then be obtained by solving for zero motion. The rate equations are applied in chemistry, where they give the rates of change of the concentrations of the various species in a reaction.

But before discussing the rate equation, here I will talk about the mathematical form of this law of motion, which consists of differential equations. This form is naturally associated with deterministic systems involving continuous magnitudes. This includes the equations of motion for the sine wave:

and the graceful ellipses that are traced out by the orbits of the planets around the sun:

This post provides some mathematical context to programmers who have not worked on scientific applications. My goal is to get as many of you on board as possible, before setting sail with Petri net programming.

Three approaches to equations: theoretical, formula-based, and computational

Let’s first consider the major approaches to equations in general. We’ll illustrate with a Diophantine equation

where and are integer variables.

In the theoretical approach (aka “qualitative analysis”), we start with the meaning of the equation and then proceed to reason about its solutions. Here are some simple consequences of this equation. They can’t all be zero, can’t all be positive, can’t all be negative, can’t all be even, and can’t all be odd.

In the formula-based approach, we seek formulas to describe the solutions. Here is an example of a formula (which does not solve our equation):

Such formulas are nice to have, but the pursuit of them is diabolically difficult. In fact, for Diophantine equations, even the question of whether an arbitrarily chosen equation has any solutions whatsoever has been proven to be algorithmically undecidable.

Finally, in the computational approach, we seek algorithms to enumerate or numerically approximate the solutions to the equations.

The three approaches to differential equations

Let’s apply the preceding classification to differential equations.

Theoretical approach

A differential equation is one that constrains the rates at which the variables are changing. This can include constraints on the rates at which the rates are changing (second-order equations), etc. The equation is ordinary if there is a single independent variable, such as time, otherwise it is partial.

Consider the equation stating that a variable increases at a rate equal to its current value. The bigger it gets, the faster it increases. Given a starting value, this determines a process — the solution to the equation — which here is exponential growth.

Let be the value at time and let’s initialize it to 1 at time 0. So we have:

These are first-order equations, because the derivative is applied at most once to any variable. They are linear equations, because the terms on each side of the equations are linear combinations of either individual variables or derivatives (in this case all of the coefficients are 1). Note also that a system of differential equations may in general have zero, one, or multiple solutions. This example belongs to a class of equations which are proven to have a unique solution for each initial condition.

You could imagine more complex systems of equations, involving multiple dependent variables, all still depending on time. That includes the rate equations for a Petri net, which have one dependent variable for each of the population sizes. The ideas for such systems are an extension of the ideas for a single-variable system. Then, a state of the system is a vector of values, with one component for each of the dependent variables. For first-order systems, such as the rate equations, where the derivatives appear on the left-hand sides, the equations determine, for each possible state of the system, a “direction” and rate of change for the state of the system.

Now here is a simple illustration of what I called the theoretical approach. Can ever become negative? No, because it starts out positive at time 0, and in order to later become negative, it must be decreasing at a time when it is still positive. That is to say, , and . But that contradicts the assumption . The general lesson here is that we don’t need a solution formula in order to make such inferences.

For the rate equations, the theoretical approach leads to substantial theorems about the existence and structure of equilibrium solutions.

Formula-based approach

It is natural to look for concise formulas to solve our equations, but the results of this overall quest are largely negative. The exponential differential equation cannot be solved by any formula that involves a finite combination of simple operations. So the solution function must be treated as a new primitive, and given a name, say . But even when we extend our language to include this new symbol, there are many differential equations that remain beyond the reach of finite formulas. So an endless collection of primitive functions is called for. (As standard practice, we always include and its complex extensions to the trigonometric functions, as primitives in our toolbox.)

But the hard mathematical reality does not end here, because even when solution formulas do exist, finding them may call for an ace detective. Only for certain classes of differential equations, such as the linear ones, do we have systematic solution methods.

The picture changes, however, if we let the formulas contain an infinite number of operations. Then the arithmetic operators give a far-reaching base for defining new functions. In fact, as you can verify, the power series

which we view as an “infinite polynomial” over the time parameter t, exactly satisfies our equations for exponential motion, and This power series therefore defines By the way, applying it to the input 1 produces a definition for the transcendental number :

Computational approach

Let’s leave aside our troubles with formulas, and consider the computational approach. For broad classes of differential equations, there are approximation algorithms that be successfully applied.

For starters, any power series that satisfies a differential equation may work for a simple approximation method. If a series is known to converge over some range of inputs, then one can approximate the value at those points by stopping the computation after a finite number of terms.

But the standard methods work directly with the equations, provided that they can be put into the right form. The simplest one is called Euler’s method. It works over a sampling grid of points separated by some small number . Let’s take the case where we have a first-order equation in explicit form, which means that for some function

We begin with the initial value . Applying we get Then for the interval from 0 to ,we use a linear approximation for , by assuming that the derivative remains constant at That gives Next, and etc. Formally,

Applying this to our exponential equation, where we get:

Hence:

So the approximation method gives a discrete exponential growth, which converges to a continuous exponential in the limit as the mesh size goes to zero.

Note, the case we just considered has more generality than might appear at first, because (1) the ideas here are easily extended to systems of explicit first order equations, and (2) higher-order equations that are “explicit” in an extended sense—meaning that the highest-order derivative is expressed as a function of time, of the variable, and of the lower-order derivatives—can be converted into an equivalent system of explicit first-order equations.

The challenging world of differential equations

So, is our cup half-empty or half-full? We have no toolbox of primitive formulas for building the solutions to all differential equations by finite compositions. And even for those which can be solved by formulas, there is no general method for finding the solutions. That is how the cookie crumbles. But on the positive side, there is an array of theoretical tools for analyzing and solving important classes of differential equations, and numerical methods can be applied in many cases.

The study of differential equations leads to some challenging problems, such as the Navier-Stokes equations, which describe the flow of fluids.

These are partial differential equations involving flow velocity, pressure, density and external forces (such as gravity), all of which vary over space and time. There are non-linear (multiplicative) interactions between these variables and their spatial and temporal derivatives, which leads to complexity in the solutions.

At high flow rates, this complexity can produce chaotic solutions, which involve complex behavior at a wide range of resolution scales. This is turbulence. Here is an insightful portrait of turbulence, by Leonardo da Vinci, whose studies in turbulence date back to the 15th Century.

Turbulence, which has been described by Richard Feynman as the most important unsolved problem of classical physics, also presents a mathematical puzzle. The general existence of solutions to the Navier-Stokes equations remains unsettled. This is one of the “Millennium Prize Problems”, for which a one million dollar prize is offered: in three dimensions, given initial values for the velocity and scalar fields, does there exist a solution that is smooth and everywhere defined? There are also complications with grid-based numerical methods, which will fail to produce globally accurate results if the solutions contain details at a smaller scale than the grid mesh. So the ubiquitous phenomenon of turbulence, which is so basic to the movements of the atmosphere and the seas, remains an open case.

But fortunately we have enough traction with differential equations to proceed directly with the rate equations for Petri nets. There we will find illuminating equations, which are the subject of both major theorems and open problems. They are non-linear and intractable by formula-based methods, yet, as we will see, they are well handled by numerical methods.

Probability Theory and the Undefinability of Truth

In 1936 Tarski proved a fundamental theorem of logic: the undefinability of truth. Roughly speaking, this says there’s no consistent way to extend arithmetic so that it talks about ‘truth’ for statements about arithmetic. Why not? Because if we could, we could cook up a statement that says “I am not true.” This would lead to a contradiction, the Liar Paradox: if this sentence is true then it’s not, and if it’s not then it is.

This is why the concept of ‘truth’ plays a limited role in most modern work on logic… surprising as that might seem to novices!

However, suppose we relax a bit and allow probability theory into our study of arithmetic. Could there be a consistent way to say, within arithmetic, that a statement about arithmetic has a certain probability of being true?

We can’t let ourselves say a statement has a 100% probability of being true, or a 0% probability of being true, or we’ll get in trouble with the undefinability of truth. But suppose we only let ourselves say that a statement has some probability greater than and less than , where Is that okay?

Yes it is, according to this draft of a paper:

• Paul Christiano, Eliezer Yudkowsky, Marcello Herreshoff and Mihaly Barasz, Definability of “Truth” in Probabilistic Logic
(Early draft), 28 March 2013.

But there’s a catch, or two. First there are many self-consistent ways to assess the probability of truth of arithmetic statements. This suggests that the probability is somewhat ‘subjective’ . But that’s fine if you think probabilities are inherently subjective—for example, if you’re a subjective Bayesian.

A bit more problematic is this: their proof that there exists a self-consistent way to assess probabilities is not constructive. In other words, you can’t use it to actually get your hands on a consistent assessment.

Fans of game theory will be amused to hear why: the proof uses Kakutani’s fixed point theorem! This is the result that John Nash used to prove games have equilibrium solutions, where nobody can improve their expected payoff by changing their strategy. And this result is not constructive.

In game theory, we use Kakutani’s fixed point theorem by letting each player update their strategy, improving it based on everyone else’s, and showing this process has a fixed point. In probabilistic logic, the process is instead that the thinker reflects on what they know, and updates their assessment of probabilities.

The statement

I have not yet carefully checked the proof of Barasz, Christiano, Herreshoff and Yudkowsky’s result. Some details have changed in the draft since I last checked, so it’s probably premature to become very nitpicky. But just to encourage technical discussions of this subject, let me try stating the result a bit more precisely. If you don’t know Tarski’s theorem, go here:

• Tarski’s undefinability theorem, Wikipedia.

I’ll assume you know that and are ready for the new stuff!

The context of this work is first-order logic. So, consider any language in first-order logic that lets us talk about natural numbers and also rational numbers. Let be the language with an additional function symbol thrown in. We require that be a rational number whenever is a natural number. We want to stand for the probability of the truth of the sentence whose Gödel number is This will give a system that can reflect about probability that what it’s saying is true.

So, suppose is some theory in the language How can we say that the probability function has ‘reasonable opinions’ about truth, assuming that the axioms of are true?

The authors have a nice way of answering this. First they consider any function assigning a probability to each sentence of They say that is coherent if there is a probability measure on the set of models of such that is the measure of the set of models in which is satisfied. They show that is coherent iff these three conditions hold:

1) for all sentences

2) for each tautology.

3) for each contradiction.

(By the way, it seems to me that 1) and 2) imply and thus 3). So either they’re giving a slightly redundant list of conditions because they feel in the mood for it, or they didn’t notice this list was redundant, or it’s not and I’m confused. It’s good to always say a list of conditions is redundant if you know it is. You may be trying to help your readers a bit, and it may seem obvious to you, but it you don’t come out and admit the redundancy, you’ll make some of your readers doubt their sanity.)

(Also by the way, they don’t say how they’re making the set of all models into a measurable space. But I bet they’re using the σ-algebra where all subsets are measurable, and I think there’s no problem with the fact that this set is very large: a proper class, I guess! If you believe in the axiom of universes, you can just restrict attention to ‘small’ models… and your probability measure will be supported on a countable set of models, since an uncountable sum of positive numbers always diverges, so the largeness of the set of these models is largely irrelevant.)

So, let’s demand that be coherent. And let’s demand that whenever the sentence is one of the axioms of

At this point, we’ve got this thing that assigns a probability to each sentence in our language. We’ve also got this thing in our language, such that is trying to be the probability of the truth of the sentence whose Gödel number is But so far these two things aren’t connected.

To connect them, they demand a reflection principle: for any sentence and any rational numbers

Here is the Gödel number of the sentence So, this principle says that if a sentence has some approximate probability of being true, the thinker—as described by —knows this. They can’t know precise probabilities, or we’ll get in trouble. Also, making the reflection principle into an if and only if statement:

is too strong. It leads to a contradictions, very much as in Tarski’s original theorem on the undefinability of truth! However, in the latest draft of the paper, the authors seem to have added a weak version of the converse to their formulation of the reflection principle.

Anyway, the main theorem they’re claiming is this:

Theorem (Barasz, Christiano, Herreshoff and Yudkowsky). There exists a function assigning a probability to each sentence of such that

1) is coherent,

2) whenever the sentence is one of the axioms of

and

3) the reflection principle holds. 

Game Theory (Part 20)

Last time we tackled von Neumann’s minimax theorem:

Theorem. For every zero-sum 2-player normal form game,

where ranges over player A’s mixed strategies and ranges over player B’s mixed strategies.

We reduced the proof to two geometrical lemmas. Now let’s prove those… and finish up the course!

But first, let me chat a bit about this theorem. Von Neumann first proved it in 1928. He later wrote:

As far as I can see, there could be no theory of games … without that theorem … I thought there was nothing worth publishing until the Minimax Theorem was proved.

Von Neumann’s gave several proofs of this result:

• Tinne Hoff Kjeldesen, John von Neumann’s conception of the minimax theorem: a journey through different mathematical contexts, Arch. Hist. Exact Sci. 56 (2001) 39–68.

In 1937 he gave a proof which became quite famous, based on an important result in topology: Brouwer’s fixed point theorem. This says that if you have a ball

and a continuous function

then this function has a fixed point, meaning a point with

You’ll often seen Brouwer’s fixed point theorem in a first course on algebraic topology, though John Milnor came up with a proof using just multivariable calculus and a bit more.

After von Neumann proved his minimax theorem using Brouwer’s fixed point theorem, the mathematician Shizuo Kakutani proved another fixed-point theorem in 1941, which let him get the minimax theorem in a different way. This is now called Kakutani fixed-point theorem.

In 1949, John Nash generalized von Neumann’s result to nonzero-sum games with any number of players: they all have Nash equilibria if we let ourselves use mixed strategies! His proof is just one page long, and it won him the Nobel prize!

Nash’s proof used the Kakutani fixed-point theorem. There is also a proof of Nash’s theorem using Brouwer’s fixed-point theorem; see here for the 2-player case and here for the n-player case.

Apparently when Nash explained his result to von Neumann, the latter said:

That’s trivial, you know. That’s just a fixed point theorem.

Maybe von Neumann was a bit jealous?

I don’t know a proof of Nash’s theorem that doesn’t use a fixed-point theorem. But von Neumann’s original minimax theorem seems to be easier. The proof I showed you last time comes from Andrew Colman’s book Game Theory and its Applications in the Social and Biological Sciences. In it, he writes:

In common with many people, I first encountered game theory in non-mathematical books, and I soon became intrigued by the minimax theorem but frustrated by the way the books tiptoed around it without proving it. It seems reasonable to suppose that I am not the only person who has encountered this problem, but I have not found any source to which mathematically unsophisticated readers can turn for a proper understanding of the theorem, so I have attempted in the pages that follow to provide a simple, self-contained proof with each step spelt out as clearly as possible both in symbols and words.

There are other proofs that avoid fixed-point theorems: for example, there’s one in Ken Binmore’s book Playing for Real. But this one uses transfinite induction, which seems a bit scary and distracting! So far, Colman’s proof seems simplest, but I’ll keep trying to do better.

The lemmas

Now let’s prove the two lemmas from last time. A lemma is an unglamorous result which we use to prove a theorem we’re interested in. The mathematician Paul Taylor has written:

Lemmas do the work in mathematics: theorems, like management, just take the credit.

Let’s remember what we were doing. We had a zero-sum 2-player normal-form game with an payoff matrix . The entry of this matrix says A’s payoff when player A makes choice and player B makes choice . We defined this set:

For example, if

then looks like this:

We assumed that

This means there exists with

and this implies that at least one of the numbers must be positive. So, if we define a set by

then can’t be in this set:

In other words, the set is empty.

Here’s what and look like in our example:

Next, we choose a point in and a point in :

• let be a point in that’s as close as possible to

and

• let be a point in that’s as close as possible to

These points and need to be different, since is empty. Here’s what these points and the vector look like in our example:

To finish the job, we need to prove two lemmas:

Lemma 1. for all and for at least one

Proof. Suppose is any point in whose coordinates are all the same those of except perhaps one, namely the th coordinate for one particular choice of By the way we’ve defined and , this point can’t be closer to than is:

This means that

But since except when this implies

Now, if we can take In this case we get

so On the other hand, if we can take and get

which simplifies to

But and so this can only be true if

In short, we know that either

•

or

• and

So, either way we get

Since was arbitrary, this implies

which is the first thing we wanted to show. Also, either way we get

which is the second thing we wanted. Finally, but we know so

for at least one choice of And this is the third thing we wanted!   █

Lemma 2. If is any point in , then

Proof. Let’s write

for short. For any number between and , the point

is on the line segment connecting the points and Since both these points are in , so is this point because the set is convex. So, by the way we’ve defined and , this point can’t be closer to than is:

This means that

With some algebra, this gives

Since we can make as small as we want, this implies that

or

or

By Lemma 1 we have and the dot product of any vector with itself is nonnegative, so it follows that

And this is what we wanted to show!   █

Conclusion

Proving lemmas is hard work, and unglamorous. But if you remember the big picture, you’ll see how great this stuff is.

We started with a very general concept of two-person game. Then we introduced probability theory and the concept of ‘mixed strategy’. Then we realized that the expected payoff of each player could be computed using a dot product! This brings geometry into the subject. Using geometry, we’ve seen that every zero-sum game has at least one ‘Nash equilibrium’, where neither player is motivated to change what they do—at least if they’re rational agents.

And this is how math works: by taking a simple concept and thinking about it very hard, over a long time, we can figure out things that are not at all obvious.

For game theory, the story goes much further than we went in this course. For starters, we should look at nonzero-sum games, and games with more than two players. John Nash showed these more general games still have Nash equilibria!

Then we should think about how to actually find these equilibria. Merely knowing that they exist is not good enough! For zero-sum games, finding the equilibria uses a subject called linear programming. This is a way to maximize a linear function given a bunch of linear constraints. It’s used all over the place—in planning, routing, scheduling, and so on.

Game theory is used a lot by economists, for example in studying competition between firms, and in setting up antitrust regulations. For that, try this book:

• Lynne Pepall, Dan Richards and George Norman, Industrial Organization: Contemporary Theory and Empirical Applications, Blackwell, 2008.

For these applications, we need to think about how people actually play games and make economic decisions. We aren’t always rational agents! So, psychologists, sociologists and economists do experiments to study what people actually do. The book above has a lot of case studies, and you can learn more here:

• Andrew Colman, Game Theory and its Applications in the Social and Biological Sciences, Routledge, London, 1982.

As this book title hints, we should also think about how game theory enters into biology. Evolution can be seen as a game where the winning genes reproduce and the losers don’t. But it’s not all about competition: there’s a lot of cooperation involved. Life is not a zero-sum game! Here’s a good introduction to some of the math:

• William H. Sandholm, Evolutionary game theory, 12 November 2007.

For more on the biology, get ahold of this classic text:

• John Maynard Smith, Evolution and the Theory of Games, Cambridge University Press, 1982.

And so on. We’ve just scratched the surface!

Game Theory (Part 19)

Okay, we’re almost done! We’ve been studying Nash equilibria for zero-sum 2-player normal form games. We proved a lot of things about them, but now we’ll wrap up the story by proving this:

Grand Theorem. For every zero-sum 2-player normal-form game, a Nash equilibrium exists. Moreover, a pair of mixed strategies for the two players is a Nash equilibrium if and only if each strategy is a maximin strategy.

Review

Let’s remember what we’ve proved in Part 16 and Part 18:

Theorem 1. For any zero-sum 2-player normal form game,

Theorem 2. Given a zero-sum 2-player normal form game for which a Nash equilibrium exists, we have

    ★

Theorem 3. If is a Nash equilibrium for a zero-sum 2-player normal-form game, then is a maximin strategy for player A and is a maximin strategy for player B.

Theorem 4. Suppose we have a zero-sum 2-player normal form game for which ★ holds. If is a maximin strategy for player A and is a maximin strategy for player B, then is a Nash equilibrium.

The plan

Today we’ll prove two more results. The first one is easy if you know some topology. The second one is the real heart of the whole subject:

Theorem 5. For every zero-sum 2-player normal-form game, a maximin strategy exists for each player.

Theorem 6. For every zero-sum 2-player normal-form game, ★ holds.

Putting all these results together, it’s easy to get our final result:

Grand Theorem. For every zero-sum 2-player normal-form game, a Nash equilibrium exists. Moreover, a pair of mixed strategies for the two players is a Nash equilibrium if and only if each strategy is a maximin strategy.

Proof. By Theorem 6 we know that ★ holds. By Theorem 5 we know that there exist maximin strategies for each player, say and . Theorem 4 says that if and are maximin strategies and ★ holds, then is a Nash equilibrium. So, a Nash equilibrium exists.

Moreover, if is any Nash equilibrium, Theorem 3 says and are maximin strategies. Conversely, since ★ holds, Theorem 4 says that if and are maximin strategies, is a Nash equilibrium.   █

Minimax strategies exist

Okay, let’s dive in and get to work:

Theorem 5. For every zero-sum 2-player normal-form game, a maximin strategy exists for each player.

Proof. We’ll prove this only for player A, since the proof for player B is similar. Remember that a maximin strategy for player A is a mixed strategy that maximizes A’s security level, which is a function

So, we just need to show that this function really has a maximum. To do this, we note that

is a continuous function defined on a compact set. As mentioned at the start of Part 17, this guarantees that has a maximum.   █

I apologize if this proof is hard to understand. All this stuff is standard if you know some topology, and a huge digression if you don’t, so I won’t go through the details. This is a nice example of how topology can be useful in other subjects!

The key theorem

Now we finally reach the heart of the whole subject: von Neumann’s minimax theorem. Our proof will be a condensed version of the one in Andrew Colman’s 1982 book Game Theory and its Applications in the Social and Biological Sciences.

Theorem 6. For every zero-sum 2-player normal-form game,

    ★

holds.

Proof. Let’s write

and

Our goal is to prove ★, which says By Theorem 1 we know

So, we just need to prove

Here’s how we will do this. We will prove

Since we’ll prove this for any game of the sort we’re studying, it’ll be true even if we add some real number to each entry of the payoff matrix Doing this adds to the expected payoff so it adds to and So, it will follow that

for any real number and this implies

So, let’s get going.

Assume To prove that , remember that

To show this is greater than or equal to zero, we just need to find some mixed strategy for player A such that

In other words, we need to find such that

    ★★

for all mixed strategies for player B.

How can we find for which this ★★ is true? The key is to consider the set

For example, if

then looks like this:

Since , for any we have

so there must exist with

Since is a mixed strategy, we have for all But since we’ve just seen

at least one of the numbers must be positive. In other words, if we define a set by

then can’t be in this set:

So, we’ve seen that no point in can be in :

Here’s what it looks like in our example:

Now the trick is to:

• let be a point in that’s as close as possible to

and

• let be a point in that’s as close as possible to

We need to use a bit of topology to be sure these points exist, since it means finding the minima of certain functions (namely, distances). But let’s not worry about that now! We’ll complete the proof with two lemmas:

Lemma 1. for all and for at least one

Lemma 2. If is any point in , then

Here’s what the points and and the vector look like in our example:

Check to see that Lemmas 1 and 2 are true in this example! We’ll prove the lemmas later; right now let’s see how they get the job done.

First, by Lemma 1, the numbers are nonnegative and at least one is positive. So, we can define a mixed strategy for player A by defining

where is a number chosen to make sure (Remember, the probabilities must be and must sum to 1.) In other words,

Now, for any mixed strategy for player B, we have and thus by Lemma 1

Dividing by , we get

for all But this is ★★, which is what we wanted to prove! So we are done!   █

I will give the proofs of Lemmas 1 and 2 in the next part.

Game Theory (Part 18)

We’re talking about zero-sum 2-player normal form games. Last time we saw that in a Nash equilibrium for a game like this, both players must use a maximin strategy. Now let’s try to prove the converse!

In other words: let’s try to prove that if both players use a maximin strategy, the result is a Nash equilibrium.

Today we’ll only prove this is true if a certain equation holds. It’s the cool-looking equation we saw last time:

Last time we showed this cool-looking equation is true whenever our game has a Nash equilibrium. In fact, this equation is always true. In other words: it’s true for any zero-sum two-player normal form game. The reason is that any such game has a Nash equilibrium. But we haven’t showed that yet.

So, let’s do what we can easily do.

Maximin strategies give Nash equilibria… sometimes

Let’s start by remembering some facts we saw in Part 16 and Part 17.

We’re studying a zero-sum 2-player normal form game. Player A’s payoff matrix is , and player B’s payoff matrix is

We saw that a pair of mixed strategies one for player A and one for player B, is a Nash equilibrium if and only if

1) for all

and

2) for all

We saw that is a maximin strategy for player A if and only if:

We also saw that is a maximin strategy for player B if and only if:

With these in hand, we can easily prove our big result for the day. We’ll call it Theorem 4, continuing with the theorem numbers we started last time:

Theorem 4. Suppose we have a zero-sum 2-player normal form game for which

    ★

holds. If is a maximin strategy for player A and is a maximin strategy for player B, then is a Nash equilibrium.

Proof. Suppose that is a maximin strategy for player A and is a maximin strategy for player B. Thus:

and

But since ★ holds, the right sides of these two equations are equal. So, the left sides are equal too:

    ★★

Now, since a function is always less than or equal to its maximum value, and greater than or equal to its minimum value, we have

But ★★ says the quantity at far left here equals the quantity at far right! So, the quantity in the middle must equal both of them:

    ★★★

By the definition of minimum value, the first equation in ★★★:

says that

for all This is condition 2) in the definition of Nash equilibrium. Similarly, by the definition of maximum value, the second equation in ★★★:

says that

for all This is condition 1) in the definition of Nash equilibrium. So, the pair is a Nash equilibrium. █

Game Theory (Part 17)

Last time we saw the official definition of maximin strategy. Now we’ll prove something really important. In a Nash equilibrium for a zero-sum game, both players must be using a maximin strategy!

To prove this we will need to look at a lot of maxima and minima. We will always assume these maxima and minima exist. For what we’re doing, this is true. This can be proved using an important result from topology: given a continuous real valued function on a compact set it has a minimum and a maximum. If you haven’t learned this yet… well, I hope you do by the time you get a degree in mathematics.

But now is not the time to talk about this. Let’s dive in!

Nash equilibria give maximin strategies

We start with a cool-looking inequality:

Theorem 1. For any zero-sum 2-player normal form game,

Proof. Since a function is always greater than or equal to its minimum value, for any mixed strategies and we have

If one function is another, its maximum value is the other function’s maximum value. So, the above inequality gives

The right side here is just a number; the left side is a function of . Since this function is always greater than or equal to the right side, so is its minimum:

  █

Next, we’ll show this cool-looking inequality becomes an equation when a Nash equilibrium exists. In fact a Nash equilibrium always exists, but we haven’t shown this yet. So:

Theorem 2. Given a zero-sum 2-player normal form game for which a Nash equilibrium exists,

Proof. Suppose a Nash equilibrium exists. Then for any mixed strategy for player A, we have

since A can’t improve their payoff by switching their mixed strategy. Similarly, for any mixed strategy for player B, since B can’t improve their payoff by switching their mixed strategy. But so this says

Combining these two inequalities, we get

for all The minimum of the left side over all must be greater than or equal to the right side, which doesn’t depend on

Now the maximum of the right side over all must be less than or equal to the left side, which doesn’t depend on

It follows that

The middle inequality here is the one we saw a moment ago. The first inequality comes from the fact that the maximum value of a function is greater than or equal to any of its values:

so

And the last inequality comes from the fact that the values of a function are always greater than or equal to its minimum value:

so

Putting all these inequalities together, we get

On the other hand, Theorem 1 gives an inequality pointing the other way:

So, the two sides must be equal:

which is what we were trying to show!   █

What’s the point of this cool-looking equation? One point is it connects the terms ‘minimax’ and ‘maximin’. There’s a lot more to say about it. But right now, we need it for one big thing: it lets us prove that in a Nash equilibrium for a zero-sum game, both players must be using a maximin strategy!

Theorem 3. If is a Nash equilibrium for a zero-sum 2-player normal-form game, then is a maximin strategy for player A and is a maximin strategy for player B.

Proof. Let’s assume that is a Nash equilibrium. We need to show that is a maximin strategy for player A and is a maximin strategy for player B.

First let’s remember some things we saw in the proof of Theorem 2. We assumed that is a Nash equilibrium, and we showed

If this looks confusing, go back to the proof of Theorem 2. But now look at the beginning and the end of this chain of inequalities. We saw in Theorem 2 that they’re equal! So all the stuff in the middle has to be equal, too. In particular,

Last time we saw this means that is a maximin strategy for player A. Also,

Last time we saw this means that that is a maximin strategy for player B.   █

Whew! That was quite a workout!

But we’re on a mission here, and we’re not done. We’ve shown that if is a Nash equilibrium, and are maximin strategies. Next time we’ll try to show the converse: if and are maximin strategies, then is a Nash equilibrium.