20 ms·

Markets are efficient if and only if P = NP (2010)

332 points by perculis 8y ago

wei_jok 8y ago
But markets are not efficient ...
- fouc 8y ago
  Proof that P does not = NP after all.
- coliveira 8y ago
  Now this will degenerate into a fight between economists and computer scientists...
  - deleted 8y ago
    [deleted]
- mdturnerphys 8y ago
  "Since P probably does not equal NP, markets are probably not efficient."
- sova 8y ago
  weak-form efficiency in markets means something special.
  - Dylan16807 8y ago
    Not really. It means that the market incorporates all past data. This paper is entertaining but it depends on the assumption that computing power grows exponentially forever and will eventually be able to solve all P problems at negligible cost. That assumption is clearly not justified. And the belief that any market perfectly incorporates data, not a single point off in any stock, is basically a strawman anyway.
    - sova 8y ago
      I don't know! I'm wondering! Because weak-form efficient means something different than strong efficiency, which is what you say when the market perfectly incorporates all data. Just out of curiosity, if the data doesn't go into the market, where does it go? Strong econ minds believe that prices do incorporate all the data necessary for valuation
      - Dylan16807 8y ago
        Sometimes data gets lost. People are making the decisions, and people are sloppy and lossy. Weak and strong are just about which data is incorporated. Neither one addresses the fact that no entity interacting with a market is infallible.
- nyolfen 8y ago
  is it really so much to ask to read the one paragraph abstract before making a comment like this?
sova 8y ago
P = NP when you nail it. From the paper: "if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. I also prove the converse by showing how we can "program" the market to solve NP-complete problems. However, there has been no proof that there does not exist some algorithm that can determine satisfiability in polynomial time. If such an algorithm were found, then we would have that P = NP. If a proof is discovered that no such algorithm exists, then we would have that P ≠ NP. Just as most people in the field of finance believe markets are at least weak-form efficient, most computer scientists believe P ≠ NP. Gasarch (2002) reports that of 100 respondents to his poll of various theorists who are “people whose opinions can be taken seriously,” the majority thought the ultimate resolution to the question would be that P ≠ NP; only 9 percent thought the ultimate resolution would be that P = NP. The majority of financial academics believe in weak form efficiency and the majority of computer scientists believe that P ≠ NP. The result of this paper is that they cannot both be right: either P = NP and the markets are weakly efficient, or P ≠ NP and the markets are not weakly efficient. "
- hvidgaard 8y ago
  That actually sounds like a refreshingly fun paper to read.
  - sova 8y ago
    Only if you can nerd out about EMH "Efficient Market Hypothesis" for 33 pages
arrownot 8y ago
What kind of markets get created when the input to the NP problem is 2^10000, I think our idea of markets are based on small scale transactions and extrapolations can't take into account intelligent agents. Also Arrow's theorem hints how small formals systems can't achieve agents desires. Anyway, I have only read the title not the arxig paper.
CJefferson 8y ago
While this is a fun, the title is a little strong. There are three limitations (whuch apply to many papers about P=NP). 1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error. 2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true. 3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.
- SolarNet 8y ago
  On two, as this appears to be a cross disciplinary paper, it's important to consider that some economists currently claim markets are efficient (the efficient market hypothesis, which is like a big open question in economics). By drawing a link between the EMH and P=NP (which many computer scientists believe is unlikely) the author is linking two open questions with opposing beliefs. So I think point two is sort of a technicality that with context it should be understood that the author is specifically talking about two open questions as they stand today. Also to further hammer home the point, due to the phrasing of the EMH, although no one may currently be using P=NP, markets would still have the efficiency property now even if no one is exploiting it. Perhaps this sort of vacuously true statement rubs you the wrong way (like it does me a bit) with the strength of the "if and only if" the author used. But if you read "markets are efficient" as the EMH then it is still a valid literal formulation. On three, sure that's great for reality. But for the formulation of markets being efficient as an inherent property (again the EMH) of markets, the size of the market could be held as effectively infinite (or at least extremely large) and the property should still hold. At some point the size of the theoretical market will explode the polynomial, and for the EMH to hold P=NP must be true.
  - stale2002 8y ago
    In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. IE, it is almost as good. So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough. Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin with.
cargocult_coder 8y ago
Therefore it's false.
modeless 8y ago
Before people get too carried away criticising markets, check this quote from the paper. > The results of this paper should not be interpreted as support for government intervention into the market; on the contrary, the fact that market efficiency and computational efficiency are linked suggests that government should no more intervene in the market or regulate market participants than it should intervene in computations or regulate computer algorithms.
- kome 8y ago
  well, governments should do both. Computer algorithms can be a very subtle form of power. And of course we should have a degree of public control over them.
- SolarNet 8y ago
  Sure, but if what the author is saying is true, then it implies that there is nothing special about markets, and a system involving an equal number of humans and computers following some other optimization algorithm could achieve similar results in efficiency. And if a government sponsored and modified such an algorithm in an attempt to optimize for equality (second only to efficiency of usage), such a system could be an effective socialism. It is at least an interesting avenue to consider if mathematical and computational parallels could be constructed.
  - nordsieck 8y ago
    1. I don't think anyone has any illusions that markets are in a mathematical sense optimal. They are a distributed process with no global knowledge - it would be strange if they somehow achieved global optimality. The real question is how efficient are they. 2. If you're serious about > if a government sponsored and modified such an algorithm in an attempt to optimize for equality (second only to efficiency of usage), such a system could be an effective socialism. The big problems you have to overcome are probably the Economic Calculation Problem [0] and the Principal Agent Problem [1]. I have yet to see any reasonable solutions proposed. [0] https://en.wikipedia.org/wiki/Economic_calculation_problem https://en.wikipedia.org/wiki/Economic_calculation_problem [1] https://en.wikipedia.org/wiki/Principal%E2%80%93agent_problem https://en.wikipedia.org/wiki/Principal%E2%80%93agent_proble...
aatchb 8y ago
I'm amazed that someone has written a paper that considers computational complexity that isn't written in LaTeX...
- fabatka 8y ago
  And the whole text is left justified... I'm appalled as well
- eXpl0it3r 8y ago
  While I'm not a fan of everything LaTeX with default layouts, this Word doc isn't very readable and the default design isn't helping.
- viraptor 8y ago
  That reminds me of Scott Aaronson's post about the early signs a complexity paper is unlikely to be valid: https://www.scottaaronson.com/blog/?p=304 https://www.scottaaronson.com/blog/?p=304 Not tex is the first point.
- joeberon 8y ago
  agreed, can't believe they even let it on the archive!
- hx2a 8y ago
  There is a LaTeX version of the paper available: https://content.iospress.com/articles/algorithmic-finance/af007 https://content.iospress.com/articles/algorithmic-finance/af...
Yuioup 8y ago
Can't markets just assume that it is and move on. It's not like markets never do speculation /s
- captainbland 8y ago
  This is bad news for the technology business when those markets only 'efficiently' allocate capital to companies that attempt to exploit P=NP.
