A map that offers a choice

Where the fixed point escapes takes Brouwer’s theorem apart by removing one hypothesis at a time from the set — drop closed, drop bounded, drop the absence of holes — and each time the point leaves. This weakens the other side of the statement. It keeps the set and changes what a map is.

A rule that assigns to each point a set of points is a correspondence, and it arises whenever a rule is not obliged to pick. The example everything here is about is the best reply in a game: against most of the other side’s mixtures one action is strictly better, so the rule returns one point — and at the mixture that leaves a chooser indifferent, every reply is best, and the rule returns a whole interval.

That is the whole theorem in one picture. A correspondence on a compact convex set, whose values are non-empty convex sets and whose graph is closed, has a point inside its own value. Kakutani proved it in 1941 in a three-page paper. The three pages exist for a specific reason: von Neumann had needed exactly this statement for his 1937 model of an expanding economy, had proved it by an argument running to many pages, and Kakutani’s note observes that the whole thing follows from Brouwer’s theorem by one approximation.

What a closed graph means, and why it is the right hypothesis #

For an ordinary function, continuity is the natural hypothesis. A correspondence has several competing notions of continuity and choosing among them is where the subject’s technicalities live, so the cleanest statement uses none of them: the graph is closed.

The graph is the set of pairs $(x, y)$ with $y$ in the value at $x$. Requiring it to be closed says that if a sequence of points converges and the values chosen at them converge too, the limit value is in the limit point’s value set. Nothing is being assumed about how the value set moves; only that it does not lose its own limits.

That is exactly what a best reply satisfies and what a function’s continuity does not capture. The left-hand graph in the figure jumps, which no continuous function does — and its graph is closed, because the vertical segment at the jump contains everything between the two sides. A function jumping the same way has a graph missing that segment, and the graph is not closed.

So closed-graph is a weakening on one axis and a strengthening on another: it permits jumps, and it requires the jumps to be filled in.

Convexity is the hypothesis that does the work #

The right-hand panel has a closed graph too. Its value at the jump is two intervals, both included, and the graph is closed. What it is not is convex: the value set has a hole in it, and the diagonal passes through the hole.

That is the whole counterexample, and it is worth stating how small it is. The two rules agree at every point except one; at that one point the first offers $[0.12, 0.78]$ and the second offers $[0.12, 0.18]$ and $[0.72, 0.78]$; and the second’s graph misses the diagonal while the first’s meets it.

Why convexity is needed is visible in the proof. Kakutani’s argument approximates the correspondence by an ordinary continuous function: triangulate the set finely, pick one value at each vertex, and interpolate linearly between them. Brouwer’s theorem gives the interpolation a fixed point; taking finer triangulations gives a sequence of these; and the limit is a fixed point of the correspondence, provided the interpolated values lie in the value sets. Interpolating between two chosen values produces a combination of them — and a combination of points of a set lies in the set exactly when the set is convex.

So the convexity is not a technical convenience covering an awkward case. It is what makes an average of two admissible answers admissible, and Brouwer’s theorem is applied to averages.

What it was wanted for #

This is the object Kakutani’s theorem exists for, and the reason the proof of the value of a zero-sum game needed it.

Take any finite game. Let the set be the product of the choosers’ mixture simplexes, which is compact and convex. Let the correspondence send a profile of mixtures to the set of profiles in which each chooser best-replies to what the others are doing. Then:

• the values are non-empty, because a finite game has a best reply to anything — a maximum over finitely many options;
• the values are convex, because if two mixtures are both best replies then so is any mixture of them, the payoff being linear in the mixture;
• the graph is closed, because best-replying is defined by non-strict inequalities and non-strict inequalities survive limits.

Kakutani’s theorem applies, and a fixed point is a profile in which everybody is best-replying to everybody — which is the definition of an equilibrium. That is Nash’s proof, from 1950, and it is one page.

The three bullet points above are exactly the three hypotheses, and each is a one-line check about payoff functions. That correspondence is the reason the theorem has the shape it has: Kakutani wrote the hypotheses that a best reply satisfies.

