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.
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!