7 ms·

This paper just gets me every time I see it. It really doesn’t claim or do much that isn’t already quite obvious (it also has the other problem of going on com

This paper just gets me every time I see it. It really doesn’t claim or do much that isn’t already quite obvious (it also has the other problem of going on completely unrelated tangents.) First, it does this funny thing where it “proves” that EMH (or market efficiency) is NP-hard, by building gadgets based on options and then using them to “embed” 3-SAT. This is fine except (a) we often don’t care about an exact solution (so we need approximation-hardness that isn’t shown) and (b) I can come up with millions of other obvious things like this! Here’s a silly one one: I give a derivative whose price is $1 if a solution (that is known to exist) to an NP-hard problem is found by a given time. This will “show the NP hardness of EMH” because obviously the derivative price should be 1 (the problem has a solution, by construction) and so anyone should “obviously” price it at $1. This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior. Taking it to its extreme then everything breaks, because the model is wrong. We don’t throw up our hands and quit because making real-life decisions is a sampling-hard, query-hard, and NP-hard problem (if all data is known), but a basic model of rationality would say that humans can “perfectly” solve it. (Which is obviously crazy, but we obviously don’t throw the assumption of rationality of agents out the window because of this.) Otoh, I am definitely of the opinion that some economists hold EMH as a “magical” axiom, but that’s a different story.

murbard2 6y ago
It's not even needed to introduce weird derivatives, a publicly traded company can announce $1,000,000 dollar prizes for factoring a RSA keys. In fact, you can embed more powerful oracles like this, e.g. publicly traded company announces a $1,000,000 dollar prize for anyone who submits an inconsistent statement in ZFC. The EMH is a framework. With any scrutiny it's obvious that it can at most be first order accurate since obtaining and processing information is costly. This is not a particularly new insight or one that would be a surprise to any proponent of the EMH.
- yowlingcat 6y ago
  > The EMH is a framework. With any scrutiny it's obvious that it can at most be first order accurate since obtaining and processing information is costly. This is not a particularly new insight or one that would be a surprise to any proponent of the EMH. Great clarification. I'm always suspicious of interpretations of EMH that are a lot more literal than they should be, drawing effectively false conclusions from double negations. I think the truth is as you said.
- whatshisface 6y ago
  >at most be first order accurate The EMH is accurate to way better than the tangent line, which is what a first order approximation is.
  - murbard2 6y ago
    When someone says a consideration is orthogonal to another one, they are not literally embedded in an Euclidean space. In this context, first order is used loosely to mean that the deviations come from effects which are only secondary in magnitude and relevance, not to indicate that we're looking at the asymptotic behavior of a formula when a parameter is taken to be infinitesimal.
    - whatshisface 6y ago
      The trouble is that EMH is a formula, so the "to first order" thing has a literal meaning that is not what the author meant. It's kind of like saying that "1-x^2/2 is cos(x) to first order," moreso than saying "my business plan is a good idea for every involved party, to first order."
- ChrisLomont 6y ago
  The complexity of factoring RSA keys is not known, so this method isn’t sufficient. It is known on a quantum computer factoring is polynomially hard.
TuringTest 6y ago
> Taking it to its extreme then everything breaks, because the model is wrong. In my view it is a good thing to prove the model wrong, because so many people take extreme moral and political stances on account of the model being accurate. At the very least, displaying counter-examples is a way to show those stances for what they are, exposing them as beliefs without scientific support.
- qsort 6y ago
  > because so many people take extreme moral and political stances on account of the model being accurate As much as this is certainly the case (people using models wrong is one of my personal pet peeves), there are at least as many people who take equal and opposite extreme moral and political stances on account of the model being inaccurate. Anyone who actually understand EMH just takes it for what it is. > beliefs without scientific support Any political or moral belief is a belief without scientific support. Those are simply not things within the domain of science. Anyone who says otherwise is just trying to bamboozle you into some weird ideology.
- SilasX 6y ago
  >In my view it is a good thing to prove the model wrong, because so many people take extreme moral and political stances on account of the model being accurate. But this wouldn't affect thoses stances (in either direction). An EMH advocate can just (rightly) say, "Markets are efficient up to the limits of computation speed." Those same limits apply to anyone else's attempt to correct the market, so it doesn't validate view based on its negation either.
bawolff 6y ago
> (a) we often don’t care about an exact solution If we're trying to prove np-hardness we do.
- LolWolf 6y ago
  It doesn’t really make sense in this case though, does it? One example is that Knapsack can be approximately solved in polynomial time for all tolerances eps (I.e., it has a Fully-polynomial time approximation scheme, or FPTAS). The EMH is only talking about essentially approximate behavior (as the paper also mentions, with repeated experiments).
  - bawolff 6y ago
    Which is why this whole venture is more an exercise in pendantry rather than an actual attempt to solve np problems with markets.
Sharlin 6y ago
There have been (at least semi-)serious proposals that P=NP based on the fact that nature seems to be able to find optima to NP-hard optimization problems such as minimizing the area:volume ratio in a foam. Of course, they have been unable to give any reasonable arguments as to why those should be global optima.
- MaxBarraclough 6y ago
  Doesn't that line of argument only work if nature's algorithms can be shown to be both precise (giving exact solutions) and complete (able to solve every valid problem)?
  - qsort 6y ago
    NP-complete problems can be polynomially reduced to each other. If you had a magical oracle that was able to solve any one specific NP-complete problem in O(1) time, you could turn that into a O(n^k) solution for all NP-complete problems. That's the idea behind DNA-computing, for instance. The question is whether it is actually possible to do so at a reasonable cost and at scale. Regardless, what "nature" does has 0 to do with P vs NP, computability or anything else. P vs NP is a statement strictly about mathematical objects, there is no notion of "nature" anywhere in it.
  - est31 6y ago
    Yeah I doubt that nature is able to solve problems above a certain size. After you put together a certain number of soap bubbles they'll collapse into a black hole. Furthermore there are concerns of speed of light or speed of sound. Nature might give efficient solvers for specific problems up to a certain size, but we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers.
    - MaxBarraclough 6y ago
      > we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers. They're out there, and practical for some problems, but SMT solvers aren't exactly a solved problem. They're used for deductive proofs about program correctness, which are still pretty finicky. [0] [0] https://blog.adacore.com/using-spark-to-prove-255-bit-integer-arithmetic-from-curve25519 https://blog.adacore.com/using-spark-to-prove-255-bit-intege...
MaxBarraclough 6y ago
> Here’s a silly one one: I give a derivative whose price is $1 if a solution (that is known to exist) to an NP-hard problem is found by a given time. With a similar approach, we could 'prove' that market efficiency is non-computable, right?
- gnulinux 6y ago
  "If you find me nth Busy Beaver program for any n>10, I'll give you $n"
  - MaxBarraclough 6y ago
    I could be wrong, but that isn't known to be undecidable, is it? Merely extremely difficult? I was thinking If you give me a program that solves the halting problem, I'll give you $1. On reflection though, that's not just a bargain, it's also an outright contradiction; we know no such program exists, so making this offer doesn't affect the market at all. Perhaps there's a sneakier variation on this.
    - gnulinux 6y ago
      It is undecidable. If we had an algorithm to compute # of steps in Busy Beaver (n) (let's call it S(n)) then for all Turing Machines with n states run S(n) steps. If it doesn't halt, it will never halt. Halting problem solved! (well, blank tape halting problem, which is as hard as halting problem). https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S(n)_and_%CE%A3(n) https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomput... > On reflection though, that's not just a bargain, it's also an outright contradiction; we know no such program exists, so making this offer doesn't affect the market at all. Perhaps there's a sneakier variation on this. We do know Busy beaver 1 to 4 (via brute force). We have lower bound for 5. It's definitely possible to compute more of these values. Uncomputable does not mean not possible to compute, it means you cannot find an algorithm that solves the problem in general. So, maybe by dedicating bizarre amount of compute, you could find BB # 1M to claim your $1M from me. Get rich quick!
AndrewKemendo 6y ago
>This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior. The granularity of the "correctness" is the major difference here and you're asking the author to be ok with an extremely rough success criteria when they are proposing a mathematically perfect success criteria. So, define how you would quantify "pretty good" in comparison with "mathematically optimal" and you might get what is in effect an infinite delta. >but a basic model of rationality would say that humans can “perfectly” solve it. "basic model of rationality" doesn't make sense. Rationalism has not been shown to provide a pathway to a general epistemology. Fundamentally the author is making a really good case for the idea that oblique or poorly specified/constructed goal and measurement criteria (eg. EMH) should not be assumed as a competent goal vectoring mechanism for society.
- LolWolf 6y ago
  > The granularity of the "correctness" is the major difference here and you're asking the author to be ok with an extremely rough success criteria when they are proposing a mathematically perfect success criteria. All I'm saying is that there are easier and clearer ways of presenting the same thing that could be done in a sentence and make the "reason why" obvious. No need to introduce gadgets and go on and on for 30 pages about "exponential time" (is the author talking about the exponential time hypothesis? Or is this P vs. NP?) among other things. There's also some additional crossed wires about "needing to try all cases" or something, that doesn't make any sense. No SAT solver/TSP solver/MILP solver, etc., does this. Anyone who is at all familiar with this topic would not make such statements, and certainly not, in the way you mention, a "mathematically perfect" criterion that "is proven wrong." So which is it? Is the author being cavalier about the literature? Or do they simply not understand the basics? Additionally, they're not proving anything wrong. This is, like what I mentioned before, similar to bashing people for saying "Nash-equilibria are PPAD-hard (and communication hard) so Nash-equilibrium as a concept is bad because it's computationally difficult." (In fact, I'd say it's even less interesting than this, because at least the latter is a nontrivial result; not a one-line argument that we can embed arbitrarily complex things into the market.) > Rationalism has not been shown to provide a pathway to a general epistemology. This is "rational" as in "rational agent" (utility-maximizing, or an agent that makes at least Pareto-optimal choices, or who plays to Nash or correlated equilibria) not "rationalists" as in people who apply rationalism as an epistemology. Applied broadly, "rational agents" could solve halting-hard problems by making an obvious game where an agent who solves such a problem gets a million dollars, since such agents are often assumed to have unbounded computational power. (In particular, nothing about the agent's computational power is often assumed.) > Fundamentally the author is making a really good case for the idea that oblique or poorly specified/constructed goal and measurement criteria (eg. EMH) should not be assumed as a competent goal vectoring mechanism for society. Not really, no. For one, EMH says nothing about exact solutions (this would require a much more careful argument with a different type of reduction), and two, in the same way as before, putting EMH on a pedestal (like putting Nash equilibria on a pedestal, or agent rationality, etc.) leads to absurd results. My point is that (a) this is well-known and (b) you can make much simpler examples (like the ones above) that don't appear to be as "clever" but prove the same (nearly-obvious) point.
tshaddox 6y ago
> This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior. Most importantly, it doesn't mean that any alternative to markets are not also NP-hard.

murbard2 6y ago

It's not even needed to introduce weird derivatives, a publicly traded company can announce $1,000,000 dollar prizes for factoring a RSA keys. In fact, you can embed more powerful oracles like this, e.g. publicly traded company announces a $1,000,000 dollar prize for anyone who submits an inconsistent statement in ZFC. The EMH is a framework. With any scrutiny it's obvious that it can at most be first order accurate since obtaining and processing information is costly. This is not a particularly new insight or one that would be a surprise to any proponent of the EMH.

yowlingcat 6y ago
> The EMH is a framework. With any scrutiny it's obvious that it can at most be first order accurate since obtaining and processing information is costly. This is not a particularly new insight or one that would be a surprise to any proponent of the EMH. Great clarification. I'm always suspicious of interpretations of EMH that are a lot more literal than they should be, drawing effectively false conclusions from double negations. I think the truth is as you said.
whatshisface 6y ago
>at most be first order accurate The EMH is accurate to way better than the tangent line, which is what a first order approximation is.
- murbard2 6y ago
  When someone says a consideration is orthogonal to another one, they are not literally embedded in an Euclidean space. In this context, first order is used loosely to mean that the deviations come from effects which are only secondary in magnitude and relevance, not to indicate that we're looking at the asymptotic behavior of a formula when a parameter is taken to be infinitesimal.
  - whatshisface 6y ago
    The trouble is that EMH is a formula, so the "to first order" thing has a literal meaning that is not what the author meant. It's kind of like saying that "1-x^2/2 is cos(x) to first order," moreso than saying "my business plan is a good idea for every involved party, to first order."
ChrisLomont 6y ago
The complexity of factoring RSA keys is not known, so this method isn’t sufficient. It is known on a quantum computer factoring is polynomially hard.

TuringTest 6y ago

> Taking it to its extreme then everything breaks, because the model is wrong. In my view it is a good thing to prove the model wrong, because so many people take extreme moral and political stances on account of the model being accurate. At the very least, displaying counter-examples is a way to show those stances for what they are, exposing them as beliefs without scientific support.

qsort 6y ago
> because so many people take extreme moral and political stances on account of the model being accurate As much as this is certainly the case (people using models wrong is one of my personal pet peeves), there are at least as many people who take equal and opposite extreme moral and political stances on account of the model being inaccurate. Anyone who actually understand EMH just takes it for what it is. > beliefs without scientific support Any political or moral belief is a belief without scientific support. Those are simply not things within the domain of science. Anyone who says otherwise is just trying to bamboozle you into some weird ideology.
SilasX 6y ago
>In my view it is a good thing to prove the model wrong, because so many people take extreme moral and political stances on account of the model being accurate. But this wouldn't affect thoses stances (in either direction). An EMH advocate can just (rightly) say, "Markets are efficient up to the limits of computation speed." Those same limits apply to anyone else's attempt to correct the market, so it doesn't validate view based on its negation either.

bawolff 6y ago

> (a) we often don’t care about an exact solution If we're trying to prove np-hardness we do.

LolWolf 6y ago
It doesn’t really make sense in this case though, does it? One example is that Knapsack can be approximately solved in polynomial time for all tolerances eps (I.e., it has a Fully-polynomial time approximation scheme, or FPTAS). The EMH is only talking about essentially approximate behavior (as the paper also mentions, with repeated experiments).
- bawolff 6y ago
  Which is why this whole venture is more an exercise in pendantry rather than an actual attempt to solve np problems with markets.

Sharlin 6y ago

There have been (at least semi-)serious proposals that P=NP based on the fact that nature seems to be able to find optima to NP-hard optimization problems such as minimizing the area:volume ratio in a foam. Of course, they have been unable to give any reasonable arguments as to why those should be global optima.

MaxBarraclough 6y ago
Doesn't that line of argument only work if nature's algorithms can be shown to be both precise (giving exact solutions) and complete (able to solve every valid problem)?
- qsort 6y ago
  NP-complete problems can be polynomially reduced to each other. If you had a magical oracle that was able to solve any one specific NP-complete problem in O(1) time, you could turn that into a O(n^k) solution for all NP-complete problems. That's the idea behind DNA-computing, for instance. The question is whether it is actually possible to do so at a reasonable cost and at scale. Regardless, what "nature" does has 0 to do with P vs NP, computability or anything else. P vs NP is a statement strictly about mathematical objects, there is no notion of "nature" anywhere in it.
- est31 6y ago
  Yeah I doubt that nature is able to solve problems above a certain size. After you put together a certain number of soap bubbles they'll collapse into a black hole. Furthermore there are concerns of speed of light or speed of sound. Nature might give efficient solvers for specific problems up to a certain size, but we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers.
  - MaxBarraclough 6y ago
    > we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers. They're out there, and practical for some problems, but SMT solvers aren't exactly a solved problem. They're used for deductive proofs about program correctness, which are still pretty finicky. [0] [0] https://blog.adacore.com/using-spark-to-prove-255-bit-integer-arithmetic-from-curve25519 https://blog.adacore.com/using-spark-to-prove-255-bit-intege...

MaxBarraclough 6y ago

> Here’s a silly one one: I give a derivative whose price is $1 if a solution (that is known to exist) to an NP-hard problem is found by a given time. With a similar approach, we could 'prove' that market efficiency is non-computable, right?

gnulinux 6y ago
"If you find me nth Busy Beaver program for any n>10, I'll give you $n"
- MaxBarraclough 6y ago
  I could be wrong, but that isn't known to be undecidable, is it? Merely extremely difficult? I was thinking If you give me a program that solves the halting problem, I'll give you $1. On reflection though, that's not just a bargain, it's also an outright contradiction; we know no such program exists, so making this offer doesn't affect the market at all. Perhaps there's a sneakier variation on this.
  - gnulinux 6y ago
    It is undecidable. If we had an algorithm to compute # of steps in Busy Beaver (n) (let's call it S(n)) then for all Turing Machines with n states run S(n) steps. If it doesn't halt, it will never halt. Halting problem solved! (well, blank tape halting problem, which is as hard as halting problem). https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S(n)_and_%CE%A3(n) https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomput... > On reflection though, that's not just a bargain, it's also an outright contradiction; we know no such program exists, so making this offer doesn't affect the market at all. Perhaps there's a sneakier variation on this. We do know Busy beaver 1 to 4 (via brute force). We have lower bound for 5. It's definitely possible to compute more of these values. Uncomputable does not mean not possible to compute, it means you cannot find an algorithm that solves the problem in general. So, maybe by dedicating bizarre amount of compute, you could find BB # 1M to claim your $1M from me. Get rich quick!

AndrewKemendo 6y ago

>This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior. The granularity of the "correctness" is the major difference here and you're asking the author to be ok with an extremely rough success criteria when they are proposing a mathematically perfect success criteria. So, define how you would quantify "pretty good" in comparison with "mathematically optimal" and you might get what is in effect an infinite delta. >but a basic model of rationality would say that humans can “perfectly” solve it. "basic model of rationality" doesn't make sense. Rationalism has not been shown to provide a pathway to a general epistemology. Fundamentally the author is making a really good case for the idea that oblique or poorly specified/constructed goal and measurement criteria (eg. EMH) should not be assumed as a competent goal vectoring mechanism for society.

LolWolf 6y ago
> The granularity of the "correctness" is the major difference here and you're asking the author to be ok with an extremely rough success criteria when they are proposing a mathematically perfect success criteria. All I'm saying is that there are easier and clearer ways of presenting the same thing that could be done in a sentence and make the "reason why" obvious. No need to introduce gadgets and go on and on for 30 pages about "exponential time" (is the author talking about the exponential time hypothesis? Or is this P vs. NP?) among other things. There's also some additional crossed wires about "needing to try all cases" or something, that doesn't make any sense. No SAT solver/TSP solver/MILP solver, etc., does this. Anyone who is at all familiar with this topic would not make such statements, and certainly not, in the way you mention, a "mathematically perfect" criterion that "is proven wrong." So which is it? Is the author being cavalier about the literature? Or do they simply not understand the basics? Additionally, they're not proving anything wrong. This is, like what I mentioned before, similar to bashing people for saying "Nash-equilibria are PPAD-hard (and communication hard) so Nash-equilibrium as a concept is bad because it's computationally difficult." (In fact, I'd say it's even less interesting than this, because at least the latter is a nontrivial result; not a one-line argument that we can embed arbitrarily complex things into the market.) > Rationalism has not been shown to provide a pathway to a general epistemology. This is "rational" as in "rational agent" (utility-maximizing, or an agent that makes at least Pareto-optimal choices, or who plays to Nash or correlated equilibria) not "rationalists" as in people who apply rationalism as an epistemology. Applied broadly, "rational agents" could solve halting-hard problems by making an obvious game where an agent who solves such a problem gets a million dollars, since such agents are often assumed to have unbounded computational power. (In particular, nothing about the agent's computational power is often assumed.) > Fundamentally the author is making a really good case for the idea that oblique or poorly specified/constructed goal and measurement criteria (eg. EMH) should not be assumed as a competent goal vectoring mechanism for society. Not really, no. For one, EMH says nothing about exact solutions (this would require a much more careful argument with a different type of reduction), and two, in the same way as before, putting EMH on a pedestal (like putting Nash equilibria on a pedestal, or agent rationality, etc.) leads to absurd results. My point is that (a) this is well-known and (b) you can make much simpler examples (like the ones above) that don't appear to be as "clever" but prove the same (nearly-obvious) point.

tshaddox 6y ago