Monday, September 28, 2009

Rationality, P=NP, Prediction Markets, and a Paradox

I got the idea for this post after reading the post of Dick Lipton on betting on the P=NP problem. The discussion in the comments was extensive, mainly touching the issues of risk aversion, the inability of humans to estimate properly small probabilities, and so on. (Wolfers and Snowberg argue that it is due to the inability of human to understand very small probabilities.) The discussion continued in the Overcoming Bias blog and there one of the comments, being tongue-in-cheek, caught my eye:

probabilities must agree with logic on certainly-true and certainly-false statements, which means that the probability of logical truths has to be 1, and logical falsehoods have to be 0.

So,if P=NP is a decidable problem, it is either true or false. So, a fully rational agent, participating in the market, should know whether P=NP. It is not a matter of probabilities! All the information to make the decision is available. So, if the market has one or more rational players, the market should converge to a price of 0 or 1 immediately, depending on the state of the problem. Right?

So, which of the following is true?

  • There are no rational agents. So, all the analysis of prediction markets that assume rationality of traders is incomplete.
  • There are rational agents. The market does not converge to 0 or 1 because the P=?NP problem is undecidable.
  • There are rational agents but the return from the risk-free rate until reaching the time to settlement exceeds the return from the market. So, the market gives information on how long it will take for the problem to be officially solved.
  • If your laptop cannot find the solution, neither can the market.
OK, back to more serious work.