A comment on Computational Complexity blog blog inspired me to look at the following problem

Suppose you give true/false test to students and want them to put down their subjective probabilities that answer is true/false. To make them honest, you would want to award points in such a way, that in order to maximize their expected points, the student would need to report their correct probabilities. Which utility function to use? It turns out, f(x)=A log x + B is one such family. Here's the derivation

Questions:

1) Does any other such utility function exist?

2) What are other fun ways to torture students?

Here are graphs of three possible functions that can be used for eliciting probabilities from students. They are all concave, maybe one can prove any suitable function must be concave?

## 8 comments:

Hi Yaroslav, thanks for answering my question. My squaring-based idea would elicit the correct internal probabilities just as surely as the log-based one; that's why I was asking what properties differentiate the two. Additivity might well be such a property (I haven't thought about it yet).

Yes, your idea seems to elicit correct probabilities as well. When I said f(x)=x^2 does not work, that was treating f(x) as a way of awarding points. On other hand, you are penalizing, so this equates to f(x)=-(1-x)^2 utility function which *does* achieve expected maximum at x=p

So any utility function f(x) for which f'(x)/f'(1-x)=(1-x)/x will work. (ie expected utility EU(x) will have a local extremum at point x=p)

This sort of looks like a differential equation...is there a good way to characterize the set of solutions?

Some smart people in comp.math commented on this, and it turns out that you can take any nice function defined on (0,1/2] and extend it to the second half by

f(x) = C + int_{1/2}^x (1-t) f'(1-t)/t dt

where C is determined in a way to make the two pieces match up.

One person suggested that in order for the function to be infinitely differentiable it should look like a/x around x=1/2 ... hm, why?

http://groups-beta.google.com/group/sci.math/browse_thread/thread/767ff149b3f830ca/2589e2a14eb8dc23

The most interesting answer I got was also the simplest looking:

f'(x)/f'(1-x) = (1-x)/x

rewrite that as

xf'(x) = (1-x)f'(1-x)

So basically you can see here is that the necessary condition is that

xf'(x) is some m(x) which is invariant under x->1-x

So to construct proper f(x) all we need to do is pick some m(x) that's

symmetric around x=1/2 and solve for f(x)

For instance, if m(x) = 1, then

xf'(x) = 1

f'(x) = 1/x

f(x) = log x +C

Or if m(x) = 2x(1-x), then

xf'(x) = 2x(1-x)

f'(x) = 2(1-x)

f(x) = 2x-x^2+C

f(x) = 4+2x-x^2

f(x) = (1-x)^2

Hi, I cannot figure out why "any utility function f(x) for which f'(x)/f'(1-x)=(1-x)/x will work. (ie expected utility EU(x) will have a local extremum at point x=p)".

The link is not available now. So I cannot see your derivation. Could you post it here? Thanks a lot.

I know the derivation now. Thanks. What if the problems are multichoice ones?

BTW, Shen Yi has written a whole dissertation on issue of calibrated losses, "LOSS FUNCTIONS FOR BINARY CLASSIFICATION AND CLASS PROBABILITY ESTIMATION", page 16 has this derivation characterizing loss functions that elicit probabilities (ie, "proper scoring rules")

Post a Comment