QML 8y ago
What does this mean for the class of PPAD-complete [1] problems? Someone correct me if I'm wrong, but if 1. Nash Equilibrium ⊂ FNP 2. "Markets are efficient" => FNP ⊂ FP How is this different from "FP = FNP if and only if P = NP" [2], which is a result already found? [1] https://en.wikipedia.org/wiki/PPAD_(complexity) https://en.wikipedia.org/wiki/PPAD_(complexity) [2] https://en.wikipedia.org/wiki/FNP_(complexity) https://en.wikipedia.org/wiki/FNP_(complexity)
AKifer 8y ago
Efficient or not efficient, as long as it can make me rich, I'm OK with it.
lend000 8y ago
Interesting topic and thought experiment. But this theory is not very fleshed out and not at all convincing (especially the part regarding using an existing efficient market to perform computation for anything other than price of the underlying instrument, i.e. what the computation is intended for). The following quote sums up how the author makes very open ended assumptions: > So what should the market do? If it is truly efficient, and there exists some way to execute all of those separate OCO orders in such a way that an overall profit is guaranteed, including taking into account the larger transactions costs from executing more orders, then the market, by its assumed efficiency, ought to be able to find a way to do so. In other words, the market allows us to compute in polynomial time the solution to an arbitrary 3-SAT problem. In reality, most financial markets are pretty efficient but none are perfectly efficient -- if they were perfectly efficient, it would imply not only perfectly efficient trading systems and an inability to get an 'edge' on the market, but also perfectly efficient market systems, which are limited by technology, conventions, and regulations (for example, significant inefficiencies arise in US securities from not being open all the time, with very little liquidity still available in the 'after hours' markets). To achieve even 'pretty good' efficiency requires significant energy, and I'm not sure I understand how the author can imply that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price. As a trader, I can tell you that most market participants do not care to verify past calculations of the current price; they only care about the future price, and will generate an action from the differential between the predicted price and the current price.
- Ar-Curunir 8y ago
  > I'm not sure I understand the author's implication that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price. That's just what P = NP means: the cost to verify a solution is the same as the cost of finding one.
  - lend000 8y ago
    Yes, but how the author relates that to a market's continuous price calculations is beyond me.
known 8y ago
https://en.wikipedia.org/wiki/Information_asymmetry https://en.wikipedia.org/wiki/Information_asymmetry is still rampant e.g https://www.economist.com/books-and-arts/2018/06/02/the-rise-and-fall-of-elizabeth-holmes-silicon-valleys-startup-queen https://www.economist.com/books-and-arts/2018/06/02/the-rise...
argestes 8y ago
Does this also mean if we can prove that markets are efficient then P = NP?
- adtac 8y ago
  Yes.
Rainymood 8y ago
Interesting. It is well known in the high-frequency literature that at frequencies higher than 5-minute one obtains market microstructure noise. The observations you observe do not fully reflect the "true" price. I.e. you observe bid/ask quotes with a spread and the "true" price is somewhere in between. This is due to the bid-ask bounce and other latency factors. How can markets ever be efficient if we can not observe the true price of something?
- totalZero 8y ago
  There's a transaction cost in either direction. If you buy a call option, the market-maker buys stock to hedge it. That moves the underlier, and raises the price of the call option he just sold. The reverse is true if you sell a call (or buy a put). Not only that, but there is a cost for all the people and computers that your order touches as it gets executed. Without price impact from transactions, markets can't be efficient, because new information has to get priced into the market somehow.
- fabatka 8y ago
  I'm not familiar with high-frequency literature, but you can rarely measure something with 100% accuracy. Despite this, your house got built even if its measurements were taken with a +-0.5cm error. So if the noise is sufficiently small, you can know the true price with enough precision. I don't know if that is the case though.
deleted 8y ago
[deleted]
MaysonL 8y ago
Somehow this seems to be a confusion of categories: markets are real-world mechanisms, while P and NP are mathematical abstractions. Does not compute. To the extent that it does, it's typical mathematical macroeconomic BS.
- adrianN 8y ago
  I economics you sometimes define mathematical objects to model real world markets. It's these models that the paper talks about.
- talltimtom 8y ago
  Markets are a conceptual and mathematica abstaction used to describe the real world.... so is computation.
- coldtea 8y ago
  >markets are real-world mechanisms, while P and NP are mathematical abstractions We use mathematical abstractions to model real-world mechanism every day for millennia. Not only that, but there are all kinds of mathematically defined limits that no real-world mechanism can bypass, from a purely logical perspective. If you only have 10 dollars and I give you 20 dollars, you'll have 30 dollars, not 500 -- that's a mathematical truth that absolutely holds in the real world too.
- jonathanstrange 8y ago
  Since when do mathematical limitations not apply to the real world? Have you ever tried to square the circle?
  - ernst_klim 8y ago
    Let's start with the fact that circles do not exist in the real world.
    - jonathanstrange 8y ago
      Well, that's a quite insubstantial point, to say the least. Mathematical theorems place upper and lower bounds on what is possible in the real world within almost every domain. Of course, there may often be other reasons why something is impossible, too.
grosjona 8y ago
The market cannot be efficient because a large portion of public information is not true. Even if all the information was true, there is still the problem that humans have very poor reasoning abilities combined with herd mentality which almost always overrides the reasoning part. To predict the market, you don't need to understand the market, you need to understand people's distorted view of the market.
John_KZ 8y ago
That's why we need peer-review.
mortdeus 8y ago
"For simplicity but without loss of generality, assume there are n past price changes, each of which is either UP (1) or DOWN (0)." You know, this is the kind of thing that makes me wonder about how much quantum computation is going to change the game. Where we aren't just calculating ups and downs but superpositions between the two.
- cheschire 8y ago
  Digital is a framework built on top of analog. Boolean logic is the foundation of all of our modern computing, and so we built all of our circuits around the ability to handle HIGH and LOW signals. What your describing seems to me like you're saying that leveraging an analog signal is the benefit of quantum computation. If so, I don't really agree. If not, then I misunderstood. Either way, I suspect that the superposition between the change in value and the change in time, in relation to all of the other superpositions in value/time changes, is the true computational power of quantum technology.
maxehmookau 8y ago
The title of this post scores 10000 HN points.
viraghr 8y ago
Have another account here but don't want to take the karma hit for being a crank. I published this 2-page proof that the EMH is false: https://arxiv.org/abs/1011.0423 https://arxiv.org/abs/1011.0423 (didn't set the date so in the document it's wrong, this was published 2010.) It doesn't depend on P = NP, it's simply a rigorous proof that EMH is false. Let's switch gears a second. Here's a famous elementary proof[1] that there are infinite primes. Suppose there are just finite primes, up to some largest. Multiply them together and add one. No prime divides the new number (because "every" prime leaves a remainder 1), so you've just produced a new prime. This new prime is larger than the largest prime in your finite set because you multiplied that by the rest of them and added one to get it. So this is a contradiction, you couldn't have had finite primes up to some largest. Anyway if you think there might be a largest prime after what you just read, it just means you don't understand the proof. If you believe EMH might be true it just means you don't understand the proof that it is false. Of course, nobody ever even hypothesized that academia was efficient :) [1] https://en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid's_proof https://en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid's_pr... -- EDIT: no mistake in my comment
- csomar 8y ago
  > Have another account here but don't want to take the karma hit for being a crank. Stop worrying about karma and what some random dudes think about you/your comments on HN or whatever online board. If you think it is wrong simply don't do it.
  - zeth___ 8y ago
    You get silenced by karma when you have unpopular opinions. You know, just how people used to tell homosexuals to not be gay when other people thought they were freaks because of it.
    - csomar 8y ago
      What I’m saying is stop worrying about karma and talk your opinions. Karma is not money or air. Your opinion matters.
soVeryTired 8y ago
Meh. Whatever your opinions on P = NP, the efficient markets hypothesis is unfalsifiable. You can only falsify a joint hypothesis of efficiency plus some model of information flow into a market.
- jonathanstrange 8y ago
  Wait a minute, if the paper correctly links a theoretical definition of efficiency to the complexity class and indeed shows that markets can be efficient only iff. P=NP, then any future proof that P!=NP falsifies the thesis that markets are efficient. And most experts agree that if we ever get a proof, then it will be a proof of NP!=P. Knuth is a notable exception, although he has to my knowledge never really vigorously advocated P=NP but merely suggested the possibility that P=NP and that the algorithms to transform NP problems into P problems could be very, very complex but still in P. Seems unlikely, though.
  - argv_empty 8y ago
    The paper doesn't even manage to prove that finding a significantly profitable technical strategy is in NP.
js8 8y ago
Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world. If you want a full critique, read Steve Keen's Debunking Economics, it has a chapter on EMH. Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that as well. Amusingly enough, the first thing that a rational person would do upon discovering a relatively efficient algorithm to solve NP problems would be to cash in all the Bitcoins. Thus proving in practice that no, markets are not really efficient. :-)
- jdironman 8y ago
  Maybe someone knows something we don't and that's why crypto coin was created in the first place? Just having fun speculating guys.
