Anders, thanks for this post, I will think about this more.
There will be an exponential explosion in the number of required prediction markets
By exponential explosion here, do you mean the usual issues with marginalizing in Bayesian networks of high treewidth? If so, this paper I wrote (UAI-2011) with some folks claims it is possible to avoid this issue in “appropriately sparse” causal graphs (by also potentially exploiting Verma constraints in the same way variable elimination exploits conditional independences):
If we want to get non-identifiable causal quantities from a joint distribution Futarchy gets us, then we will fail, but I am not sure this is Futarchy’s fault—it is a method of aggregating info about a joint distribution, nothing more and nothing less.
If we want to get an identifiable causal quantity, and if the above is the kind of exponential explosion you meant, then the issue is merely computational for identifiable causal quantities (and also remains for non-causal quantities if the graph has a large enough treewidth / there aren’t enough independences to exploit). Futarchy isn’t magic, it can’t solve NP-complete problems for free.
If the graph is sparse, then either we equate futarchy-estimated probabilities with causal ones by design (by e.g. asking about randomized trials), or just treat Futarchy as a module that does “statistical inference” (filling in probabilities in a table by aggregating previously unaggregated info) for us, and then pay a polynomial cost to get the functionals we really want. Either way, we are not doomed (???).
I hope I didn’t abuse terminology when I used the term “exponential explosion”. I should have double checked the use of this term with someone more technical than me. What I meant was essentially the “curse of dimensionality” - the number of required prediction markets grows exponentially with the number of confounders.
I see this as a real problem because almost all those conditional prediction markets would have to be reversed with all the trades unwound. This makes it very hard to argue that the markets are worth the time of the participants.
Asking about randomized trials is an interesting idea, but those markets will be hard to settle without actually running the randomized trial. Also, when using futarchy to make political decisions, the questions we want answers to are often one-off events at the aggregate country level, which makes it very hard to run a trial.
Anders, what I meant is your Kim/Hillary example has a graph that looks like this:
A → Y ← C → A, and you want p(Y | do(a)). Your point is that your problem grows exponentially with the statespace of C.
Imagine instead that you had a much more complicated word example with a graph in Fig. 7 in the paper I linked (where a bunch of confounders are not observed and are arbitrarily complicated. In fact instead of x1, …, x5, imagine it was a graph of length k: x1, …, xk. And you want p(xk | do(xk-2)). Then my claim is the problem is not exponential size/time in the statespace of those confounders, OR in k, but in fact of constant size/time.
Although I am not entirely sure how to ask a prediction market for the right parameters directly… this is probably an open problem.
Anders, thanks for this post, I will think about this more.
By exponential explosion here, do you mean the usual issues with marginalizing in Bayesian networks of high treewidth? If so, this paper I wrote (UAI-2011) with some folks claims it is possible to avoid this issue in “appropriately sparse” causal graphs (by also potentially exploiting Verma constraints in the same way variable elimination exploits conditional independences):
http://arxiv.org/pdf/1202.3763.pdf
If we want to get non-identifiable causal quantities from a joint distribution Futarchy gets us, then we will fail, but I am not sure this is Futarchy’s fault—it is a method of aggregating info about a joint distribution, nothing more and nothing less.
If we want to get an identifiable causal quantity, and if the above is the kind of exponential explosion you meant, then the issue is merely computational for identifiable causal quantities (and also remains for non-causal quantities if the graph has a large enough treewidth / there aren’t enough independences to exploit). Futarchy isn’t magic, it can’t solve NP-complete problems for free.
If the graph is sparse, then either we equate futarchy-estimated probabilities with causal ones by design (by e.g. asking about randomized trials), or just treat Futarchy as a module that does “statistical inference” (filling in probabilities in a table by aggregating previously unaggregated info) for us, and then pay a polynomial cost to get the functionals we really want. Either way, we are not doomed (???).
Thank you for the great comments Ilya!
I hope I didn’t abuse terminology when I used the term “exponential explosion”. I should have double checked the use of this term with someone more technical than me. What I meant was essentially the “curse of dimensionality” - the number of required prediction markets grows exponentially with the number of confounders.
I see this as a real problem because almost all those conditional prediction markets would have to be reversed with all the trades unwound. This makes it very hard to argue that the markets are worth the time of the participants.
Asking about randomized trials is an interesting idea, but those markets will be hard to settle without actually running the randomized trial. Also, when using futarchy to make political decisions, the questions we want answers to are often one-off events at the aggregate country level, which makes it very hard to run a trial.
Anders, what I meant is your Kim/Hillary example has a graph that looks like this:
A → Y ← C → A, and you want p(Y | do(a)). Your point is that your problem grows exponentially with the statespace of C.
Imagine instead that you had a much more complicated word example with a graph in Fig. 7 in the paper I linked (where a bunch of confounders are not observed and are arbitrarily complicated. In fact instead of x1, …, x5, imagine it was a graph of length k: x1, …, xk. And you want p(xk | do(xk-2)). Then my claim is the problem is not exponential size/time in the statespace of those confounders, OR in k, but in fact of constant size/time.
Although I am not entirely sure how to ask a prediction market for the right parameters directly… this is probably an open problem.