Convexity, twice over #

There is a second place convexity enters and it is worth separating, because the two are often run together.

The set must be convex. That hypothesis is Brouwer’s already, in the disguised form no holes: the ring is where Brouwer’s theorem fails, and a ring is not convex. Kakutani inherits it unchanged.

The values must be convex. That hypothesis is new and is the one this page is about.

The two are independent and both are needed. A correspondence with convex values on a ring can avoid every point — a rotation does it, with singleton values — and a correspondence with holey values on a disc can avoid every point, as the hero figure’s right-hand panel does on an interval.

And in the game application both are supplied by the same fact. The set of mixtures is convex because a mixture of mixtures is a mixture; the set of best replies is convex because the payoff is linear in the mixture, so the set of maximisers of a linear function is a face and a face is convex. Linearity in the probabilities is doing both jobs, which is why the whole apparatus fits games so exactly and fits almost nothing else without work.

How Nash’s proof avoided the theorem, once #

There is a piece of history worth having, because it says something about how much the theorem is doing.

Nash’s 1950 note in the Proceedings of the National Academy of Sciences proves existence with Kakutani’s theorem in half a page. His 1951 paper in the Annals proves the same thing with Brouwer’s theorem instead, by a construction that removes the correspondence entirely.

The trick is to build an ordinary continuous map whose fixed points are the equilibria. For each chooser and each pure action, let $g$ be how much that chooser would gain by switching entirely to that action, or nought if switching would lose. Then map a profile of mixtures to a new profile in which each action’s probability is increased in proportion to its $g$ and the whole thing renormalised. That map is continuous, it sends the simplex to itself, and its fixed points are exactly the profiles where every gain is nought — which is to say the equilibria.

So the correspondence was avoidable in this instance, and the avoidance cost a page of construction that has to be checked. Two readings of that are available and both are fair.

Kakutani’s theorem is not needed for Nash’s theorem, strictly, and a reader who wants the shortest self-contained account of why games have equilibria should take the 1951 route.

And the correspondence is still the honest object. The 1951 map is an artefact — it has no meaning in the game, nobody adjusts that way, and the only reason to write it down is to be allowed to apply Brouwer. The best-reply correspondence is the thing the equilibrium condition is about, and stating the theorem for it is stating it about the object rather than about a device. The applications in the next section have no such device available, which is why they use Kakutani rather than imitating the 1951 proof.

What is not obtained #

The theorem is an existence result of the purest kind and it is worth being explicit about the cost.

No construction. Kakutani’s proof passes through Brouwer’s, and Brouwer’s proof — whichever one is used — locates nothing. Sperner’s lemma gives an algorithm of a sort, and the algorithm’s cost grows badly with the dimension; finding a Nash equilibrium of a two-player game is now known to be complete for a complexity class that is believed to be intractable, so the difficulty is not an artefact of the proof technique. The gap is the same one Sperner’s lemma’s odd count leaves: the count proves a rainbow triangle exists and following the doors to it can take exponentially long.

No uniqueness. The stag-hunt figure has three crossings. The theorem says at least one, and everything about which one happens is outside it.

And no stability. A fixed point of a correspondence need not attract anything. A chooser adjusting toward a best reply may circle an equilibrium for ever, which is what the replicator flow does in a mixed equilibrium — existence is about a point, and dynamics is a separate question with a separate answer.

Where else a correspondence turns up #

Best replies are the motivating case and they are not the only one. Three others, each of which is a set of maximisers and therefore convex-valued for the same reason.

A demand correspondence. At most prices a consumer has one best bundle; at the prices where two bundles are equally good, the set of best bundles is the segment between them. General-equilibrium existence — Arrow and Debreu, 1954 — is Kakutani applied to exactly that, with the fixed point a price vector at which supply meets demand, and it is the result that made the theorem standard equipment in economics.

A subdifferential. A convex function that is not differentiable at a point has, in place of a derivative, the set of slopes of lines lying under it there — which is a whole interval at a corner and a single number elsewhere. That set is convex and the correspondence has a closed graph, and the fixed-point theory of subdifferentials is what optimisation on non-smooth functions runs on.