- psergeant 8y ago
  > Frankly, everybody with a bit of economic common sense knows Citation? True Scotsman fallacy?
  - js8 8y ago
    I gave a citation. When I say "everybody with a bit of economic common sense", I mean everybody in economic profession who is able of some elementary reflection on what they are doing. Even most neoclassicals (which is probably the only school where somebody actually believes in EMH) know that many of the theoretical assumptions are bullshit. Another classic example, aside from EMH, is SMD theorem. I am pretty sure that most economic Nobel prize winners do not believe in EMH, from the top of my head, Akerlof and Kahneman.
    - psergeant 8y ago
      You gave a link to a popsci book whose Wikipedia Criticism section is ... unforgiving and relentless. You then double down on your True Scotsman fallacy, mae a sweeping unsupported claim about a nebulous group of people, and follow it up with another conjecture about another group in an attempt to appeal to authority. We can do better than this.
mortdeus 8y ago
So just to better understand the issue of P=NP, am I right in assuming that an NP problem is like trying to build a neural net for image recognition? In the sense that it takes a huge amount of time and images to train the thing to become smart (in other words, to go through the entire network of neurons one by one and assign better weight values etc) but when it comes to actually verifying if our network is smart all it takes is to run an image straight through the network? And the issue of trying to prove N=NP is essentially trying to prove that there isn't a magical way to train a neural network with just one image of training data?
- yoklov 8y ago
  No, I don't think building a neural net for image recognition qualifies. NP problems are essentially problems where the following two properties hold: 1. No better algorithm is known than using brute force -- generating every possible result and checking if it's a valid result. 2. Checking that the given result is valid is doable in polynomial time or better. (This is less critical to understanding, but essentially your `isValidSolution(input, solution)` function needs to take `O(n)`, `O(n^2)`, `O(n^3)`, (etc.) time or better.) Essentially, a NP problem is a problem where you have to brute force the solution, but it's easy to know when you've found the correct solution. If P = NP that means that there are no problems where this is true -- it would mean that any problem where it's easy to know if you've found the solution also has an algorithm for finding it more efficiently than brute force. Your neural network example doesn't apply because training a neural network doesn't require brute forcing the solution space of the neural network weights. That would be crazy. So it's a problem in P.
  - zaarn 8y ago
    Re1: the problem here goes a bit deeper, classically the NP problem is a problem which requires a non-deterministic turing machine to solve. Ie a machine that can explore multiple outcomes at once, even the entire problem space to some extend. A non-deterministic turing machine can interprete multiple instructions (write 5 to tape and go to state 2 OR write 3 to tape and go to state 19) and (depending on interpretation) use the instruction that gives the result fastest or explore all instruction branches at once. Note that the "OR" in there is not a classical if-else, it means literally the machine can pick one. There is no memory value that tells it which is correct. Basically, problems that are polynomial on a NDTM will likely be NP on a normal machine (with some exceptions depending on the problem). Re2: As above, verifying is actually easy as you can then simply follow the execution branch the NDTM picked on a normal deterministic turing machine. Atleast this above is what I learned in CS course 2nd semester.
devnull791101 8y ago
free market efficiency is an evolutionary concept not accounting one. there's no intelligent design.
sddfd 8y ago
Even if P ist not equal NP, hardness of efficient markets could be in APX2 i.e. computing a solution that is at most twice as bad as the optimal solution is in P.
zwww 8y ago
Most people seem to read this as a proof that markets are inherently flawed and as lending support to their ideological distrust of market economies. I think that if the authors thesis holds true and p indeed != np, this kind of conclusion could spell an even bigger problem for those who advocate to agument or replace market economies with another, typically more centralized, form of economic calculation. Allende's cybersyn famously used linear programming (P) in order to centrally 'simulate' and improve upon more regular market mechanics. If the authors thesis holds I think it's actually an argument in favor of the economic calculation problem talking point of Hayek and the like: efficient calculation of economic distribution problems is impossible and flawed dynamics of the market are probably close to the best approximation we can afford.
- Iv 8y ago
  When I tried to read about Allende's cybersyn all I could find are a few retro-futuristic furniture, but no meat whatsoever about the kind of software that was behind. It looked like pure PR to me. Do you have good sources about it? It has always intrigued me. Personally I think it is very unlikely that the markets are close to the best approximation we can afford. The current market-making agents use limited intelligence on limited data. It is an efficient system in the sense that it beats randomness and it beats a central (human) intelligence with (allegedly) superior access to information.
  - baursak 8y ago
    I'm interested in this. So far, the best resources I found are: - "Red Plenty" by Francis Spufford, a mix of fiction and non-fiction about planning experience in the USSR. It includes a rich bibliography and references to papers published over the past 70 years around this issue. - There are few papers by Chinese economists, most notably this one: https://boingboing.net/2017/09/14/platform-socialism.html https://boingboing.net/2017/09/14/platform-socialism.html (you have to mess around with Sci-Hub mirrors to get a free copy). - There are few papers and books by Michael Ellman, e.g.: https://www.amazon.com/Planning-Problems-USSR-Contribution-Mathematical/dp/0521202493/ref https://www.amazon.com/Planning-Problems-USSR-Contribution-M... - I also have a few primers on linear programming in my to-do list, e.g.: https://www.amazon.com/gp/product/0486654915/ https://www.amazon.com/gp/product/0486654915/ - Somewhat tangential, but "the greatest American capitalist" ripping into EMH is a fun read too: https://www8.gsb.columbia.edu/articles/columbia-business/superinvestors https://www8.gsb.columbia.edu/articles/columbia-business/sup... None of these really talk about the software still, but I would imagine a combination of: - existing supply-chain systems already in place at Amazon, Walmart, etc., - something along the lines of non-monetary Kickstarter to gauge popularity of ideas from the ground up, and encourage innovation - strong democratic institutions - still allow free market at low levels, like individual entrepreneurs that don't employ anybody (once you employ someone, it must be a co-op). Dunno, these are just random ideas in my head. :)
babypistol 8y ago
I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me. But in the article, there is an interesting section on that: > If P = NP, even with a high exponent on the polynomial, that means that checking strategies from the past becomes only polynomially harder as time passes and data is aggregated. But so long as the combined computational power of financial market participants continues to grow exponentially, either through population growth or technological advances, then there will always come a time when all past strategies can be quickly backtested by the then-prevailing amount of computational power. In short, so long as P = NP, the markets will ultimately be efficient, regardless of how high the exponent on the polynomial is; the only question is when, and the answer depends on the available computational power. So this section, if I understand it correctly, says that problems in P are easy because the computational power in the world grows exponentially and we can assume that they will at least once become feasible to solve. That's an interesting way of looking at it. Is this really the reason why we consider polynomial problems much easier than NP-hard ones?
- leereeves 8y ago
  That's assuming computational resources could grow forever without limit, which of course they can't.
  - QML 8y ago
    To add on: Moore's law is "dying", and that places further pressure on algorithms to get faster. However, even in an exponential world, I am reminded of a quote: "exponential algorithms make polynomially slow progress, while polynomial algorithms advance exponentially fast".
  - babypistol 8y ago
    Yeah, in this case we are back to square one and P vs NP again seems irrelevant to me.
yeslibertarian 8y ago
Government is obviously much more efficient than the market. Venezuela, Cuba and North Corea are a good testament of that.
em70 8y ago
This paper is rubbish. Trading is ultimately a partial information, sequential game with an unknown number of participants whose payoff functions (and utilities) are also unknown. Could the market be closer to being efficient if P=NP? Likely. Does P=NP imply efficiency? Not at all.
- naasking 8y ago
  You seem to be missing the point. Markets were and possibly still are widely considered weak-form efficient. This is a disproof of that conjecture by showing an inherent contradiction between widely believed properties, ie. P!=NP and markets are weak-form efficient, therefore at least one of them is false. Edit: "Does P=NP imply efficiency? Not at all." This isn't even a claim of the paper. The paper is claiming the opposite, that market efficiency is true only if P=NP.
