Pete’s problem

It’s not every day that a presidential candidate stumps you with a really interesting math problem, but that’s exactly what Pete Buttigieg did on Tuesday when he sent out the following email to his supporters:

Pete’s Innovation Team handles data, engineering, and analytics responsibilities for the campaign, so you might not be shocked to learn that we have more than a few numbers geeks in the group. And while we’re extremely serious about helping make Pete our next president, we find joy in some strange places…like clever donation amounts.

You might have seen our $20.20 buttons on the website (classic), but we also enjoy $2.70 (for the electoral votes), $46 (for our next president), or $20.55 (for the year when Pete reaches the current age of the current president). But as we started to do our end of year analyses, we decided to get even geekier. We thought up an end of year guessing game, and we want you to be part of the fun.

All you have to do to win is donate the smallest amount that nobody else donates. In other words, suppose you donate $1.00. If someone else playing also donated exactly $1, you both lose. We’ll see if only one player donated $1.01, and so on until we find an amount donated exactly once, and that’s our winner.

This presents a neat problem: let’s say you want to donate once and your goal is to maximize your chances of winning this game. Suppose you expect there to be n other donations (my best guess for n is 50,000). How should you play?

To formalize this a bit: you are trying to maximize your chances of winning per dollar you spend, and so is everyone else. What is the equilibrium strategy?

(Note that this strategy necessarily involves randomness, i.e. it takes the form “draw your bid randomly from a distribution”; otherwise everyone would donate the same amount and no one would win.)

So here’s what I recommend: before reading on, spend a couple minutes and make your best guess at the average donation amount in the equilibrium strategy. For n = 50,000, is it one dollar? Ten? A hundred? How does this amount grow with n? Then, if you’re feeling up for it, try to solve for the equilibrium! Then, read on.

 

 

 

 

 

 

 

 

 

 

The key property of the equilibrium strategy is this: the probability that you win if you donate k cents is proportional to k. That’s because if this is not the case, donors will have an incentive to deviate from the equilibrium: they can get a larger probability of winning per dollar spent by donating a value with a high win-probability-to-money-spent ratio.

This lets us set up an equation to find the equilibrium solution. If you’re interested in the math, read straight ahead; if you want to skip the math and see the result, scroll down to the pretty chart!

 

So, what is the probability that you win if you donate k cents? Two things need to happen:

  • For every i < k, either zero donations or multiple donationd of i cents must be made.
  • No one else makes a donation of exactly k cents.

Define f(i) to be the probability of a donation being exactly i cents (in the equilibrium strategy). Then the probability that not exactly one donation of i cents is made is

1 - n f(i) (1 - f(i))^{n - 1} \approx 1 - n f(i) e^{-nf(i)}.

These probabilities are almost independent for different values of i, so the probability that the first bullet holds is

\prod_{i = 1}^{k - 1} (1 - nf(i)e^{-nf(i)}).

The probability that the second bullet holds is

(1 - f(k))^n \approx e^{-nf(k)}.

Therefore, if we denote with p(k) the probability of winning if you donate k cents, we have

p(k) \approx e^{-nf(k)} \prod_{i = 1}^{k - 1} (1 - nf(i)e^{-nf(i)}).

Somewhat tautologically, we have

p(k + 1) \approx e^{-nf(k + 1)} \prod_{i = 1}^{k} (1 - nf(i)e^{-nf(i)}).

A nice thing about these last two quantities is that they look very similar: they both involve a big product, but the products are almost identical. So let’s see what happens if we divide these two quantities.

\frac{p(k + 1)}{p(k)} \approx e^{-n(f(k + 1) - f(k))} (1 - nf(k)e^{-n f(k)}).

But we have another way of expressing \frac{p(k + 1)}{p(k)} — specifically, it’s just $\frac{k + 1}{k}$, by the “key property” we noted above. Therefore we have

e^{-n(f(k + 1) - f(k))} (1 - nf(k)e^{-n f(k)}) \approx \frac{k + 1}{k}.

We can now solve for f(k + 1) in terms of f(k). I’ll spare you the algebraic manipulation; what you end up getting is

f(k + 1) \approx f(k) + \frac{1}{n} \ln \left( \frac{k}{k + 1}(1 - nf(k)e^{-nf(k)}) \right).

Now, if you wanted you could turn this recursive formula for f(k) into a differential equation: letting y = f(x), we have

y' = \frac{1}{n} \ln \left( \frac{x}{x + 1}(1 - nye^{-ny}) \right).

However, I’m pretty sure this differential equation doesn’t have a nice solution, so it doesn’t really pay to do that. Instead, we can set any particular n we want (I’m going with n = 50,000) and compute the values of f(k) recursively. Except… how do we figure out what f(1) is? Well, we know that \sum_i f(i) = 1 and we can search for the value of f(1) that makes this happen. That’s exactly what I did, and I ended up with the following distribution:

50000_Chart

This is a graph of the probability density function (PDF) of the equilibrium strategy, where the x-axis is in cents.

