I have a question about Dutch books. If I give you a finite table of probabilities, is there a polynomial time algorithm that will verify that it is or is not Dutch bookable? Or: help me make this question better-posed.
It reminds me of Boolean satisfiability, which is known to be NP complete, but maybe the similarity is superficial.
On the assumption that the known probability is the implied payoff (in reverse of betting, where the known payoff is assumed to be the implied probability of the bet) you can check for a dutch-book by summing the probabilities. Above one and it books the gambler (who will probably not buy it), below one and it books the bookmaker.
This is because Dutch books have to be profitable over every possible outcome. There is a procedure called dutching which is very similar, except it doesn’t guarantee a profit; it just forms a Dutch book over a restricted set of bets. This is no longer exhaustive, so there are outcomes in dutching where all of your bets fail and you lose money.
I am not sure what changes if the payoff and the probability of paying off are not equivalent.
Yes. You can do the same for a diachronic Dutch book which takes the table of probabilities that describes an agents beliefs before the agent learns E and after the agent learns E. For all H in table two p(H) must = p(H|E) in table 1. If p(H) does not = p(H|E) the the agent these tables describe is Dutch bookable assuming she will wager at those probabilities.
It would seem that something is “Dutch Bookable” so long as the sum of probabilities doesn’t add up to 1, which should not be a very difficult task at all.
I’m hoping this helps you clarify the question, since I feel like this answer probably doesn’t actually address your intent :)
Great question, I think I’ll work on it. I agree with Eliezer—my intuition tells me that there exists some algorithm that does this in polynomial time in the size of the table… but I’m also curious how many bets the Dutch book has to have, in general (as a function of the number of branching points and the number of choices at each update).
It’s NP-hard. Here’s a reduction from the complement problem of 3SAT: let’s say you have n clauses of the form (p and not-q and r), i.e., conjunctions of 3 positive or negated atoms. Offer bets on each clause that cost 1 and pay n+1. The whole book is Dutch iff the disjunction of all the clauses is a propositional tautology.
I’ve written some speculations about what this might mean. The tentative title is “Against the possibility of a formal account of rationality”:
Hm… if your probability assignments are conjunctions of that form, is it still true that finding a Dutch book is polynomial in the size of the probability table that would be required to store the entire joint probability distribution corresponding to every possible assignment of all atoms? I.e., NP-hard in the number of conjunctions, but polynomial in the size of the entire probability distribution?
Interesting. I’m actually not sure. The general result by Paris I cited is a little unclear. He proves CONSISTENCY (consistency of a set of personal probability statements) to be NP-complete. First he gets SAT \leq_P CONSISTENCY, but SAT is only O(2^n) in the number of atoms, not in the number of constraints. However, the corresponding positive result, that CONSISTENCY is in NP, is proven using an algorithm whose running time depends on the whole length of the input.
It could be that if you have the whole table in front of you, checking consistency is just checking that all the rows and columns sum to 1.
However, I don’t think that looking at the complete joint distribution is the right formalization of the problem. For example, I have beliefs about 100 propositions, but it doesn’t seem like I have 2^100 beliefs about the probabilities that they co-occur.
Yes, a complete probability table is coherent iff all entries sum to 1. But what do you mean by “the” complete probability table corresponding to a given set of constraints? There’s often more than one such table.
To unify all the language and make things explicit: if you have n atoms, then there are 2^n possible states of the world (truth assignments to the atoms). Then, if you have a personal probability for each of the 2^n states (“complete joint distribution”, “complete table”), you can check consistency by summing them and seeing that you get 1. This is O(n) in the size of the table.
The question at stake seems to be something like this: does the agent legitimately have access to her (exponentially large) complete joint distribution? Or does she only have access to personal probabilities for a small number of statements (for example, a few conjunctions of atoms)? In the second case, there may be no complete joint distribution corresponding to her personal probabilities (if she’s inconsistent), exactly one (if the joint distribution is completely specified, possibly implicitly via independence assumptions that uniquely determine it), or infinitely many.
I have a question about Dutch books. If I give you a finite table of probabilities, is there a polynomial time algorithm that will verify that it is or is not Dutch bookable? Or: help me make this question better-posed.
It reminds me of Boolean satisfiability, which is known to be NP complete, but maybe the similarity is superficial.
On the assumption that the known probability is the implied payoff (in reverse of betting, where the known payoff is assumed to be the implied probability of the bet) you can check for a dutch-book by summing the probabilities. Above one and it books the gambler (who will probably not buy it), below one and it books the bookmaker.
This is because Dutch books have to be profitable over every possible outcome. There is a procedure called dutching which is very similar, except it doesn’t guarantee a profit; it just forms a Dutch book over a restricted set of bets. This is no longer exhaustive, so there are outcomes in dutching where all of your bets fail and you lose money.
I am not sure what changes if the payoff and the probability of paying off are not equivalent.
Yes. You can do the same for a diachronic Dutch book which takes the table of probabilities that describes an agents beliefs before the agent learns E and after the agent learns E. For all H in table two p(H) must = p(H|E) in table 1. If p(H) does not = p(H|E) the the agent these tables describe is Dutch bookable assuming she will wager at those probabilities.
It would seem that something is “Dutch Bookable” so long as the sum of probabilities doesn’t add up to 1, which should not be a very difficult task at all.
I’m hoping this helps you clarify the question, since I feel like this answer probably doesn’t actually address your intent :)
Well, depends on if the probabilities overlap. So:
P(A)=.5 P(A&B)=.1 P(&~B)=.2
is Dutch-Bookable
It seems closer to the solvability of a system of linear equations. Depends on what kind of probabilities you get? Like if you have
P(A), p(B), p(C), p(A&B)=P(B&C)=P(A&C)=0, it’s trivial.
But if you have
P()=1/4
then you’ve got trouble.
Everyone’s of course right. But it means I don’t see a place for my train of thought to go.
Great question, I think I’ll work on it. I agree with Eliezer—my intuition tells me that there exists some algorithm that does this in polynomial time in the size of the table… but I’m also curious how many bets the Dutch book has to have, in general (as a function of the number of branching points and the number of choices at each update).
If we let the probabilities go to 0 and 1, doesn’t this problem just become SAT?
EDIT: As it turns out, no, no it doesn’t.
I expect an algorithm polynomial in the size of the table would exist.
It’s NP-hard. Here’s a reduction from the complement problem of 3SAT: let’s say you have n clauses of the form (p and not-q and r), i.e., conjunctions of 3 positive or negated atoms. Offer bets on each clause that cost 1 and pay n+1. The whole book is Dutch iff the disjunction of all the clauses is a propositional tautology.
I’ve written some speculations about what this might mean. The tentative title is “Against the possibility of a formal account of rationality”:
http://cs.stanford.edu/people/slingamn/philosophy/against_rationality/against_rationality.pdf
I really like the Less Wrong community’s exposition of Bayesianism so I’d be delighted to have feedback!
Hm… if your probability assignments are conjunctions of that form, is it still true that finding a Dutch book is polynomial in the size of the probability table that would be required to store the entire joint probability distribution corresponding to every possible assignment of all atoms? I.e., NP-hard in the number of conjunctions, but polynomial in the size of the entire probability distribution?
Interesting. I’m actually not sure. The general result by Paris I cited is a little unclear. He proves CONSISTENCY (consistency of a set of personal probability statements) to be NP-complete. First he gets SAT \leq_P CONSISTENCY, but SAT is only O(2^n) in the number of atoms, not in the number of constraints. However, the corresponding positive result, that CONSISTENCY is in NP, is proven using an algorithm whose running time depends on the whole length of the input.
It could be that if you have the whole table in front of you, checking consistency is just checking that all the rows and columns sum to 1.
However, I don’t think that looking at the complete joint distribution is the right formalization of the problem. For example, I have beliefs about 100 propositions, but it doesn’t seem like I have 2^100 beliefs about the probabilities that they co-occur.
Yes, a complete probability table is coherent iff all entries sum to 1. But what do you mean by “the” complete probability table corresponding to a given set of constraints? There’s often more than one such table.
Oh, thanks, you’re completely right.
To unify all the language and make things explicit: if you have n atoms, then there are 2^n possible states of the world (truth assignments to the atoms). Then, if you have a personal probability for each of the 2^n states (“complete joint distribution”, “complete table”), you can check consistency by summing them and seeing that you get 1. This is O(n) in the size of the table.
The question at stake seems to be something like this: does the agent legitimately have access to her (exponentially large) complete joint distribution? Or does she only have access to personal probabilities for a small number of statements (for example, a few conjunctions of atoms)? In the second case, there may be no complete joint distribution corresponding to her personal probabilities (if she’s inconsistent), exactly one (if the joint distribution is completely specified, possibly implicitly via independence assumptions that uniquely determine it), or infinitely many.
Can I just take a second to boast about this.
Here’s a paper that I think you’ll find interesting.