- danbruc 8y ago
  Is it even theoretically possible to show that markets are efficient on purely theoretical grounds? As a thought experiment, imagine that all human brains have a weird defect that causes them to always ignore some specific kind of information when making pricing decisions, including when they write software dealing with those decisions, and under all other conceivable circumstances. In that case, it seems to me, it would be impossible to decide on purely theoretical grounds that markets are efficient because it strictly depends on the empirical observation that human brains have this weird defect. I could imagine the other way around to work, i.e. that there could be an obstruction to markets being efficient that can be shown to exist on purely theoretical grounds. But no matter what the answer to the second question is, in no case could you arrive at an »if and only if« result without including the empirical observation that brains do not have this weird defect.
- epr 8y ago
  The entire premise of this paper is complete nonsense, and serves only to demonstrate the authors complete lack of understanding when it comes to the subject of markets. "Trading is ultimately a partial information, sequential game with an unknown number of participants whose payoff functions (and utilities) are also unknown." Markets in general are essentially an infinitely-armed bandit problem where everyone plays whether they know it or not, and resources are allocated over time in a manner not unlike evolution.
TekMol 8y ago
As I understand it, his argument is that there might be information available that needs time to interpret. And that the time the market took to interpret the available data is not sufficient to gain the maximum insight possible. So that somebody with more computing power then the market could beat the market. I don't see that as an argument against the EMH. I think it is inherent in the EMH that the market has more computing power then any individual. I would say that it is the core of the EMH. That more people make better predictions. Because they have more computing power. I always found it strange that the EMH is often defined as the market price including all available data. As if the data can simply be added without interpretation.
inputcoffee 8y ago
The author’s claim only applies to weak form of market efficiency. The original Fama paper distinguishes between three forms of the EMH: weak, semi strong and strong. The weak form only alleges that historical price info is fully incorporated in the current price. You can still make money by working hard and figuring things out from outside the price history. The weak form applies to purely technical trading that extracts value from price history like momentum and the simple moving averages cross over studies you see.
Symmetry 8y ago
I don't think anybody would claim that even the weak form of the EMH applies in all cases. Like the idea that objects of different weights fall at the same speed it's an approximation that can be very close to true in some cases but can be badly misleading in others. If you've ever listened to economists talk about prediction markets they always seem to bring up the idea that markets with low capitalization have low efficiency. And even looking at the highly capitalized stock market I know at least one story of a major player that got its start noticing a violation of weak-form efficiency and becoming very rich by fixing the violation. There's no reason to think that actual markets are now finally efficient and in fact there are some that are publicly know, but which only bring a small return and require decades of investment to fix so nobody is interested in trying.
adament 8y ago
First of all this paper leaves a lot to be desired in terms of rigor and it is for good reason not how mathematics is written by most mathematicians. It is very conversational and assumptions and derivations are jumbled together, while you sometimes find these in breakthrough papers from visionary mathematicians it often makes it harder to verify. My understanding of the central argument in the paper is the following: Definition: Let N be a positive integer denoting the length of the history, M be a positive integer denoting the number of assets. A market realization is an element of {-1, 1}^(NxM), i.e. M vectors of length n where all entries are either +1 or -1. Definition: We call a function f: {-1, 1}^(TxM) -> {0, 1}^M satisfying f \circ s = s \circ f for s any element in the symmetric group S_M a technical strategy of lookback T. The symmetric group condition just states that permuting the vectors of length T among the M assets is the same as permuting the output the strategy. I.e. that the strategy has no inherent preferences among the assets. The payoff of a technical strategy s on a market realization h is given by payoff(s, h) = \sum_{i=T}^N s(h_{i-T, ..., i-1}) \cdot h_i where the indexation is in the time dimension i.e. h_i denotes a length M vector. The budget of a technical strategy is budget(s) = max_{v \in {-1, 1}^TxM} s(v) \cdot (1, ..., 1). That is the maximal number of assets it wants to hold in any given state of the world. Given a market realization h, positive integers B and K we say that h is (B, K) EMH-inconsistent if there exists a technical strategy s such that budget(s) <= B and payoff(s, h) >= K. If a market realization h is not (B, K) EMH-inconsistent we call it (B, K) EMH-consistent. Claim (presented as a theorem in the paper): The problem of determining whether a market realization is (B, K) EMH-consistent is in P if and only if the knapsack problem is in P. Claim: The weak efficient market hypothesis is true if and only if EMH-consistency is in P. In the second part of the paper he indicates a model of an order book where he wants to encode 3-SAT as combinations of market orders. I do not understand how this is intended to work, i.e. if all information is available and incorporated into the market and the information generating process is stopped, and I have bid-offer spreads because of transaction costs, and I irrationally (remember I am not interested in the buying or selling the security, I am just interested in solving a 3-SAT problem, thus my actions should not influence the price generation process of an efficient market) enter an OCO-3 order to buy A, B or C at mid. Why should this result in a transaction? In the case (a or a or a) and (!a or !a or !a) I make one trade with myself in the case (a or a or a) and (b or b or b) and (!a or b or b) I make one trade with myself, but one of the problems is satisfiable the other is not. Now it seems obvious that by inventing new order types we can get order book rules that allow for complex computation to resolve clearing, however this is a problem with the proposed order types not the efficient market hypothesis? A (to me) equivalent avenue of investigation would be to imagine different order types such that to decide the clearing of an order book it would involve solving an undecidable problem - i.e. what are the most reasonable order types and order book rules such that we can encode the halting problem?
splitrocket 8y ago
Profit is the measure of inefficiency in a market.
jkingsbery 8y ago
> "But given that there are 3n patterns to test, finding a solution, as opposed to verifying one, requires O(3^n), i.e. it is exponential in the size of n. For small n, this is computable, even though it is exponential. But as n grows, it becomes impossible to check every possible pattern quickly." If a strategy is a sequence of BUY-HOLD-SELL decisions, then just because there's O(3^n) strategies doesn't mean you need to evaluate them all. It seems pretty easy (if a strategy is only defined in retrospect) to define a greedy algorithm that finds the optimal strategy. (see page 16.) The author goes on to compare this to the Knapsack problem (pg 19). The thing that makes the Knapsack question (and NP-complete problems generally) hard is that greedy algorithms don't work (as far as we know), whereas it seems like a greedy algorithm work for the problem the author has laid out.
lynal 8y ago
Based on a quick skim, this is not a good paper. Computer scientists writing on economics is great, it's helpful to grow new ideas in the field. Unfortunately they sometimes use economic concepts imprecisely at detriment to their question, methodology, and results. That's the case here. This paper posits a definition of efficiency, but does not explain why that definition is correct or how it relates to other efficiency measures. A better proof of arbitrage opportunities in markets is Wah 2016, which identifies actual arbitrage opportunities in actual markets. Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement? And what is the correct way to concisely and precisely write: "most people familiar with the P = NP problem believe with varying degrees of confidence that P is not equal to NP, but so far no proof exists."
- myWindoonn 8y ago
  Whether P and NP are equal is an arithmetic statement; it's either true or not true, but we may not have the proof systems required to demonstrate it. Your excerpted sentence is already quite concise compared to serious surveys like https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf
- openasocket 8y ago
  > Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement? It actually does have a formal meaning! This is one of the most interesting results (in my opinion) on the P vs NP problem. Given a random oracle R, Pr(P^R != NP^R) = 1. So given a random universe, it is almost certainly true that your version of P != your version of NP. At least that's how my theory prof liked to explain it. Here's a link with the proof: http://theory.stanford.edu/~trevisan/cs254-14/lecture04.pdf http://theory.stanford.edu/~trevisan/cs254-14/lecture04.pdf