A differential inclusion. A mechanical system with friction obeys a law that does not specify a force when the velocity is zero — it specifies a range of forces, any of which keeps the object still. The equations of motion become inclusions rather than equations, and their solvability rests on the same convexity.

The common feature is worth naming: in all four the multi-valuedness appears exactly where something is tied. A best reply is a set at indifference, a demand is a set where two bundles are equal, a subdifferential is a set at a corner, a friction force is a set at rest. The correspondence is what a rule becomes when the thing it optimises stops having a unique answer, and the convexity comes free because ties are between things the rule values equally, and a mixture of two equally-valued things is equally valued.

The other direction in the same theorem #

There is a companion result worth naming, because it makes the shape of Kakutani’s clearer by contrast.

Michael’s selection theorem says that a correspondence with convex values that is lower hemicontinuous admits a continuous selection — a genuine function picking one value at each point, continuously. Given that, Brouwer’s theorem applies to the selection directly and a fixed point follows with nothing new required.

Kakutani’s correspondences do not satisfy that hypothesis. A best reply is upper hemicontinuous and not lower: its value can suddenly become large at the indifference point, and a continuous selection through such a jump does not exist — a function through the left panel’s graph would have to jump.

So the two theorems handle the two ways a correspondence can fail to be a function. One picks a function and reduces to Brouwer; the other cannot pick and argues through approximation. The kind that arises from optimising — a set of maximisers — is always the second kind, because a set of maximisers grows abruptly and shrinks gradually.

One dimension, and a theorem about all of them #

The fixed point is found by a sweep, and a sweep is finite. Each panel is tested at two thousand points and reports the first where the value contains the point. That the right-hand panel has no fixed point anywhere is a fact about the rule, argued in prose; what the figure establishes is that none of two thousand sampled points is one.

One dimension is not the theorem. Everything here is drawn on an interval or in a square, where a graph crossing a diagonal can be seen. The theorem is about a compact convex set in any dimension, and the triangulation argument that proves it has no two-dimensional picture — what the pictures show is the statement, at the one size where the statement is visible.

The best-reply figures are two-by-two. With three actions a chooser’s mixtures form a triangle, the correspondence lives in a four-dimensional product, and the crossing has no side view. Both game figures are drawn at the only size a square accommodates, and the general claim — that every finite game has an equilibrium — is about sizes with no picture.

And nothing here is a dynamic. The crossing is a static condition, and a reader could easily take the two paths as trajectories converging on their intersection. They are not: each path is the set of a chooser’s best replies, drawn all at once, and no point of either is anywhere at any time.

Still open here: finding what is proved to exist #

The existence is settled and complete. Everything unresolved is about producing the point.

Computing a Nash equilibrium of a two-player game is PPAD-complete, a result of 2006, and the class is believed to admit no polynomial algorithm — so a theorem proved in one page describes an object nobody can find at scale. That gap is the sharpest one in this collection between an existence result and a construction, sharper than the ones an existence proof rather than a construction usually opens, because here the non-existence of a method is a theorem rather than an absence of one.

The other direction asks what happens when the hypotheses are relaxed further. Infinite-dimensional versions — the Fan–Glicksberg theorem — cover games with continuous action spaces and are what the mechanism-design literature runs on. And correspondences with non-convex values have their own fixed-point theory, under conditions on how badly the convexity fails; none of it is as clean as the statement above, which is the usual sign that the hypothesis being relaxed was the right one.

What a hypothesis is for #

The habit is to ask which hypothesis a theorem is actually about.

Brouwer’s theorem has four conditions and dropping each in turn shows each one mattering. Kakutani’s has those four and one more, and the extra one is not a technicality bolted on to make a proof work — it is the condition under which averaging two answers gives an answer, which is precisely what the proof does at every step.

A hypothesis that looks like bookkeeping is worth testing by removing it, and the test is the hero figure: two rules differing at one point, one with a fixed point and one without. When the difference is that small and the consequence is that total, the hypothesis was the theorem.