Who really wins the Olympics?: some optimization and geometry

With the 2024 Summer Olympics going on, the New York Times had this wonderful visualization:

The plot shows, for different weights assigned to the silver and gold medals, how the United States would rank compared to different countries. Well, this specific plot is a bit boring because it seems like the United States just dominates. Indeed, when that screenshot was taken, the United States had more gold, more silver, and more bronze than any other country: so under any weighting system, it would always rank first. Here's a couple other countries just to see something interesting.

On the NYT website, you can play around with the visualization and experiment with different weights. I don't know how they created such a plot but my hunch is that they did it by sampling, i.e., by testing each point in a mesh grid of weights (although I'd be interested to hear more). When I saw the visualization, two questions came to mind:

1. Given the data on medal counts, what is the highest/lowest rank that a given country can achieve over some range of weights?
2. Given a country and a rank, can we get an analytic representation of the weight space over which the country achieves that rank?

The optimization problem

The optimization problem is to find the lowest and highest rank a country can achieve, knowing the medal counts of all countries. Let's fix some definitions. Let there be \(n\) countries, numbered \(1,2,..n\). The rank of a country will be defined as the count of the number of countries with a score strictly greater than it, plus one. This handles ties in the usual convention (e.g., if two countries are tied for first, then zero countries beat them, so they both get rank 1; and the next country would have rank 3). Also, the plus one doesn't matter for the optimization problem, but we will include it so we get more human-readable answers. The count of gold, silver, and bronze medals for a country \(i\) are denoted \(G_i, S_i, B_i\) respectively.

The variables we are interested in are the weight of a gold medal, \(w_g\), and the weight of a silver medal, \(w_s\). Thus, the score of a country \(i\) is: \(w_g G_i + w_s S_i + B_i\). Note the weights of gold and silver are relative to bronze, in the sense that we just assign bronze a weight of 1. Also, my specification differs slightly from the NYT visualization: they define the weight of gold relative to the weight of silver. As we will see, defining it the way I have makes it a linear problem, and thus much more easily solved. We have the restrictions that \(1 \leq w_s \leq w_g \le 20\), i.e., gold is more valuable the silver, and for our solution, we arbitrarily bound the weights to be at most 20, but this choice is inconsequential.

Fix a country \(k\). We want to find the lowest and highest rank that this country \(k\) can achieve. (Note: by "lowest", I mean numerically: e.g., rank 1 is the lowest possible rank, although the usual use of this word would mean e.g., last place).

In order to count the number of countries that beat country \(k\), we can introduce binary variables that capture whether a country \(i\) has a higher score than \(k\). For each country \(i \neq k\), introduce a variable \(z_i\), which is 1 if and only if \(score_i > score_k\). Then, the rank of country \(k\) is simply \(1 + \sum_{i \neq k} z_i\). This objective is of course linear in the \(z\) variables.

But, how can we handle the definition of the \(z\) variables? We can use the usual big-M trick, taught in pretty much every intro to linear optimization class. Let \(M\) be a "big" number and \(\epsilon\) be some tolerance. Then, for each \(i \neq k\), we can write \(score_i \geq score_k + \epsilon - M(1-z_i)\) and \(score_i \leq score_k + M z_i\).

Putting all of this together, all of our constraints are linear, our objective is linear, and we have some continuous and some binary variables. So, what we have is a mixed-integer linear program! Explicitly, our full optimization problem is as follows: \[ \begin{align} & \text{optimize} \; 1 + \sum_{i \neq k} z_i \\ & \text{s.t.} \\ & score_i = w_g G_i + w_s S_i + B_i \quad \forall i \\ & score_i \geq score_k + \epsilon - M(1-z_i) \quad \forall i \neq k \\ & score_i \leq score_k + M z_i \quad \forall i \neq k \\ & w_g \geq w_s \\ & w_g, w_s \in [1,20] \\ & z_i \in \{0,1\} \quad \forall i \neq k \end{align} \] Above, "optimize" can be replaced with minimize or maximize, depending on if we want the minimum rank or the maximum rank. This problem is quite easily solved with your favourite linear programming solver, e.g. Gurobi.

An example

Here's some mock data.

I implemented the previous optimization problem in Mathematica (really because I wanted it to work well with the next part of this, the geometry part, but it was honestly a bit painful compared to Gurobi). For each country A to J, I computed the minimum rank (the best possible placement) and the maximum rank (the worst possible placement). To solve all 20 of the optimization problems (min and max for each of the ten countries) took on the order of ~2 seconds. The results are below.

It seems country E is perhaps in the best position! At best, it is first place, and at worst, it is in second place, over the weight space we test. Country F has the widest range, going from first to last across our weight space.

The geometry problem

The geometry problem is: given a country and a rank, can I exactly characterize the region in the weight space over which it achieves that rank? Indeed, the previous optimization problem only told us, e.g., that there exist weights where country E (in the example) is ranked first. But, there would reasonably be multiple weights where this is true. What can we say, geometrically, about this set of weights?