tomtimtall 8y ago
Reading this comment thread is hilarious to a degree. I think that it really highlights how much noise gets thrown into a discussion when your naming becomes too relatable. Essentially bike shedding of theory discussion. If the Efficient Market Hypothesis has been called the “Fundamental Market Property Hypothesis M = H” or similar I doubt most would have made the comments they made. But because “efficient market” sounds to relatable most feel that they can comment without even knowing what the specifics of the EMH are.
carapace 8y ago
Er, markets are massively parallel, yes? Um, am I wrong in thinking that P and NP refer to non-parallel algorithms? (Apologies in advance if I'm having a brain fart.)

332 points by perculis 8y ago

wei_jok 8y ago

But markets are not efficient ...

fouc 8y ago
Proof that P does not = NP after all.
coliveira 8y ago
Now this will degenerate into a fight between economists and computer scientists...
- deleted 8y ago
  [deleted]
mdturnerphys 8y ago
"Since P probably does not equal NP, markets are probably not efficient."
sova 8y ago
weak-form efficiency in markets means something special.
- Dylan16807 8y ago
  Not really. It means that the market incorporates all past data. This paper is entertaining but it depends on the assumption that computing power grows exponentially forever and will eventually be able to solve all P problems at negligible cost. That assumption is clearly not justified. And the belief that any market perfectly incorporates data, not a single point off in any stock, is basically a strawman anyway.
  - sova 8y ago
    I don't know! I'm wondering! Because weak-form efficient means something different than strong efficiency, which is what you say when the market perfectly incorporates all data. Just out of curiosity, if the data doesn't go into the market, where does it go? Strong econ minds believe that prices do incorporate all the data necessary for valuation
    - Dylan16807 8y ago
      Sometimes data gets lost. People are making the decisions, and people are sloppy and lossy. Weak and strong are just about which data is incorporated. Neither one addresses the fact that no entity interacting with a market is infallible.
nyolfen 8y ago
is it really so much to ask to read the one paragraph abstract before making a comment like this?

sova 8y ago

P = NP when you nail it. From the paper: "if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. I also prove the converse by showing how we can "program" the market to solve NP-complete problems. However, there has been no proof that there does not exist some algorithm that can determine satisfiability in polynomial time. If such an algorithm were found, then we would have that P = NP. If a proof is discovered that no such algorithm exists, then we would have that P ≠ NP. Just as most people in the field of finance believe markets are at least weak-form efficient, most computer scientists believe P ≠ NP. Gasarch (2002) reports that of 100 respondents to his poll of various theorists who are “people whose opinions can be taken seriously,” the majority thought the ultimate resolution to the question would be that P ≠ NP; only 9 percent thought the ultimate resolution would be that P = NP. The majority of financial academics believe in weak form efficiency and the majority of computer scientists believe that P ≠ NP. The result of this paper is that they cannot both be right: either P = NP and the markets are weakly efficient, or P ≠ NP and the markets are not weakly efficient. "

hvidgaard 8y ago
That actually sounds like a refreshingly fun paper to read.
- sova 8y ago
  Only if you can nerd out about EMH "Efficient Market Hypothesis" for 33 pages

arrownot 8y ago

What kind of markets get created when the input to the NP problem is 2^10000, I think our idea of markets are based on small scale transactions and extrapolations can't take into account intelligent agents. Also Arrow's theorem hints how small formals systems can't achieve agents desires. Anyway, I have only read the title not the arxig paper.

CJefferson 8y ago

While this is a fun, the title is a little strong. There are three limitations (whuch apply to many papers about P=NP). 1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error. 2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true. 3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.

SolarNet 8y ago
On two, as this appears to be a cross disciplinary paper, it's important to consider that some economists currently claim markets are efficient (the efficient market hypothesis, which is like a big open question in economics). By drawing a link between the EMH and P=NP (which many computer scientists believe is unlikely) the author is linking two open questions with opposing beliefs. So I think point two is sort of a technicality that with context it should be understood that the author is specifically talking about two open questions as they stand today. Also to further hammer home the point, due to the phrasing of the EMH, although no one may currently be using P=NP, markets would still have the efficiency property now even if no one is exploiting it. Perhaps this sort of vacuously true statement rubs you the wrong way (like it does me a bit) with the strength of the "if and only if" the author used. But if you read "markets are efficient" as the EMH then it is still a valid literal formulation. On three, sure that's great for reality. But for the formulation of markets being efficient as an inherent property (again the EMH) of markets, the size of the market could be held as effectively infinite (or at least extremely large) and the property should still hold. At some point the size of the theoretical market will explode the polynomial, and for the EMH to hold P=NP must be true.
- stale2002 8y ago
  In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. IE, it is almost as good. So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough. Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin with.

cargocult_coder 8y ago

Therefore it's false.

modeless 8y ago

Before people get too carried away criticising markets, check this quote from the paper. > The results of this paper should not be interpreted as support for government intervention into the market; on the contrary, the fact that market efficiency and computational efficiency are linked suggests that government should no more intervene in the market or regulate market participants than it should intervene in computations or regulate computer algorithms.

kome 8y ago
well, governments should do both. Computer algorithms can be a very subtle form of power. And of course we should have a degree of public control over them.
SolarNet 8y ago
Sure, but if what the author is saying is true, then it implies that there is nothing special about markets, and a system involving an equal number of humans and computers following some other optimization algorithm could achieve similar results in efficiency. And if a government sponsored and modified such an algorithm in an attempt to optimize for equality (second only to efficiency of usage), such a system could be an effective socialism. It is at least an interesting avenue to consider if mathematical and computational parallels could be constructed.
- nordsieck 8y ago
  1. I don't think anyone has any illusions that markets are in a mathematical sense optimal. They are a distributed process with no global knowledge - it would be strange if they somehow achieved global optimality. The real question is how efficient are they. 2. If you're serious about > if a government sponsored and modified such an algorithm in an attempt to optimize for equality (second only to efficiency of usage), such a system could be an effective socialism. The big problems you have to overcome are probably the Economic Calculation Problem [0] and the Principal Agent Problem [1]. I have yet to see any reasonable solutions proposed. [0] https://en.wikipedia.org/wiki/Economic_calculation_problem https://en.wikipedia.org/wiki/Economic_calculation_problem [1] https://en.wikipedia.org/wiki/Principal%E2%80%93agent_problem https://en.wikipedia.org/wiki/Principal%E2%80%93agent_proble...

aatchb 8y ago

I'm amazed that someone has written a paper that considers computational complexity that isn't written in LaTeX...

fabatka 8y ago
And the whole text is left justified... I'm appalled as well
eXpl0it3r 8y ago
While I'm not a fan of everything LaTeX with default layouts, this Word doc isn't very readable and the default design isn't helping.
viraptor 8y ago
That reminds me of Scott Aaronson's post about the early signs a complexity paper is unlikely to be valid: https://www.scottaaronson.com/blog/?p=304 https://www.scottaaronson.com/blog/?p=304 Not tex is the first point.
joeberon 8y ago
agreed, can't believe they even let it on the archive!
hx2a 8y ago
There is a LaTeX version of the paper available: https://content.iospress.com/articles/algorithmic-finance/af007 https://content.iospress.com/articles/algorithmic-finance/af...

Yuioup 8y ago

Can't markets just assume that it is and move on. It's not like markets never do speculation /s

captainbland 8y ago
This is bad news for the technology business when those markets only 'efficiently' allocate capital to companies that attempt to exploit P=NP.

QML 8y ago

What does this mean for the class of PPAD-complete [1] problems? Someone correct me if I'm wrong, but if 1. Nash Equilibrium ⊂ FNP 2. "Markets are efficient" => FNP ⊂ FP How is this different from "FP = FNP if and only if P = NP" [2], which is a result already found? [1] https://en.wikipedia.org/wiki/PPAD_(complexity) https://en.wikipedia.org/wiki/PPAD_(complexity) [2] https://en.wikipedia.org/wiki/FNP_(complexity) https://en.wikipedia.org/wiki/FNP_(complexity)

AKifer 8y ago

Efficient or not efficient, as long as it can make me rich, I'm OK with it.

lend000 8y ago

Interesting topic and thought experiment. But this theory is not very fleshed out and not at all convincing (especially the part regarding using an existing efficient market to perform computation for anything other than price of the underlying instrument, i.e. what the computation is intended for). The following quote sums up how the author makes very open ended assumptions: > So what should the market do? If it is truly efficient, and there exists some way to execute all of those separate OCO orders in such a way that an overall profit is guaranteed, including taking into account the larger transactions costs from executing more orders, then the market, by its assumed efficiency, ought to be able to find a way to do so. In other words, the market allows us to compute in polynomial time the solution to an arbitrary 3-SAT problem. In reality, most financial markets are pretty efficient but none are perfectly efficient -- if they were perfectly efficient, it would imply not only perfectly efficient trading systems and an inability to get an 'edge' on the market, but also perfectly efficient market systems, which are limited by technology, conventions, and regulations (for example, significant inefficiencies arise in US securities from not being open all the time, with very little liquidity still available in the 'after hours' markets). To achieve even 'pretty good' efficiency requires significant energy, and I'm not sure I understand how the author can imply that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price. As a trader, I can tell you that most market participants do not care to verify past calculations of the current price; they only care about the future price, and will generate an action from the differential between the predicted price and the current price.

Ar-Curunir 8y ago
> I'm not sure I understand the author's implication that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price. That's just what P = NP means: the cost to verify a solution is the same as the cost of finding one.
- lend000 8y ago
  Yes, but how the author relates that to a market's continuous price calculations is beyond me.

known 8y ago

https://en.wikipedia.org/wiki/Information_asymmetry https://en.wikipedia.org/wiki/Information_asymmetry is still rampant e.g https://www.economist.com/books-and-arts/2018/06/02/the-rise-and-fall-of-elizabeth-holmes-silicon-valleys-startup-queen https://www.economist.com/books-and-arts/2018/06/02/the-rise...

argestes 8y ago

Does this also mean if we can prove that markets are efficient then P = NP?

adtac 8y ago
Yes.

Rainymood 8y ago

Interesting. It is well known in the high-frequency literature that at frequencies higher than 5-minute one obtains market microstructure noise. The observations you observe do not fully reflect the "true" price. I.e. you observe bid/ask quotes with a spread and the "true" price is somewhere in between. This is due to the bid-ask bounce and other latency factors. How can markets ever be efficient if we can not observe the true price of something?

totalZero 8y ago
There's a transaction cost in either direction. If you buy a call option, the market-maker buys stock to hedge it. That moves the underlier, and raises the price of the call option he just sold. The reverse is true if you sell a call (or buy a put). Not only that, but there is a cost for all the people and computers that your order touches as it gets executed. Without price impact from transactions, markets can't be efficient, because new information has to get priced into the market somehow.
fabatka 8y ago
I'm not familiar with high-frequency literature, but you can rarely measure something with 100% accuracy. Despite this, your house got built even if its measurements were taken with a +-0.5cm error. So if the noise is sufficiently small, you can know the true price with enough precision. I don't know if that is the case though.

deleted 8y ago

[deleted]

MaysonL 8y ago

Somehow this seems to be a confusion of categories: markets are real-world mechanisms, while P and NP are mathematical abstractions. Does not compute. To the extent that it does, it's typical mathematical macroeconomic BS.

adrianN 8y ago
I economics you sometimes define mathematical objects to model real world markets. It's these models that the paper talks about.
talltimtom 8y ago
Markets are a conceptual and mathematica abstaction used to describe the real world.... so is computation.
coldtea 8y ago
>markets are real-world mechanisms, while P and NP are mathematical abstractions We use mathematical abstractions to model real-world mechanism every day for millennia. Not only that, but there are all kinds of mathematically defined limits that no real-world mechanism can bypass, from a purely logical perspective. If you only have 10 dollars and I give you 20 dollars, you'll have 30 dollars, not 500 -- that's a mathematical truth that absolutely holds in the real world too.
jonathanstrange 8y ago
Since when do mathematical limitations not apply to the real world? Have you ever tried to square the circle?
- ernst_klim 8y ago
  Let's start with the fact that circles do not exist in the real world.
  - jonathanstrange 8y ago
    Well, that's a quite insubstantial point, to say the least. Mathematical theorems place upper and lower bounds on what is possible in the real world within almost every domain. Of course, there may often be other reasons why something is impossible, too.

grosjona 8y ago

The market cannot be efficient because a large portion of public information is not true. Even if all the information was true, there is still the problem that humans have very poor reasoning abilities combined with herd mentality which almost always overrides the reasoning part. To predict the market, you don't need to understand the market, you need to understand people's distorted view of the market.

John_KZ 8y ago

That's why we need peer-review.

mortdeus 8y ago

"For simplicity but without loss of generality, assume there are n past price changes, each of which is either UP (1) or DOWN (0)." You know, this is the kind of thing that makes me wonder about how much quantum computation is going to change the game. Where we aren't just calculating ups and downs but superpositions between the two.

cheschire 8y ago
Digital is a framework built on top of analog. Boolean logic is the foundation of all of our modern computing, and so we built all of our circuits around the ability to handle HIGH and LOW signals. What your describing seems to me like you're saying that leveraging an analog signal is the benefit of quantum computation. If so, I don't really agree. If not, then I misunderstood. Either way, I suspect that the superposition between the change in value and the change in time, in relation to all of the other superpositions in value/time changes, is the true computational power of quantum technology.

maxehmookau 8y ago

The title of this post scores 10000 HN points.

viraghr 8y ago

Have another account here but don't want to take the karma hit for being a crank. I published this 2-page proof that the EMH is false: https://arxiv.org/abs/1011.0423 https://arxiv.org/abs/1011.0423 (didn't set the date so in the document it's wrong, this was published 2010.) It doesn't depend on P = NP, it's simply a rigorous proof that EMH is false. Let's switch gears a second. Here's a famous elementary proof[1] that there are infinite primes. Suppose there are just finite primes, up to some largest. Multiply them together and add one. No prime divides the new number (because "every" prime leaves a remainder 1), so you've just produced a new prime. This new prime is larger than the largest prime in your finite set because you multiplied that by the rest of them and added one to get it. So this is a contradiction, you couldn't have had finite primes up to some largest. Anyway if you think there might be a largest prime after what you just read, it just means you don't understand the proof. If you believe EMH might be true it just means you don't understand the proof that it is false. Of course, nobody ever even hypothesized that academia was efficient :) [1] https://en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid's_proof https://en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid's_pr... -- EDIT: no mistake in my comment

csomar 8y ago
> Have another account here but don't want to take the karma hit for being a crank. Stop worrying about karma and what some random dudes think about you/your comments on HN or whatever online board. If you think it is wrong simply don't do it.
- zeth___ 8y ago
  You get silenced by karma when you have unpopular opinions. You know, just how people used to tell homosexuals to not be gay when other people thought they were freaks because of it.
  - csomar 8y ago
    What I’m saying is stop worrying about karma and talk your opinions. Karma is not money or air. Your opinion matters.

soVeryTired 8y ago

Meh. Whatever your opinions on P = NP, the efficient markets hypothesis is unfalsifiable. You can only falsify a joint hypothesis of efficiency plus some model of information flow into a market.

jonathanstrange 8y ago
Wait a minute, if the paper correctly links a theoretical definition of efficiency to the complexity class and indeed shows that markets can be efficient only iff. P=NP, then any future proof that P!=NP falsifies the thesis that markets are efficient. And most experts agree that if we ever get a proof, then it will be a proof of NP!=P. Knuth is a notable exception, although he has to my knowledge never really vigorously advocated P=NP but merely suggested the possibility that P=NP and that the algorithms to transform NP problems into P problems could be very, very complex but still in P. Seems unlikely, though.
- argv_empty 8y ago
  The paper doesn't even manage to prove that finding a significantly profitable technical strategy is in NP.

js8 8y ago

Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world. If you want a full critique, read Steve Keen's Debunking Economics, it has a chapter on EMH. Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that as well. Amusingly enough, the first thing that a rational person would do upon discovering a relatively efficient algorithm to solve NP problems would be to cash in all the Bitcoins. Thus proving in practice that no, markets are not really efficient. :-)

jdironman 8y ago
Maybe someone knows something we don't and that's why crypto coin was created in the first place? Just having fun speculating guys.
psergeant 8y ago
> Frankly, everybody with a bit of economic common sense knows Citation? True Scotsman fallacy?
- js8 8y ago
  I gave a citation. When I say "everybody with a bit of economic common sense", I mean everybody in economic profession who is able of some elementary reflection on what they are doing. Even most neoclassicals (which is probably the only school where somebody actually believes in EMH) know that many of the theoretical assumptions are bullshit. Another classic example, aside from EMH, is SMD theorem. I am pretty sure that most economic Nobel prize winners do not believe in EMH, from the top of my head, Akerlof and Kahneman.
  - psergeant 8y ago
    You gave a link to a popsci book whose Wikipedia Criticism section is ... unforgiving and relentless. You then double down on your True Scotsman fallacy, mae a sweeping unsupported claim about a nebulous group of people, and follow it up with another conjecture about another group in an attempt to appeal to authority. We can do better than this.

mortdeus 8y ago

So just to better understand the issue of P=NP, am I right in assuming that an NP problem is like trying to build a neural net for image recognition? In the sense that it takes a huge amount of time and images to train the thing to become smart (in other words, to go through the entire network of neurons one by one and assign better weight values etc) but when it comes to actually verifying if our network is smart all it takes is to run an image straight through the network? And the issue of trying to prove N=NP is essentially trying to prove that there isn't a magical way to train a neural network with just one image of training data?

yoklov 8y ago
No, I don't think building a neural net for image recognition qualifies. NP problems are essentially problems where the following two properties hold: 1. No better algorithm is known than using brute force -- generating every possible result and checking if it's a valid result. 2. Checking that the given result is valid is doable in polynomial time or better. (This is less critical to understanding, but essentially your `isValidSolution(input, solution)` function needs to take `O(n)`, `O(n^2)`, `O(n^3)`, (etc.) time or better.) Essentially, a NP problem is a problem where you have to brute force the solution, but it's easy to know when you've found the correct solution. If P = NP that means that there are no problems where this is true -- it would mean that any problem where it's easy to know if you've found the solution also has an algorithm for finding it more efficiently than brute force. Your neural network example doesn't apply because training a neural network doesn't require brute forcing the solution space of the neural network weights. That would be crazy. So it's a problem in P.
- zaarn 8y ago
  Re1: the problem here goes a bit deeper, classically the NP problem is a problem which requires a non-deterministic turing machine to solve. Ie a machine that can explore multiple outcomes at once, even the entire problem space to some extend. A non-deterministic turing machine can interprete multiple instructions (write 5 to tape and go to state 2 OR write 3 to tape and go to state 19) and (depending on interpretation) use the instruction that gives the result fastest or explore all instruction branches at once. Note that the "OR" in there is not a classical if-else, it means literally the machine can pick one. There is no memory value that tells it which is correct. Basically, problems that are polynomial on a NDTM will likely be NP on a normal machine (with some exceptions depending on the problem). Re2: As above, verifying is actually easy as you can then simply follow the execution branch the NDTM picked on a normal deterministic turing machine. Atleast this above is what I learned in CS course 2nd semester.

devnull791101 8y ago

free market efficiency is an evolutionary concept not accounting one. there's no intelligent design.

sddfd 8y ago

Even if P ist not equal NP, hardness of efficient markets could be in APX2 i.e. computing a solution that is at most twice as bad as the optimal solution is in P.

zwww 8y ago

Most people seem to read this as a proof that markets are inherently flawed and as lending support to their ideological distrust of market economies. I think that if the authors thesis holds true and p indeed != np, this kind of conclusion could spell an even bigger problem for those who advocate to agument or replace market economies with another, typically more centralized, form of economic calculation. Allende's cybersyn famously used linear programming (P) in order to centrally 'simulate' and improve upon more regular market mechanics. If the authors thesis holds I think it's actually an argument in favor of the economic calculation problem talking point of Hayek and the like: efficient calculation of economic distribution problems is impossible and flawed dynamics of the market are probably close to the best approximation we can afford.

Iv 8y ago
When I tried to read about Allende's cybersyn all I could find are a few retro-futuristic furniture, but no meat whatsoever about the kind of software that was behind. It looked like pure PR to me. Do you have good sources about it? It has always intrigued me. Personally I think it is very unlikely that the markets are close to the best approximation we can afford. The current market-making agents use limited intelligence on limited data. It is an efficient system in the sense that it beats randomness and it beats a central (human) intelligence with (allegedly) superior access to information.
- baursak 8y ago
  I'm interested in this. So far, the best resources I found are: - "Red Plenty" by Francis Spufford, a mix of fiction and non-fiction about planning experience in the USSR. It includes a rich bibliography and references to papers published over the past 70 years around this issue. - There are few papers by Chinese economists, most notably this one: https://boingboing.net/2017/09/14/platform-socialism.html https://boingboing.net/2017/09/14/platform-socialism.html (you have to mess around with Sci-Hub mirrors to get a free copy). - There are few papers and books by Michael Ellman, e.g.: https://www.amazon.com/Planning-Problems-USSR-Contribution-Mathematical/dp/0521202493/ref https://www.amazon.com/Planning-Problems-USSR-Contribution-M... - I also have a few primers on linear programming in my to-do list, e.g.: https://www.amazon.com/gp/product/0486654915/ https://www.amazon.com/gp/product/0486654915/ - Somewhat tangential, but "the greatest American capitalist" ripping into EMH is a fun read too: https://www8.gsb.columbia.edu/articles/columbia-business/superinvestors https://www8.gsb.columbia.edu/articles/columbia-business/sup... None of these really talk about the software still, but I would imagine a combination of: - existing supply-chain systems already in place at Amazon, Walmart, etc., - something along the lines of non-monetary Kickstarter to gauge popularity of ideas from the ground up, and encourage innovation - strong democratic institutions - still allow free market at low levels, like individual entrepreneurs that don't employ anybody (once you employ someone, it must be a co-op). Dunno, these are just random ideas in my head. :)

