Words Vs. Bets

I once had a long discussion with Ken Steiglitz about P=NP, while I was still at Princeton. … Ken was and still is sure that P must not be equal to NP. Okay, I said to Ken, what are the odds that they are equal? Ken said that he thought the odds were a million to one. I immediately suggested a bet. I did not ask him to “bet his life,” but I did ask for a million to one bet. I would put up one dollar. If in say ten years P=NP had not been proved, then he would win my dollar. If P=NP was proved in that time frame, then I would win a million dollars from Ken. Ken said no way. After more discussion the best bet I could get out of Ken was {2} to {1}.  Two to one. That was the best he would do.

That is from Richard Lipton; hat tip to Michael Nielsen.  Does anyone doubt that two to one better summarizes his evidence than a million to one?

GD Star Rating
Tagged as: ,
Trackback URL:
  • tgrass

    I will further infuriate my friends with this logically elegant reply to illogical established probabilities. I love it. Thank you.

  • I think you’re missing a “that” in there – and yes, I very much doubt that the chance against finding P=NP are closer to 2:1 than to a million to one. Not making that kind of bet is more a matter of personality than of calmly considering expected winnings. Some people won’t bet no matter what, and only a gambling addict would explicitly make a bet that could bankrupt him, no matter how small the chance. People buy insurance *against* unlikely but ruinous events.

    • only a gambling addict would explicitly make a bet that could bankrupt him, no matter how small the chance.

      Ok, I will bet you that the sun will not emit only green light on Christmas day of this year. If the sun emits only green light on Christmas day of this year, I will owe you $1,000,000,000,000. If not, you will owe me $100.

      Am I a gambling addict?

  • g

    1. Utilities versus dollars: I’m not sure I’d bet a dollar on anything at 1000000:1 odds, because having to pay $1M would hurt me a *lot* (much more than 1e6 times more than having to pay $1). Is Ken Steiglitz rich?

    2. Utilities versus dollars: The effort of actually collecting on such a bet would probably be worth more than $1. Is Ken Steiglitz’s time valueless?

    3. Risk aversion: as Brazzy says, unless Ken Steiglitz is committed to acting as a pure utility maximizer (which most people aren’t) and actually does so (which I bet most people don’t, even if notionally committed) inferring his actual beliefs or evidence from his bets is a pretty hopeless enterprise.

    Now, having said all that, if he is prepared to bet but won’t bet more than 2:1 then it seems clear that he doesn’t really think the odds are 1M:1. But such reluctance seems consistent (given #3) with really truly evaluating the odds at 1000:1, say. (Though if I thought Pr(P=NP)=0.001 then I’d be happy to bet at more than 2:1, provided the amount I stood to gain comfortably outweighed the likely cost of collecting. Say, gaining $10 versus losing $500. My current assignment — on the basis of rather little evidence — is more like 20:1 than 1000:1, though, so I’m not offering any such bet.)

    • Autumnal Harvest

      I don’t see how this reluctance can be consistent with evaluating the odds at 1000:1. There’s virtually no one so risk-adverse that they would really turn down a bet offering 3:1 where the odds are really 1000:1. Imagine an offer to buy stocks in a company that had a 99.9% chance of growing in value by 33% over 10 years, and a 0.1% chance of going bankrupt. As an amazing unheard-of added bonus, the company won’t require you to pay the money you owe them for the stocks now, but will let you hold onto it, to do as you like with, until the 10 years are up. I think Ken Steiglitz would jump at the chance, and in all likelihood owns much riskier stocks.

      As for the cost of collecting the bet: you can make the bet $1000 to $3000, if you like, and the stock analogy still shows that Ken should like this bet. However, I suspect for small bets, both sides have a constant utility associated with the glory of winning a bet, which should make even a $1 to $3 bet attractive to Ken.

      • g

        Some people are *very* risk-averse, and we don’t know how small a bet Lipton offered Steiglitz. (I agree that if he would bet at $2:$1 but not at $3:$1 then that’s hard to square with even, say, 10:1 as his real underlying belief.)

        I think you mean “growing by 3x”, not “growing by 33%”.

        It wouldn’t surprise me in the least if someone were much more risk-averse when making bets than when investing in the stock market. (Here are two possible explanations: (1) Investing substantial sums in the stock market is What Everyone Expects You To Do. I think lots of people do it without really considering whether it’s what they want to do. Betting large sums is not. (2) People commonly care a lot about what others think of them. Losing a pile of money by investing unwisely in the stock market may hurt your image a lot less than losing it by betting unwisely.)

        Please note: I am not arguing that refusing to take a 3:1 bet of modest size on a proposition you (really truly) think is 1000:1 is *sensible* or *rational*. (Nor that being happy to take such bets when they’re labelled “investment” but not when they’re labelled “bet” is sensible or rational.) On the contrary, I think it clearly isn’t; and if Steiglitz really did so refuse while truly believing that P=NP is very unlikely, then I think he was foolish. What I am arguing is only that such behaviour is *entirely possible* and therefore that the conclusion to be drawn from Steiglitz’s behaviour may be something other than “he doesn’t really think P=NP is very unlikely”.

  • It’s risk aversion and transaction costs, people are overly sensitive to big loses, and small wins get swamped by costs of managing the bet over 10 years.

    A few months ago I did a 0.01 GBP vs 100 GBP bet on global maize production, which I won. Low bet value, and low time-frame (googling 5 minutes later) reduced both risk aversion and transaction costs. I wouldn’t take the same bet if it took 10 years to clear, and it was 100 GBP vs 1,000,000 GBP.

    P=NP is definitely less likely than 1:2. While you might be hard pressed to find anyone betting against it at 1:1000000, nobody sane would bet for it at 1:2.

    • Jeff

      I think this is likely, and we could test this. What would Steiglitz take as a bet if the amount of money were higher? For example, I think it likely that Steiglitz would take a hundred-to-one bet if someone offered him, say, $10,000 if P!=NP for $1,000,000 if P=NP. I might even take that bet, but the thing about taking that sort of bet is that you can’t push the million up much. If I had a billion dollars, I would take a $100,000 to $1 billion bet on that subject (10,000 to 1), but I can’t take that bet right now because the consequences of being wrong, even if I think it’s a million-to-one bet, are too extreme.

  • Steven

    The traditional way to account for risk aversion is to ask the subject for the odds at which he would be indifferent between taking either side of the bet. For sufficiently small bets, these odds will approach the subjective probability ratio. For most utility functions, the convergence if fairly quick.

    Personally, I’d be indifferent at odds of about 1:20 (for small bets, say $1:$20).

  • John Cotterell

    If you’re going to bet on this one, you need to take into account the fact that p=np, if true, is a much more easily provable result.

    Even if less likely, it’s still more likely to be the result we see in our lifetimes.

    Bet on it, you’ll either win or not live to see yourself lose.


  • haig

    Affinity for risk varies so much, especially with dollar amounts so large. The thought of really losing $1 million overwhelmed the person’s judgement even with his high confidence level because the ramifications for losing would be overwhelmingly negative. If there was a nonzero probability of losing $1 million, he was not betting.

    A better way to come up with stakes might be to figure out each person’s optimum max_stake and then scale the 1M:1 accordingly. For BIll Gates it might be more than $1million dollars for the same confidence that P!=NP, and for your friend it might be $1000:1.

  • I wrote the piece on P=NP and betting. My point was that there is a feeling in the theory CS community that it is “obvious” that P is not NP, but that “feeling” is not really based on any fact.

    And the community is betting every day: they bet by what they work on, what they vote to fund, what they accept at conferences, what they decide to assign to students, and so on.

    • But researchers are individually betting on what other researchers will approve, not what is true.

    • Thanks – great story!

      I’ll take your bet at, hmm, 20 to 1. Up for it?
      Anyone else want to post the odds they’d take the bet at?

  • Tony

    Does it really make sense to talk about the “odds” of something that is already either true or false? Probability is generally defined in terms of the outcome of some repeatable random process. The truth of a mathematical proposition is nothing like this! You can’t decide the truth of P=NP over and over and get a different result each time, so how can you place “odds” on it?

    • gaffa

      An alternative interpretation is that probability is a measure of your subjective state of uncertainty. See:

    • I think what Eliezer Yudkowsky would say would be along the lines of “Uncertainty is a fact about your mind, not a fact about the world.” So in this case, perhaps the best we can do in defining it is the odds someone would take on a bet.

    • mjgeddes

      This indicates another weakness in Bayes. I doubt it makes sense to assign probabilities to mathematical hypothesis.

      Instead I suggest assigning a ‘similarity’ measure – degree of similarity between such-and-such a problem and other known problems (case-based, analogical reasoning).

  • Would it be possible to adjust for the nonlinear utility of the marginal dollar in a way that would allow one to map belief units to dollar amounts in bets? Then (for instance) a 1:1000 ratio might be translated into $.01 : $10.00 or equivalently $1 : $500 or $100 : $15,000. Of course, the mapping would vary a lot from person to person. And the hard part of constructing the mapping would be empirically determining the parameters for a given individual with any sort of accuracy.

  • Neel Krishnaswami

    Does anyone doubt that two to one better summarizes his evidence than a million to one?

    Yes, of course.

    P vs. NP is a purely logical proposition, which means that a Bayesian agent can only assign it a probability of either 0 or 1, since the axioms of probability require that the probability of a logical truth is 1, and the probability of a falsehood is 0. Therefore, being willing to offer any other odds — whether a million to one or two to one — on a logical proposition is evidence that the agent is not rational, since there is a simple Dutch book against them. This then means you cannot use their propensity to bet to draw conclusions about the strength of their evidence, because that principle only works for rational agents.

    • Where do the axioms of Bayesian probability say that P(logical truth) = 1 ?

      • Neel Krishnaswami

        One of Cox’s postulates, from which he derived the axioms of Bayesian probability, is that the probability calculus is an extension of logic, so that 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.

        More concretely, in this particular case, you can also construct the world’s easiest Dutch book. Suppose my probability for true is p < 1. Then my probability for false is 1-p. Offer me a bet with odds better than p/(1-p) that false holds. Collect my money, because false doesn't hold.

      • I think that Neel’s comment is both tongue-in-cheek and serious at the same time.

        Neel simply points out that the idea of a “rational” agent does not hold. A rational agent (in other words, an agent of infinite computational power) should be able to know whether P=NP, P!=NP, or whether the problem is undecidable. We do not expect time to resolve this question as there is not a random component in this question.

        So, a prediction market on this question assumes that the participants are not “rational”, but rather operate under a “bounded rationality” (Rational ==calculating everything to the maximum degree possible.)

    • Unknown

      “This then means you cannot use their propensity to bet to draw conclusions about the strength of their evidence, because that principle only works for rational agents.”

      This is just non-responsive to Robin’s post. Humans are not logically omniscient, and different sets of evidence will give us (with our inductive biases and limited computational capabilities) different degrees of confidence in logical and mathematical propositions. Mathematicians and computer scientists use such degrees of confidence every day in selecting possible avenues for research and proof.

    • andrew c

      Bollocks. I just flipped a coin. It either came up heads or tails. Are you really going to assign a probability of 1 or 0 to either outcome? How does your dutch book work out if the proposition turns out to be true? Can you dutch book someone who assigns 1:1 odds to heads?

  • Autumnal Harvest

    g, I can’t reply to your reply. I’m not sure if that’s a feature because Robin doesn’t want overly protracted discussions, or just due to column width. I guess I’ll try posting this and see it’s allowed.

    You seem overly reluctant to draw conclusions about people’s beliefs about likelihoods from their actual behavior. Certainly nothing in this scenario consistitues a rigorous mathematical proof about what Ken does or does not believe, and all of the issues you’ve brought up indeed prevent us from making any airtight statements about Ken’s beliefs. However, they don’t strike me as overall adding up to a plausible explanation as to why someone (call him Ken_v2) who really believes something is 99.9% likely to occur would be willing to put up $2 to win $1, but not to put up $3; a theoretically possible explanation, yes, but not a plausible one. A much more plausible explanation is that the claim of 99.9% was a rhetorical flourish, rather than a true statement of his beliefs.

    Yes, people are not calculating reasoning machines, but I disagree that “inferring his actual beliefs or evidence from his bets is a pretty hopeless enterprise.” Your argument essentially appears to be that it’s hopeless because one can always come up with arguments as to why complications, nonlinearities, and non-rational biases could conceivably explain his actions. That’s true, but by the same logic, you could just as easily say “inferring a person’s actual beliefs from his actions is a pretty hopeless enterprise.” In the case of Ken_v2, I would ask what he means when he says “99.9% likely.” Can he point me to other cases in which we have good frequentist methods of agreeing that the probability is roughly 99.9% (e.g. the probability that the weather in Denver is over 80 degrees Fahrenheit on a particular day in December), and in which he exhibits similar levels of risk aversion? If he can’t, I think it signficantly more plausible to label his claims as insincere, rather than his actions as foolish.

    • g

      I think replies nested more than one level deep just aren’t allowed. I’d guess that the reason might actually be simply that whoever wrote the software that runs OB found it easier that way.

      Anyway. On reflection, I agree that I overstated the case, but not in quite the way I think you’re suggesting. I didn’t say — at least, I didn’t intend to, and I don’t think I actually did — that the mere fact that other explanations are *possible* makes it impossible to draw any conclusions about Steiglitz’s beliefs. I do think that a considerable degree of divergence between “real” opinions and willingness to bet is (not only possible in principle but) commonplace, and exactly how much is (not only in principle but in practice, and to a considerable extent) dependent on just what sort of bet is proposed. 2:1 versus 1000000:1 does indeed seem ridiculous, and I’m pretty sure Steiglitz doesn’t “really” think P(P=NP) is as small as 10^-6. I’m not sure I’m really prepared to defend 2:1 versus 1000:1. But, say, 10:1 versus 1000:1 or 2:1 versus 30:1? Seems entirely plausible to me, unfortunately.

      • g

        Oops: I see that in fact replies two levels deep (but not more) are allowed, at which point I no longer find it plausible that it was easier to allow that than to allow arbitrary depths.

  • Jeff

    The other thing about the million-to-one bet is that it’s worth asking Steiglitz what numbers he’d require to take the bet the other way. I, for example, would also say something like a million to one for P=NP, but I might take a $1million-$1 if all I’m offering up is $1. I do not expect P to be = to NP, but I’ve no odds-calculating-robot certainty of it. Gaining $1 isn’t worth the risk of losing a million, but gaining a million is worth the risk of losing a dollar on a subject whose odds I don’t think are as obviously against me as, say, a lottery ticket. I wouldn’t take a lot of those bets, and if several were offered I might look for an opportunity that I think is more likely to pay off, but losing a dollar isn’t a big deal.

  • Daniel B

    You should have tried it with 1c vs $10K or even 1c vs $100. An amount like $1M is likely to spook most people because of the non-linear utility value of being completely broke.

    But 2:1 says something. It’s funny how people’s ‘intuition’ (or left brain) shifts in to gear when confronted with a situation with actual consequences. For this reason I like the expression ‘Your mouth is writing checks that your ass can’t cash’.

  • Greg Lee

    “Does anyone doubt that two to one better summarizes his evidence than a million to one?”

    RH: would you also argue that 35:1 on 00 on a U.S. roulette wheel better summarizes the evidence than 37:1? After all, millions of dollars are bet at 35:1.

  • Pingback: Math World | Overcoming Bias : Words Vs. Bets()

  • Ian Maxwell

    Interesting. I find it really strange that Ken Steiglitz wouldn’t accept any odds steeper than 2:1. I know very little of P vs. NP beyond the question itself (which I do actually understand technically), and so you would think I would be less sure than this fellow of the answer—yet, thinking about it, the point at which I actually feel indifferent about betting is something like 25:1. By contrast, I find it much less likely that P vs. NP is ever proven independent of current axioms—I might take something like 500:1 on that. (I have good reason to think that such a proof is impossible, but I’m still only an amateur mathematician and I may have missed some subtlety.)

    If anyone wants to offer me a small-stakes wager based on this, please do. I would be quite willing to bet twenty against one that P != NP, or one against thirty that P = NP, as long as I don’t stand to lose more than $100 or so.

  • Ian Maxwell

    Immediate revision to my last comment: In retrospect, I am prone to huge overestimates at the far end of my probability scale, so I should probably revise waaaay down to about 10:1 for P != NP and 100:1 for undecidablity.

  • Douglas Knight

    Ian Maxwell, I would be happy to bet my $100 against your $10k that PvNP is shown to be undecidable by Peano arithmetic within the next 20 years. If you cap your losses at $100, it doesn’t look to me worth the transaction costs to collect 20 years in the future, so I won’t put up my $1. Similarly, I don’t think my first offer gives you any upside.

  • Pingback: links « Mike Kenny()