In order to represent our region of interest, I will be finding its cylindrical algebraic decomposition (CAD). I like the way CAD represents regions in multidimensional real space because it can be understood as a tree. I won't go over the details of CAD here, but what that means for our case is that CAD will break up the \(w_s\) in our region of interest into points and intervals, and then over each of these points/intervals, it will characterize \(w_g\) by an (in)equality.

CAD is quite a powerful algorithm, and it can be used to describe any semialgebraic set, i.e., a set defined by Boolean combinations of polynomial equalities and polynomial inequalities. So, using CAD here is a bit like using a nuclear weapon to kill a bug but I'm not sure if there's another way to get the representation I want. Also, the fact that CAD natively handles Boolean expressions and strict inequalities is useful because it means we don't have to use big-M's nor \(\epsilon\) tolerances, and the numerical issues that come with them.

Mathematically, suppose we have a country \(k\), and we want it to achieve rank \(r\). We therefore have the following system: \[ \begin{align} & \sum_{i \neq k} z_i = r - 1 \\ & score_i = w_g G_i + w_s S_i + B_i \quad \forall i \\ & score_i > score_k \implies z_i = 1 \quad \forall i \\ & score_i \leq score_k \implies z_i = 0 \quad \forall i \\ & w_g \geq w_s \\ & w_g, w_s \in [1,20] \end{align} \]

This is indeed a Boolean combination of polynomial equalities and inequalities. Recall that implication has an equivalent form as a disjunction: \(P \implies Q\) is equivalent to \(\neg P \lor Q\), so we have "or"s and "and"s here. More specifically, we have a Boolean combination of linear (in)equalities. Geometrically, that means that the boundaries of our regions of interest are going to be lines! You may be wondering if this contradicts the NYT visualization, where there are clearly curves -- the difference is due to the fact they define the gold weight relative to the silver weight.

I implemented the above in Mathematica. If we construct the CAD of such a system, we'll get an exact description of the weight space we are interested in. Let's again go back to country E, which the optimization problem showed can achieve first place. Solving for the CAD of where E achieves rank 1, we get:

• \(1 \leq w_s \leq \frac{3}{2} \rightarrow \frac{1}{6}(3+4w_s) \leq w_g \leq 20 \)
• \(\frac{3}{2} \lt w_s \lt 20 \rightarrow w_s \leq w_g \leq 20 \)
• \(w_s = 20 \rightarrow w_g=20 \)

Some further geometric facts: such regions are not necessarily convex. In fact, they are not even necessarily connected! If you plot the region where country G achieves rank 6, you get:

I've included the CAD expression as well so you can see why: there's a jump in the \(w_s\) from \(13/12\) to \(1\), which you can see by inspecting the expression.

Putting it all together with Olympic data

I copied the current medal count of the Summer 2024 Olympics, of the top 30 countries, into Mathematica and did the same thing as above. It took a few seconds to solve all 60 of the optimization problems (min/max for each country). The results are below.

It seems in the real world, rankings are rather invariant to changes in weights. The gaps between the best and worst possible is often small, although it gets bigger as you get to lower-medalling countries. The top of the table though is quite tight: for example, the US always stays first, China always stays second. This accords with the NYT visualization!

Now, using the results of the optimization, we can explore a particular rank for a given country. For example, we know that Canada is either rank 10 or rank 11. So, we can attempt to construct the CAD for Canada to achieve rank 10. Unfortunately, Mathematica aborts on me (I'm using Wolfram Cloud). The key issue is that CAD scales horribly with the number of variables (doubly exponential in the general case). In our system, we have the two variables we are interested in, \(w_s, w_g\), but also all the \(z\) variables, which is equal to the number of countries minus one (exclude the chosen country \(k\)). So, in this case, we have 29 \(z\) variables plus the two weight variables, meaning 31 variables. Now, recall that everything in our system is linear, so the complexity is not as bad as in general, and the Mathematica docs claims it uses a specialized version of CAD for this setting via an algorithm of Loos and Weispfenning. However, it still takes too long to compute (for my Wolfram Cloud instance) and aborts.

Closing remarks

This Olympics problem is actually related to something deeper: multi-objective optimization. Often in multi-objective optimization, we try to combine multiple objectives into one objective for ranking purposes, similar to how we weighed the Olympic medals and summed them to make a single score. Namely, we have some function \(f:\mathbb{R{^n \to \mathbb{R}}}\) which maps \(n\) valuations into a single valuation. Now, this choice of \(f\), e.g., Olympic weights, is arbitrary, so we may want to evaluate such a ranking over a whole space of possible \(f\). This is what our optimization problem helps us to elucidate, and as we saw it is easily solvable thanks to the power of mixed-integer linear programming.

On the other hand, the geometry problem was much more difficult computationally. I have a hunch that it may be possible to develop some preprocessing for CAD in this setting that may scale much better. One idea is: we can eliminate \(z\) variables if we can be certain of their value. For example, the USA is always first place, so for any other country, the \(z_{USA}\) variable is always 1, as the USA always beats it. More generally, we can compare min/max ranks of pairs of countries, given by the optimization results, to fix some values of \(z\). I believe that such a procedure would be more broadly applicable to multi-objective optimization.

All the code I used in this post is in this Mathematica notebook.