babypistol 8y ago

I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me. But in the article, there is an interesting section on that: > If P = NP, even with a high exponent on the polynomial, that means that checking strategies from the past becomes only polynomially harder as time passes and data is aggregated. But so long as the combined computational power of financial market participants continues to grow exponentially, either through population growth or technological advances, then there will always come a time when all past strategies can be quickly backtested by the then-prevailing amount of computational power. In short, so long as P = NP, the markets will ultimately be efficient, regardless of how high the exponent on the polynomial is; the only question is when, and the answer depends on the available computational power. So this section, if I understand it correctly, says that problems in P are easy because the computational power in the world grows exponentially and we can assume that they will at least once become feasible to solve. That's an interesting way of looking at it. Is this really the reason why we consider polynomial problems much easier than NP-hard ones?

leereeves 8y ago
That's assuming computational resources could grow forever without limit, which of course they can't.
- QML 8y ago
  To add on: Moore's law is "dying", and that places further pressure on algorithms to get faster. However, even in an exponential world, I am reminded of a quote: "exponential algorithms make polynomially slow progress, while polynomial algorithms advance exponentially fast".
- babypistol 8y ago
  Yeah, in this case we are back to square one and P vs NP again seems irrelevant to me.

yeslibertarian 8y ago

Government is obviously much more efficient than the market. Venezuela, Cuba and North Corea are a good testament of that.

