A friend sent me an e-mail mentioning an interesting probability problem which I thought about and am posting my attempt at solving...
Let's say there's a biased coin, e.g., maybe it lands on heads 70% of the time instead of 50% of the time. Now some people think they know how biased the coin is, but they are unmotivated to just tell you how biased they think it is, so you need to offer money.
So you offer some "stocks", the value of which will be determined by a single coin toss. For instance the Tails stock is worth $1 if it lands on tails, and nothing if it lands on heads. The Heads stock is similar, worth $1 if it lands on heads.
Now, if you just let each person pick either Heads or Tails stock, then everyone who thinks the coin is more than 50% biased towards heads will pick Heads, and everyone else will pick Tails, but this won't tell you how biased people think the coin is.
So you could offer a number of different stocks, e.g., Heads-0%, Heads-10%, Heads-20%, ..., Heads-100%, where the Heads-70% is worth say 70 cents if it lands on heads, and 30 cents if it lands on tails.
It turns out there are various ways to set the payoffs for these stocks to motivate people to pick the stocks that match their true beliefs about the coin. That is, you can get it so that if someone thinks the coin is 70% biased towards heads, then they will pick the Heads-70% stock.
The question is: is there someway to characterize all the different ways of setting the payoffs that have this honesty-inducing property?
Here's a solution for the case where we have 5 stocks: Heads-0%, Heads-25%, Heads-50%, Heads-75%, and Heads-100%. Each stock is represented by a colored line on the graph (dark blue, green, red, orange and light blue respectively).
The height of each line as it crosses the 0% vertical line on the left is the payout of that stock when the coin lands on tails. The height of the line as it crosses the 100% vertical line on the right is the payout when the coin lands on heads. The height of the line in general is the expected payout of that stock for various biases of the coin. Note that math forces these lines to be straight — all we get to choose is the payout for tails and heads.
Now when I say it's a "solution", I mean that a different line is highest at 0%, 25%, 50%, 75% and 100%. For instance, at 25%, the green line is highest, which is the Heads-25% stock. This means that if the true bias of the coin is 25%, then the stock with the highest expected payout is the Heads-25% stock. So if someone thinks the true bias of the coin is 25%, they should pick this stock.
More generally, we can think of all the colored lines as tangent lines to a curve. You can sort of see the curve they create, like a basket:
The curve tells us the payouts for an infinite number of possible stock options, e.g., if we want to know the payout for Heads-56.32%, we just find the line tangent to our curve at 56.32%, and see where it intersects the 0% and 100% lines to get our payout for tails and heads respectively.
I claim that any honesty-inducing payout scheme with many stock options can be defined by a concave up, U-ish-shaped, curve like the one above, where the stocks are effectively tangent lines to this curve.
Proof: any set of stock payouts will create a bunch of lines on this chart, and we can always trace a curve which is the height of the highest line at each point along the x-axis. I claim this curve will never be concave down — if you draw a concave down curve and draw a line through any point in it (except the ends), that line will not be entirely below the curve, meaning it will be above it somewhere, meaning that we failed to have our curve be the hight of the highest line somewhere.
So the curve, if not straight, will be concave up, like our sample above. The lines touching this curve are the only ones we care about, since all the other ones are stocks which are never picked, since there's always a better option than those stocks for any bias of the coin.
In fact, we can define any payout scheme with a concave up curve, where tangent lines to the curve define all our stock payouts. Honesty-inducing schemes are really just ones where we correctly label the stocks. That is, if someone thinks the coin is biased 75% heads, they will pick the stock with the highest expected payout for 75%, whatever it is called, so hopefully it is called Heads-75%.