So, this is pretty interesting! It turns out that you never want to donate more than $48.60. The intuition behind that is: with fifty thousand donors, it’s almost guaranteed that for some donation amount below $48.61, exactly one person will donate that amount, so it never makes sense to donate more than $48.60.1 Let’s let D_{\text{max}}(n) denote the maximum donation that someone playing the equilibrium strategy might donate (so D_{\text{max}}(50000) = \$48.60).

What about the mean of this distribution? If you play the equilibrium strategy, your expected donation is $22.03. Let’s call the expected donation D_{\text{avg}}(n) (so D_{\text{avg}}(50000) = \$22.03).

You might be wondering how D_{\text{max}}(n) and D_{\text{avg}}(n) grow with n. It turns out they grow linearly with \frac{n}{\log n}. In particular, from trying different values of n (as large as 1,000,000), I conjecture the following:

  • Asymptotically with n, we have D_{\text{max}}(n) \to \frac{n}{\ln n}. More formally, \lim_{n \to \infty} \frac{D_{\text{max}}(n) \ln n}{n} = 1.
  • As n gets large, the distribution of f(k) becomes closer and closer to uniform, and so D_{\text{avg}}(n) \to \frac{n}{2 \ln n}.

While this makes a lot of sense now that I’ve spent a while thinking about Pete’s problem, this isn’t the guess I originally made! I expected D_{\text{avg}}(n) to grow roughly as \sqrt{n} (or \sqrt{n} \log n or something). I can’t re-explain my intuition in a way that makes sense, but it was coming from the same \sqrt{n} that appears in the birthday problem.

 

I’d like to end this post with a pitch to the Democratic presidential campaigns. I know you all are coveting endorsements, particularly from publications as influential as the Des Moines Register, the New York Times, and Unexpected Values. So here’s what you can do to win this blog’s endorsement: give me math problems that are interesting enough for me to blog about! My contact information is available on the About page. First to five wins. Mayor Pete, you’re in the lead!

 

EDIT (1/2/2020): The results are in, and I vastly overestimated the number of donations the campaign would collect! The actual number of donations was “over 1600,” per the campaign; let’s say the actual number was 1650. Also, it seems that you weren’t allowed to donate less than $1. Given these parameters, the equilibrium solution looks like this:

1650_Chart

In particular, the maximum contribution in the equilibrium is $3.58 and the average contribution is $2.13.

As it turns out, the winning value was $1.40. In comparison, the expected winning value is $2.36 (not $2.13, since in our equilibrium larger values are more likely to win (so that probability of winning per dollar contributed stays constant)). In the distribution over winning numbers, $1.40 is just the 11th percentile number. I think this is predictable, since people don’t play the equilibrium and instead do silly things like contributing $1 and $4.20 and $100, which essentially lowers the number of people who “play the game to win.”

For amusement, here are some more details form the Buttigieg campaign:

  • Overall we collected more than 1600 donations, with over 600 different values represented
  • 182 out of the 200 values between $1 and $2.99 were represented (spoiler alert, that means the winner was in there!) [Note: this implication is incorrect! -Eric]
  • In case you were wondering, 8 people chose 3.14 (~pi), but only 4 tried 2.72 (~e)
  • Apart from $1 on the nose, $1.19 (for Pete’s birthday, perhaps?) was the most popular guess by far, with 37 submissions
  • After the first few hours of the game, nobody had yet donated $1.01 but by the end of the game, 10 people had given it a shot

(I’m pretty happy that they singled out e in their email, though I’m not convinced the people who donated $2.72 were actually trying to donate e :))

 

1. A subtle point: the fact that we are solving for the strategy that maximizes probability of victory per dollar spent, rather than probability of victory given that you can only make one donation (of whatever size) is important here; otherwise there would be some (tiny) probability of donating k cents for every k. (Why?)

2 thoughts on “Pete’s problem

  1. The goal to “get a larger probability of winning per dollar spent” is natural. Another natural goal (my original goal) is to “get a larger probability of winning regardless of the amount spent” with equilibrium strategy “the probability that you win is the same for any donated amount”. That slightly changes the differential equation – instead of x/(x+1) we will have 1. Will the result approximately stay the same?
    I did not expect to have a plateau in the middle of the graph, with the donation amount(in cents) going so close to the number of participants.

    Liked by 1 person

    1. That’s the problem I originally thought about (before deciding that maximizing probability of winning per dollar spent is more natural, since you can give multiple donations). That’s exactly right — the \frac{x}{x + 1} goes away and the math is somewhat nicer! (Though the solution to the differential equation still can’t be expressed in terms of elementary functions.)

      You get something pretty similar: D_{\text{avg}} grows as \frac{n}{\log n}, and I think that asymptotically you get the same constants too. For n = 50,000 I’m getting that D_{\text{avg}} = \$24.29, slightly more than the $22.03 I got above.

      The probability density plot looks similar to the one above, except that there isn’t a steep drop at the beginning (but there is a steep drop at the end). That’s because whereas in the above problem you want the probability of winning with a two-cent donation to be *double* that of winning with a one-cent donation, in your problem you want them to be the same. This effect is very noticeable near zero but has negligible effect further out.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s