em70 8y ago

This paper is rubbish. Trading is ultimately a partial information, sequential game with an unknown number of participants whose payoff functions (and utilities) are also unknown. Could the market be closer to being efficient if P=NP? Likely. Does P=NP imply efficiency? Not at all.

naasking 8y ago
You seem to be missing the point. Markets were and possibly still are widely considered weak-form efficient. This is a disproof of that conjecture by showing an inherent contradiction between widely believed properties, ie. P!=NP and markets are weak-form efficient, therefore at least one of them is false. Edit: "Does P=NP imply efficiency? Not at all." This isn't even a claim of the paper. The paper is claiming the opposite, that market efficiency is true only if P=NP.
danbruc 8y ago
Is it even theoretically possible to show that markets are efficient on purely theoretical grounds? As a thought experiment, imagine that all human brains have a weird defect that causes them to always ignore some specific kind of information when making pricing decisions, including when they write software dealing with those decisions, and under all other conceivable circumstances. In that case, it seems to me, it would be impossible to decide on purely theoretical grounds that markets are efficient because it strictly depends on the empirical observation that human brains have this weird defect. I could imagine the other way around to work, i.e. that there could be an obstruction to markets being efficient that can be shown to exist on purely theoretical grounds. But no matter what the answer to the second question is, in no case could you arrive at an »if and only if« result without including the empirical observation that brains do not have this weird defect.
epr 8y ago
The entire premise of this paper is complete nonsense, and serves only to demonstrate the authors complete lack of understanding when it comes to the subject of markets. "Trading is ultimately a partial information, sequential game with an unknown number of participants whose payoff functions (and utilities) are also unknown." Markets in general are essentially an infinitely-armed bandit problem where everyone plays whether they know it or not, and resources are allocated over time in a manner not unlike evolution.

