Better prediction of probabilities through auctions

I bet you think this is another post about Hypothesis, don’t you?

Nope! This is about something completely different. This is about prediction markets and proper scoring rules.

Which aren’t actually something I know that much about, so it’s very likely everything in this post is either obvious or a bad idea. This should just be considered a “here’s some stuff I thought of while reading about this and I couldn’t find anyone who wrote this down before so I’ll write it down now” post.

A scoring rule is a way of rewarding predictions. You have some possibilities A1, …, An which are disjoint and cover everything. So e.g. you could have A1 = “there will be a labour majority in the UK 2015 elections”, A2 = “there will be a conservative majority”, A3 = “none of the above”. You want people to assign probabilities to these events. They give you a probability distribution and depending on which outcome occurs you give them a reward (or penalise them for negative rules, which a lot of them are).

A scoring rule is proper if predicting the correct probabilities is an optimal solution and strictly proper if it’s the only optimal solution. For example a scoring rule that gives you a score of log(r_i) where r_k is the probability you assigned to outcome k and i is the outcome that occurs is a strictly proper scoring rule. A scoring rule that assigns you a score of 0 regardless of what happens is proper but not strictly proper (You can’t do better than 0, but anything you want to predict at all doesn’t do worse than that either).

When thinking about these things I noticed a particularly simple sort of proper scoring rule. It’s not strictly proper, but under a certain natural extension of the definitions can be made into a strictly proper extended scoring rule.

The rule is this:

Let \(q_1, \ldots, q_n\) be any sequence of numbers in \([0, 1]\). They do not have to sum to \(1\). Let \(r_1, \ldots, r_n\) be your prediction. Your total cost is \(C = \sum\limits_{i, q_i < r_i} q_i\). Let \(i\) be the winning outcome. Then you score \(1 – C\) if \(r_i > q_i\) and \(-C\) otherwise.

You might notice that you are basically conducting a simultaneous Vickrey auction on each coordinate.

Theorem: Under this scoring rule, a distribution \(r\) obtains the optimal score if and only if \(r_i < q_i\) whenever \(p_i < q_i\) and \(q_i < r_i\) whenever \(p_i < r_i\).

Proof:

In order to simplify this proof we will show that this is true without the constraint that \(\sum r_i = 1\). Showing that these are the optimal solutions in the general case also implies that they are the optimal solutions in the specific case.

Let \(t_i = 1\) if \(r_i > q_i\) else \(t_i = 0\). Then your expected score is \(\sum t_i (p_i – r_i)\), because you pay a cost of \(r_i\) for each case where \(t_i = 1\) and a cost of \(0\) for each case where \(t_i = 0\), and you get a benefit of \(1\) with probability \(p_i\) if \(t_i\) = 1 and 0 otherwise.

This means that the multiplier for \(t_i\) is negative if \(p_i < r_i\), positive \(p_i > r_i\) and \(0\) when \(p_i = r_i\). So the only sensible choices to achieve optimality are to set \(t_i = 0\) when the coefficient is negative and \(1\) when it is positive. It doesn’t matter what you set it to when it’s 0 because the expected value is the same either way.

QED

Note that this uses very little about your chosen distribution: All you’re actually doing is picking a set of values and saying “I think your current choice of estimates undervalues these and I’m prepared to stake money on it”. This is why it’s not a proper scoring rule: Any distribution which correctly identifies which values are underconfident will do.

There are two things you can do with this. One of them turns it into a proper scoring rule of sorts, the other just uses that feature as is. I’ll now explain both:

Randomizing for fun and expected profit

The solution which makes it a proper scoring rule is as follows: Let \(Q\) be any random vector taking values in \([0, 1]^n\) with a smooth and strictly positive distribution function.

Now play exactly the above scoring rule, but you make your prediction and then \(Q\) is drawn and you play the scoring rule against the drawn value.

Lets see that the only optimal choice of \(r_i\) is \(p_i\):

Consider again the profit you make from component \(i\). Call this profit \(T_i\). Then \(E(T_i|Q_i = q_i) = p_i – q_i\) if \(r_i > q_i\) or 0 if \(r_i \leq q_i)\).

So \(E(T_i) = (p_i – E(q_i | q_i < r_i) ) P(q_i < r_i) = p_i P(q_i < r_i) – \int\limits_0^{r_i} x f_i(x) dx = \int\limits_0^{r_i} (p_i – x) f_i(x)\)

Where \(f_i\) is the marginal distribution of \(Q_i\). Now, as assumed, \(f_i\) is strictly positive. That means that this integrand is strictly increasing for as long as \(p_i \leq x\) and strictly decreasing once \(x > p_i\), so the optimal value has to be at \(r_i = p_i\).

QED

We can also derandomize this given any explicit choice of \(Q\): You make your prediction and then when the results come in we give you what would have been the expected value of your choice.

Lets consider how that would work for the simple case where each \(q_i\) is chosen uniformly at random. Splitting it up once more into benefit and cost, your expected reward is the probability that you would have won the winning index \(i\). That is, it’s \(r_i\).

Meanwhile your total cost is \( \sum E(Q_i | Q_i \leq r_i) P(Q_i \leq r_i  = \sum \frac{1}{2} r_i^2\). So your reward is \(r_i – \frac{1}{2} \sum r_i^2\). And this is just our old friend the quadratic scoring rule! So it’s possible that by picking other interesting probability distributions for \(q\) we could produce other interesting proper scoring rules. I don’t know. I haven’t really investigated.

Prediction markets

As Robin Hanson famously observed, you can turn any proper scoring rule into a prediction market. I don’t think what I’m about to describe is actually an instance of his scheme, but I don’t feel like I’ve sufficiently digested said scheme to be sure that it’s not. It’s certainly very close even if it’s not exactly the same thing.

You can use the original non-random form of the scoring rule to create what’s basically the world’s simplest prediction market:

You have n disjoint events as above that you want to predict, and you want to solicit the wisdom of the crowds in predicting it.

You do so by placing an initial non-zero bid on each option, \(b_i\). The market is now open for bidding.

A bid consists of simply picking one of the outcomes. When bidding on outcome \(i\) you pay the current market prediction, which is \(\frac{b_i}{\sum b_j}\) and increment \(b_i\) by one. If this is the outcome that occurs then you will get a reward of \(1\) for your bid. People may bid as many times as they want on as many options as they want.

This scheme should converge to something corresponding to the true beliefs of the market. When the market believes that the current prediction is under confident they will buy shares in it, raising its value. When they believe it is overconfident they must also believe that some other value is underconfident (because the probabilities sum to 1 so if \(q_i > p_i\) for some \(i\) then \(q_j < p_j\) for some \(j\)), so they will bid on that one, causing all the other probabilities to fall.

Convergence in theory is quite slow, basically oscillating like \(\frac{1}{n}\) in the number of bids on either side of the true probabilities, but I think in practice that still quickly takes it within the realms of being finer precision than peoples’ predictions are going to be anyway.

I’ve no idea if this is a good prediction mechanism in general, but it’s appealingly simple and might be worth consideration in some contexts for that alone.

This entry was posted in Uncategorized on by .