That's why we need peer-review.
Markets are efficient if and only if P = NP (2010)
51–60 of 201 posts
Re: Markets are efficient if and only if P = NP (2010)
#52"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.
Re: Markets are efficient if and only if P = NP (2010)
#53Earlier quoted context omitted.
On 1: That's exactly the point of this paper. That's what the EMH claims, and what this paper is linking to P=NP. If this paper is correct then markets are not violations of P=NP, and a lot of economists are wrong (or P=NP). On 2: My answer to both problems (any problems) is Turing equivalence. If one algorithm of people and computers can solve the problem, then so can another one with the same resources. And given o…
Equal number of people doesn't not solve the principle agent problem. The idea of the principle agent problem is that the best person who is able to understand their own wants and desires is the person themselves. Markets are currently the way that puts the maximum amount of control into each individuals own hands. IE, a person has X resources, and they can trade them how they like because they are best able to under…
> The idea of the principle agent problem is that the best person who is able to understand their own wants and desires is the person themselves.
I don't see how markets are supposed to solve that when we allow countries with slaves to participate on the markets. Or landlords to exercise economic rent over the land that other people maintain and live on. I guess my point here is I'm not sure markets as we have them today solve that problem very well anyway.
> Equal number of people doesn't not solve the principle agent problem.
But it does. If your claim is that every person is an economic agent representing themselves on markets (which isn't true for many people, but sure let's go with it), then any equivalent system would have to factor in the amount of work they provide to the algorithms that are markets and provide an equivalent (alternatives might include surveys, bizarre computer generated questions, kickstarter style projects but with government/basic income style funds). That's fine, it's still an interesting direction of research, which would be necessary to understand the computational structure of economies.
The alternative claim, is that markets some how create a system that is greater than the sum of computers and people it encompasses... this paper deals with that by placing it squarely in the realm of NP completeness.
Re: Markets are efficient if and only if P = NP (2010)
#54Earlier quoted context omitted.
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 wit…
Sure, but significant facts come out of it: * Economic systems are optimization algorithms on an NP hard problem. Hence markets have no special efficiency capabilities, they are simply a choice of optimization algorithm, there may be better ones out there with more favorable properties. Any optimization algorithm with similar resources could have effectively equivalent efficiency. This destroys the economic calculati…
The concept of NP-complete is different form the concept of np-hard to approximate in any way. The question if a particular problem is hard to approximate is typically a diverse and interesting research area, that does not have obvious answers.
For example, it has been proven that the well-known traveling salesperson problem on metric instances (i.e., instances satisfying the triangle inequality) can not be approximated within around 1.008 unless P=NP, and there is an approximation algorithm that has factor 1.5.
I have not read the above pre-print, but from a cursory glance it does not discuss theoretical approximation hardness at all. It does have a section on approximations, but it is hand-wavy and fluffy and uses a colloquial/non-strict meaning for approximation.
Re: Markets are efficient if and only if P = NP (2010)
#55Earlier quoted context omitted.
Sure, but significant facts come out of it: * Economic systems are optimization algorithms on an NP hard problem. Hence markets have no special efficiency capabilities, they are simply a choice of optimization algorithm, there may be better ones out there with more favorable properties. Any optimization algorithm with similar resources could have effectively equivalent efficiency. This destroys the economic calculati…
The concept of NP-complete is different form the concept of np-hard to approximate in any way. The question if a particular problem is hard to approximate is typically a diverse and interesting research area, that does not have obvious answers. For example, it has been proven that the well-known traveling salesperson problem on metric instances (i.e., instances satisfying the triangle inequality) can not be approxima…
[deleted]
Re: Markets are efficient if and only if P = NP (2010)
#56The title of this post scores 10000 HN points.
Re: Markets are efficient if and only if P = NP (2010)
#57Have 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
(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_pr...
--
EDIT: no mistake in my comment
Re: Markets are efficient if and only if P = NP (2010)
#58Meh. 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.
Re: Markets are efficient if and only if P = NP (2010)
#59While 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. Ma…
There is an impedance mismatch between the terminology in economics and CS. CS is at it's core a hard math discipline, and absolute statements are used a lot, and they differ quite a bit from what people outside of the field understand. This paper assumes a basic knowledge about CS theory and economic theory.
While you're right in your points here, the CS aspect of this paper leans on the CS theory. When a computer scientist say, "we cannot do this efficiently" it means, "We might be able to do this efficiently for some instances of the problem, but not for all instances". And when the scientist say "we can do this efficiently" it means "we know how to solve this in a way that when we double the input size, the difficulty will be a fixed factor larger. But it might be infeasible to solve any instance of the problem what so ever".
Re: Markets are efficient if and only if P = NP (2010)
#60While 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. Ma…
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…
I don’t think economists claim markets are efficient. There’s far too many examples to the contrary - see amazon, wellsfargo, and Verizon as examples. While those companies do technically have competition, they operate with significant market power.
Also, I once heard an Econ explain EH as “true if enough people operate under the assumption that it is not true”
Edit-After waking up a little more, I’m not entirely sure of my statement that amazon, wellsfargo, and Verizon serve as examples against EH. But the later quote I heard from someone with 30+ years of research.