TekMol 8y ago

As I understand it, his argument is that there might be information available that needs time to interpret. And that the time the market took to interpret the available data is not sufficient to gain the maximum insight possible. So that somebody with more computing power then the market could beat the market. I don't see that as an argument against the EMH. I think it is inherent in the EMH that the market has more computing power then any individual. I would say that it is the core of the EMH. That more people make better predictions. Because they have more computing power. I always found it strange that the EMH is often defined as the market price including all available data. As if the data can simply be added without interpretation.

inputcoffee 8y ago

The author’s claim only applies to weak form of market efficiency. The original Fama paper distinguishes between three forms of the EMH: weak, semi strong and strong. The weak form only alleges that historical price info is fully incorporated in the current price. You can still make money by working hard and figuring things out from outside the price history. The weak form applies to purely technical trading that extracts value from price history like momentum and the simple moving averages cross over studies you see.

Symmetry 8y ago

I don't think anybody would claim that even the weak form of the EMH applies in all cases. Like the idea that objects of different weights fall at the same speed it's an approximation that can be very close to true in some cases but can be badly misleading in others. If you've ever listened to economists talk about prediction markets they always seem to bring up the idea that markets with low capitalization have low efficiency. And even looking at the highly capitalized stock market I know at least one story of a major player that got its start noticing a violation of weak-form efficiency and becoming very rich by fixing the violation. There's no reason to think that actual markets are now finally efficient and in fact there are some that are publicly know, but which only bring a small return and require decades of investment to fix so nobody is interested in trying.

adament 8y ago

First of all this paper leaves a lot to be desired in terms of rigor and it is for good reason not how mathematics is written by most mathematicians. It is very conversational and assumptions and derivations are jumbled together, while you sometimes find these in breakthrough papers from visionary mathematicians it often makes it harder to verify. My understanding of the central argument in the paper is the following: Definition: Let N be a positive integer denoting the length of the history, M be a positive integer denoting the number of assets. A market realization is an element of {-1, 1}^(NxM), i.e. M vectors of length n where all entries are either +1 or -1. Definition: We call a function f: {-1, 1}^(TxM) -> {0, 1}^M satisfying f \circ s = s \circ f for s any element in the symmetric group S_M a technical strategy of lookback T. The symmetric group condition just states that permuting the vectors of length T among the M assets is the same as permuting the output the strategy. I.e. that the strategy has no inherent preferences among the assets. The payoff of a technical strategy s on a market realization h is given by payoff(s, h) = \sum_{i=T}^N s(h_{i-T, ..., i-1}) \cdot h_i where the indexation is in the time dimension i.e. h_i denotes a length M vector. The budget of a technical strategy is budget(s) = max_{v \in {-1, 1}^TxM} s(v) \cdot (1, ..., 1). That is the maximal number of assets it wants to hold in any given state of the world. Given a market realization h, positive integers B and K we say that h is (B, K) EMH-inconsistent if there exists a technical strategy s such that budget(s) <= B and payoff(s, h) >= K. If a market realization h is not (B, K) EMH-inconsistent we call it (B, K) EMH-consistent. Claim (presented as a theorem in the paper): The problem of determining whether a market realization is (B, K) EMH-consistent is in P if and only if the knapsack problem is in P. Claim: The weak efficient market hypothesis is true if and only if EMH-consistency is in P. In the second part of the paper he indicates a model of an order book where he wants to encode 3-SAT as combinations of market orders. I do not understand how this is intended to work, i.e. if all information is available and incorporated into the market and the information generating process is stopped, and I have bid-offer spreads because of transaction costs, and I irrationally (remember I am not interested in the buying or selling the security, I am just interested in solving a 3-SAT problem, thus my actions should not influence the price generation process of an efficient market) enter an OCO-3 order to buy A, B or C at mid. Why should this result in a transaction? In the case (a or a or a) and (!a or !a or !a) I make one trade with myself in the case (a or a or a) and (b or b or b) and (!a or b or b) I make one trade with myself, but one of the problems is satisfiable the other is not. Now it seems obvious that by inventing new order types we can get order book rules that allow for complex computation to resolve clearing, however this is a problem with the proposed order types not the efficient market hypothesis? A (to me) equivalent avenue of investigation would be to imagine different order types such that to decide the clearing of an order book it would involve solving an undecidable problem - i.e. what are the most reasonable order types and order book rules such that we can encode the halting problem?

splitrocket 8y ago

Profit is the measure of inefficiency in a market.

jkingsbery 8y ago

> "But given that there are 3n patterns to test, finding a solution, as opposed to verifying one, requires O(3^n), i.e. it is exponential in the size of n. For small n, this is computable, even though it is exponential. But as n grows, it becomes impossible to check every possible pattern quickly." If a strategy is a sequence of BUY-HOLD-SELL decisions, then just because there's O(3^n) strategies doesn't mean you need to evaluate them all. It seems pretty easy (if a strategy is only defined in retrospect) to define a greedy algorithm that finds the optimal strategy. (see page 16.) The author goes on to compare this to the Knapsack problem (pg 19). The thing that makes the Knapsack question (and NP-complete problems generally) hard is that greedy algorithms don't work (as far as we know), whereas it seems like a greedy algorithm work for the problem the author has laid out.

lynal 8y ago

Based on a quick skim, this is not a good paper. Computer scientists writing on economics is great, it's helpful to grow new ideas in the field. Unfortunately they sometimes use economic concepts imprecisely at detriment to their question, methodology, and results. That's the case here. This paper posits a definition of efficiency, but does not explain why that definition is correct or how it relates to other efficiency measures. A better proof of arbitrage opportunities in markets is Wah 2016, which identifies actual arbitrage opportunities in actual markets. Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement? And what is the correct way to concisely and precisely write: "most people familiar with the P = NP problem believe with varying degrees of confidence that P is not equal to NP, but so far no proof exists."

myWindoonn 8y ago
Whether P and NP are equal is an arithmetic statement; it's either true or not true, but we may not have the proof systems required to demonstrate it. Your excerpted sentence is already quite concise compared to serious surveys like https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf
openasocket 8y ago
> Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement? It actually does have a formal meaning! This is one of the most interesting results (in my opinion) on the P vs NP problem. Given a random oracle R, Pr(P^R != NP^R) = 1. So given a random universe, it is almost certainly true that your version of P != your version of NP. At least that's how my theory prof liked to explain it. Here's a link with the proof: http://theory.stanford.edu/~trevisan/cs254-14/lecture04.pdf http://theory.stanford.edu/~trevisan/cs254-14/lecture04.pdf

tomtimtall 8y ago

Reading this comment thread is hilarious to a degree. I think that it really highlights how much noise gets thrown into a discussion when your naming becomes too relatable. Essentially bike shedding of theory discussion. If the Efficient Market Hypothesis has been called the “Fundamental Market Property Hypothesis M = H” or similar I doubt most would have made the comments they made. But because “efficient market” sounds to relatable most feel that they can comment without even knowing what the specifics of the EMH are.

carapace 8y ago

Er, markets are massively parallel, yes? Um, am I wrong in thinking that P and NP refer to non-parallel algorithms? (Apologies in advance if I'm having a brain fart.)