What do Brazil, Auctions, and Multi-Threading Have in Common?

On the different guises that a single mathematical concept can have

I have argued before that one of the things that makes math math is the fact that context doesn’t matter—structure does. You can define a certain mathematical concept, and then have it appear in many different contexts, because the logical structure is the same, even if all of the physical details are completely different.

What is Math?

I think I have a good example that doesn’t get talked about much. Let me introduce you to tropical semi-rings.

The min tropical semi-ring is defined as follows: start with the real numbers ℝ, and adjoin a formal symbol ∞, which you think of as being larger than any real number. Then define two operations:

1. x⊕y=min(x,y)

2. x⊗y=x+y.

Surprisingly, ⊕ acts like addition, and ⊗ acts like multiplication, in the following sense:

1. These two operations are associative and commutative.

2. Both have an identity element. (∞ for ⊕, 0 for ⊗.)

3. ⊗ distributes over ⊕.

4. x⊗∞=∞, for all x. (Since ∞ is the identity for ⊕, this is the analog of the statement that x⋅0=0.)

Similarly, one defines the max tropical semi-ring by starting with ℝ and adjoining a formal symbol -∞, which you think of as smaller than any real number, and you define two operations

1. x⊕y=max(x,y)

2. x⊗y=x+y.

Here, again, ⊕ acts like addition, and ⊗ acts like multiplication, in the same sense.

This might seem like a curiosity, but it is actually deeply practical. Here’s one reason why: suppose that you have a collection of physical processes, each of which takes a certain amount of time to complete, but some of these processes can run concurrently, whereas others depend on each other (so one has to finish before the other begins).

This is, for instance, how multithreading on a computer works: you have a certain task, that you split up into smaller sub-tasks. Some of those sub-tasks can be run independently of each other, so you can run them simultaneously. For some of these sub-tasks, however, you need to know the output of one before you can feed it into the next.

How do you compute the total time required for all processes to complete? If x and y are the times for two such processes, and they can be run simultaneously, then the total time is max(x,y). If you have to run one and then the other, it is x+y.

Hold on—those are just the operations of the max tropical semi-ring! So, questions about running times of computer processes can be phrased as questions about the algebraic properties of the max tropical semi-ring.

For this and other reasons (for instance, they connect abstract algebra with finite automata), the tropical semi-rings are actually quite applied in computer science—they are, indeed, named after Brazilian computer scientist Imre Simon, who initiated their study. (Because Brazil is tropical, I suppose.)

That field is now known as tropical geometry—it’s quite young, having consolidated really just in the 1990s.¹ I learned of it quite accidentally—when I was in graduate school, Sam Payne was there, and he had a fairly robust algebraic and tropical geometry group.

What are those two fields, and what is the connection between them? In classical algebraic geometry, you might be given a polynomial like y³+4xy+x³+x+2, and you would study it by considering its zero set, in this case a curve.

More generally, this is something called an algebraic variety. There is a beautiful interplay between the geometry and the algebra here—studying one gives insights into the other, and if you define everything just right, there really ceases to be any true difference between the two. In tropical geometry, you define the tropicalization of such an algebraic variety. To start, you take your polynomial, replace + and × with ⊕ and ⊗, and drop all constants.² So, in our example, we have

\(\begin{align*} y^3&+4xy+x^3+x+2 \\ &=y\cdot y \cdot y+4\cdot x\cdot y+x\cdot x\cdot x+x+2 \\ &\rightsquigarrow \max(3y,x+y,3x,x,2). \end{align*}\)

This is a function of two variables—the set of points where it fails to be differentiable is a collection of lines.

On the left is the graph of the tropical polynomial; on the right is the corresponding tropical curve.

There’s a fun little Mathematica demonstration that allows graphing arbitrary tropical curves. Below is an example.

The tropical curve for max(a₁x+b₁y+c₁,… a₆x+b₆y+c₆)

You might notice that tropical curves are in many ways much simpler than algebraic curves. Here’s the amazing thing: there’s actually a deep interplay between the classical picture and the tropical picture. You can learn a lot about a curve from its tropicalization and vice versa. There are many, many theorems in algebraic geometry that have tropical analogs; conversely, there are theorems about algebraic geometry that have been proved by studying the tropical picture.

But what applications does this have? There’s a very surprising one, but before I get to that, I want to set the stage—let’s go back to the financial crisis of 2007-2008.

The exact causes of the crisis are complex and would be better described by an economist. However, one of the key things that happened is that housing prices in the US suddenly crashed, taking with them the value of any financial instrument (such as bundled loan portfolios) that had been backed by mortgages on those houses. This latter effect was no longer just a US problem—it was a crisis for the entire global financial market as banks and other financial institutions suddenly found themselves on the verge of bankruptcy.

One of the resulting issues was that there was a severe credit crunch—it became significantly harder to obtain a loan from a bank. A possible solution to this for the government was to buy up higher-risk assets, such as the aforementioned mortgage-backed securities, or to offer loans with those higher-risk assets as collateral. This would give banks the money they needed to continue offering loans. This is precisely what the UK decided to do.

In the fall of 2007, the Bank of England tried to implement this kind of solution: they wanted to offer loans with these kinds of toxic assets as collateral. The trouble was determining exactly what rates they had to offer; there were many different institutions involved with many different kinds of assets, so it would not be possible to give a “one-size-fits-all” type of pricing. So, the Bank decided to run an auction. After four unsuccessful attempts to make this work, the then-Governor of the Bank contacted Paul Klemperer, Edgeworth Professor of Economics at Oxford, to see if he could design an efficient system. One of the important constraints was that this auction had to work fast, in just a matter of minutes—otherwise, the valuation given to some of these toxic assets would potentially influence the market’s valuation of some of the other assets.

This led Professor Klemperer to invent the Product Mix Auction. The underlying theory behind this auction was properly developed and generalized by Paul Klemperer and Elizabeth Baldwin in their co-authored paper… Tropical Geometry to Analyse Demand.

Ah. Here’s a diagram from that paper.

Taken from page 24

That’s a tropical curve! This was the fundamental insight of Baldwin and Klemperer: demand for goods can be gainfully described via tropical curves and you can use results from tropical geometry to better understand the underlying economics. Quoting directly from the introduction to their paper:

Economists mostly think about agents’ demands by focusing on the direct utility functions. We instead begin by focusing on the geometric structure of the regions of price space in which an agent demands different bundles. Our crucial observation is that dividing price space in this way creates precisely the geometric structure which is studied in the recently-developed, non-Euclidean, branch of algebraic geometry called “tropical geometry”. We can therefore use the tools of convex and tropical geometry, such as the duality between the geometric structure of an agent’s demand in price space and the same agent’s demand in quantity space, to obtain new insights about demand. Moving backwards and forwards between the dual representations of demand in price space and quantity space improves our understanding of both.

For example, it is much easier to aggregate individual demands in price space, but translating aggregate demand back into quantity space allows a strong theorem that encompasses and extends many existing results about when a competitive equilibrium exists.

On the other hand, if we start from the (direct) valuation function in quantity space, our methods for translating to the dual in price space quickly reveal the key properties of demand. Many existing results in demand theory can be understood more readily, and developed more efficiently, using our tropical-geometric perspective than using traditional methods.

1. It is a testament to how ancient and deep mathematics is as a discipline that people can sincerely say that a field of study is “very young” when it is over 30 years old.

2. In general, you apply a valuation to the constants, such as the p-adic ones, but for simplicity, I am just using the trivial valuation that maps all complex numbers to 0.