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.)
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?
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.
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.
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.
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
"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."
Instead you have created a number that may or may not be prime but definitely requires a new prime number (not in your set) to factorise it. Counter example: Take your set of prime numbers to be {2,3,5,7,11,13} then
(2.3.5.7.11.13)+1 = 30031
30031 factorises into 59.509 so you have found two prime numbers that are not in your original set.
EDIT: Responding to the edit above. The problem is that you claim that you make a new prime number by multiplying them all together and adding one. You didn't multiply all the numbers and added one to get the prime number, you multiplied all the numbers and added one to get a number (POSSIBLY NOT PRIME) whose FACTORS are prime numbers not in your original 'supposed' finite set. Your proof essentially lacks the step: IF new_number is prime: proof finished ELSE: factor new_number and show that at least one of the factors is not in your finite set.
EDIT 2: Counterexample number 2. Suppose your finite set of primes is {2,7} (2.7)+1 = 15 So you have found 3 and 5 as primes that are not in your original set and are SMALLER than the largest prime in your original set. This is now a second mistake in your proof. Whether you are trolling or just too arrogant to see the mistake/error I do not know.
Edit: I've thought about this a bit more, and you can save the parent post by prepending a result like "Every number larger than one is either prime, or divisible by a prime smaller than itself". In this case you can then assert that your constructed number is prime. However, this result requires its own proof and was not mentioned by the parent post.
It is possible that the OP did not make the mistake that you are attributing to them, although best case is that the exposition was simply unclear.
This little mental exercise proves that 2 and 7 can't be the only primes in existence. It doesn't really matter what 15 really is or isn't. No need to add noise about it. We only care about the supposition, which you cut out of your quote.
Hope this explains why I didn't deal with the true status of new_number! It just doesn't matter.
However, I'm disappointed in you, in the other respondent, and in the moderation here, and I'm glad I made this alternate account.
But it seems to me that even in the example from your note the stock price will tend to reflect the the correct price. As you realease new information the factorization becomes more feasible and once it's feasible enough the stock price will get the correct value. Maybe we should amend EMH to say that asset prices fully reflect all the facts that are feasible to compute from the available information.
Anyway, the reason I'm writing this comment is to say that you should no be so sure of your proofs, especially because your proof of the infinitude of primes is wrong. This proof does not show that the new number (the product of primes + 1) is prime. It shows that none of the primes are factors in this new number and from that it follows that there must be more primes, but it does not follow that the new number is necessarily prime (it might be a product of another unknown primer and the others).
For the prime proof, the new number is prime as long as as it has no prime factors < itself, which we assumed at the start. This guarantees it's prime under our assumption and this falsifies the assumption. Doesn't matter if it's really prime.
I think if we were to approach the EMH from a constructive or computability approach, we'd have to make that definition much crisper. That is, the feasibility of computing the factorization based on limited information determines whether the information is actually "available" in the sense of the EMH.
In the real world we can see things like drug trials that will determine the success of a pharmaceutical company. The information that the drug works or doesn't work, or has side effects, would be "apparent" to a hypothetical "ideal" expert in human biochemistry -- so simply knowing the chemical formula for a new drug, the information about its working is "available" in that sense.
I like your drug trial example but a "hypothetical ideal expert" isn't assured to exist. Do you have an existence proof?
On the other hand, unique prime factorization is assured, we know that given infinite time anyone can factor any large number.
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.
You know, just how people used to tell homosexuals to not be gay when other people thought they were freaks because of it.
Weak and strong are just about which data is incorporated. Neither one addresses the fact that no entity interacting with a market is infallible.
I would argue that until the search space was reduced to the point where it would be feasible to factor the secret before another digit is revealed, the information is not "available" in any useful sense. So maybe, in some sense, this helps us narrow down a definition of what "available" means, but since real-world price signals are rarely something that is deterministically computable, I'm not sure that this would help to clarify the EMH.
In my drug trial example, such an expert does not exist, but if we're dealing with mundane real-world stuff, then the assurances that the proposed $1B gift to a random company would actually go through would have to be factored into any strategy -- why would I bother committing computing resources to factoring the number when in all likelihood the billion dollars would not handed over because why would anyone actually do that?
For the drug trial example, again, I like it but perhaps such an expert is theoretically excluded? Your statement might be like saying "suppose there's a hypothetical O(n) halting algorithm that answers the halting problem in constant time for the length of the program it's testing." That's nice but there's a proof that what you've just hypothesized is impossible[1].
I am not exactly saying that an ideal expert in human biochemistry who can predict the results of drug trials is impossible, but how do we know it's possible? I mean, is chemistry guaranteed to be fully computable or something?
For your last point, I think that what I asked to assume (that the $1B transfer is credible, that the computer is secure) are nowhere near the size of assumption of something like "assume there exists someone who can predict biochemical reactions in humans without testing." Basically the legal instruments and secure computers I included are easy, solved problems that I ask the reader to assume are being implemented following best practices.
But that's not how I argued. Instead I showed that 15 is the new prime because it's relatively prime to all the primes. (By the assumption we had started from all the primes.) And this is what falsifies the assumption.
I think my argument is fine and I don't need to address whether 15 is really a prime.
"Any number that is relatively prime to all other primes is itself a prime"
You would need to first state and prove this in order for your original post to constitute a rigorous proof.
Do you mean that the number you've produced is prime? Or do you mean that "the number you have computed is either prime or has a prime factors not in your list of primes, therefore, by computing the factorization of that number, you produce a new prime"?
The former statement is demonstrably false, the latter statement is true. Others have read your proof as stating the former, and I argue that the latter is a generous but not unreasonable interpretation of your phrasing.
Remember that we are arguing from the false assumption that you start with the finite set of all primes, up to some largest prime, L. Call this false assumption A. It's fine to make false statements that follow from A, no problem at all. Indeed this is the point.
One definition of a prime is that there are no primes smaller than it in its prime factorization. We'll call this definition NSPIPF - no smaller prime in prime factorization. Is NSPIPF an OK test for primality? Sure.
So when you get to new_number, produce the prime factorization. Does it meet the definition of NSPIPF? Yes, because we made it relatively prime to every prime (under assumption A).
It passes primality test NSPIPF. Under A. And therefore is prime. Under A. (This is the part you and others object to, but it's absolutely flawless application of the NSPIPF primality test.) It doesn't matter that in some other way I could also get to a contradiction. For now this is what we do.
Under A, using NSPIPF primality test, we just proved new_number is prime.
Next we show that this new_number definitely wasn't in the set of all primes, since it's larger than L, having had L and a bunch of other positive integers as factors and then one added to that for good measure. It is at this point that we show explicitly that A cannot be true, because we used A to produce a prime that wasn't in the set of all primes.
It doesn't matter if that was a false statement!
I think all this is in my original comment and it is a flawless proof by contradiction. I asked you to "Suppose there are just finite primes, up to some largest" and you gave up when you started seeing false statements, rather than at the end of the paragraph where I presented the conclusion in black and white.
Or it just says: You're posting too fast. Please slow down. Thanks.
That you're conventional enough to never stand out of the herd says more about you than anything else.
Here you've introduced a definition of prime that is different than the usual one, and is in fact self-recursive. NSPIPF is "no smaller prime in prime factorization". What is the first "prime" in this definition? Is it a number such that there is "no smaller prime in prime factorization"? What is the second "prime" in that definition? Is that the usual "prime factorization", or is it an NSPIPF factorization? In other words, how would you prove that 2 is prime given the NSPIPF definition?
It is more natural to talk about primality as a test that can be done independent of any assumptions about other primes, but rather as a matter of whether it can be expressed as the multiple of some number other than 1 and itself. That way we can make a precise statement about the product of the finite set of primes plus one without reference to the set of primes.
This is clearly not what I was doing. I clearly referred to having no smaller prime factors. Anyway this aside is tiresome, it's like poking me for saying "every positive integer has a prime factorization" and then asking, okay, so what about 1 or something. I think my proof is fine and I'm not going to defend it anymore.
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.
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.
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.
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.
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".
https://content.iospress.com/articles/algorithmic-finance/af...
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. :-)
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) [2] https://en.wikipedia.org/wiki/FNP_(complexity)
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.
> 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.
That's just what P = NP means: the cost to verify a solution is the same as the cost of finding one.
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?
> 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.
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.
How so? It implies simply that markets are not efficient. It does not imply that state control would be more efficient and it does not imply that markets are not the most efficient way of determining the value of a resource.
What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods and fix prices based on that determination.
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 [1] https://en.wikipedia.org/wiki/Principal%E2%80%93agent_proble...
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.
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.
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."
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
Your excerpted sentence is already quite concise compared to serious surveys like https://www.scottaaronson.com/papers/pnp.pdf
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.
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?
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.
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.
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.
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. "
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.
Computational complexity and markets have more in common that most think. Mechanisms which rely on algorithms, such on auctions, have runtimes.
Hence, why we have a field called algorithmic game theory [1].
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.
The project was very short-lived, but (IIRC) the primary designer was Stafford Beer (https://en.wikipedia.org/wiki/Stafford_Beer) who based the work on his so-called Viable System Model (https://en.wikipedia.org/wiki/Viable_system_model). For the fundamental theories of the time you'd want to read Beer's works as well as those of his contemporaries, who espoused competing theories and methodologies. (I say "at the time" but the state of the art never really changed. Project Cybersyn is a fascinating chapter in the long-history of AI, and if there's any dominate thread to AI it's one of diminishing expectations and migration to ever more circumscribed problem domains.)
As I mention in my Amazon review the author, Eden Medina, seems to have compiled a ridiculous amount of material but only a fraction of it bleeds through into her book. The book is fascinating but if you're interested in the theory and history more generally then the book's bibliography is priceless.
It's been awhile since I read the book but here's one lasting impression: one of the biggest problems with Project Cybersyn was communication between producers and consumers. Much of the budget and time was actually spent on telecommunications infrastructure and then figuring out how to get people to use it properly. Which hints at one of the most important functions of a market: price signaling. Regardless of whether a market is efficient, given the dynamic nature of a complex economy any system you setup that tries to centralize price signaling (capturing pricing information is a prerequisite for processing it and generating optimal allocations) seems like it'd very quickly become antiquated and a hindrance. Markets may be inefficient but at scale not only are they remarkably powerful distributed computation engines, they co-evolve with the economy. But that doesn't mean there isn't room for applying these techniques in sub-domains (e.g. trading engines, city governance, etc), improving overall efficiency.
- "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 (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-M...
- I also have a few primers on linear programming in my to-do list, e.g.: 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/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. :)
Frankly, everybody with a bit of economic common sense knows
Citation? True Scotsman fallacy?
I am pretty sure that most economic Nobel prize winners do not believe in EMH, from the top of my head, Akerlof and Kahneman.
Isn't it also ironic that you criticize the book as being pop-sci by perusing Wikipedia? You know, in both cases, being pop-sci doesn't imply being wrong.
It's not even binary and is not a static property, just like our laws are just a proxy to a question of what is ethical or moral; and the truth of their purpose is entirely based on the historical context.
Note that I said "people invest in markets", and not index funds above. There is a subtle differences, modern index funds are not true market indexes. There are fund managers who trade actively - however they trade mush less often than a traditional actively managed funds and with different rules. The managers do watch earnings reports and sell bad stocks, but the managers are also in for the long term and re willing to wait out a downturn. The managers also know they are judged by the index, and so bad stocks are not a negative in the same way that active funds are judged. Thus an index fund trades much less often, but they are not really a buy the index as published.
I would argue that belief in EMH is supported by existence of index funds. But index funds are also supported by laws that require certain level of openness and information sharing (such as laws against insider trading). When this information sharing is not enforced by law, it is a major source of market inefficiencies.
> The basic argument is as follows. For simplicity but without loss of generality, assume there are n past price changes, each of which is either UP (1) or DOWN (0). How many possible trading strategies are there? Suppose we allow a strategy to either be long, short, or neutral to the market. Then the list of all possible strategies includes the strategy which would have been always neutral, the ones that would have been always neutral but for the last day when it would have been either long or short, and so on. In other words, there are three possibilities for each of the n past price changes; there are 3n possible strategies.
There are 2^n possible histories of length n. If a strategy maps each history to one of three positions, there are 3^(2^n) strategies that consider n bits of history.
"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.
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.
The importance of the difference between P and NP appears to be much greater in domains that are starkly discrete, such as cryptography, than in those that are approximately continuous, like finance, where there are often approximate methods in P that are very effective and efficient, at least for most real-world cases.
[1] Only in the last section does the author look at all at real market data, and there only to look for evidence in support of a weak prediction from the thesis. This is so riddled with uncontrolled factors that it tells us nothing about the quantitative consequences of N != NP on market efficiency.
We give importance to this question because it is open, it is big, it relates to many other parts of computer science, it has real-world implications, etc. The fact that you don't think this question is important likely means that you don't have the complexity-theoretic background required to appreciate the stark deepness of the question. This isn't bad, but it's myopic.
The fact that the exponents tend to be small in the algorithms that our puny brains were able to produce does not convince me one bit that all problems in P have algorithms with small exponents.
Why are you so sure that P vs NP is important? Does it really relate to so many parts of computer science?
I do agree that complexity analysis is a very (perhaps the most) important part of CS. But that does not necessarily mean that P vs NP is a fundamental question.
RSA wouldn't break even if P = NP. Even if we came up with a polynomial algorithm for integer factorisation in could have a much higher exponent than the multiplication required to verify the result.
This is what bothers me the most, people saying that P = NP implies that solving a problem is as difficult as verifying a solution. That's simply not true: P = NP implies that solving a problem is as difficult as verifying a solution (modulo polynomial reductions).
The part about ignoring polynomial reductions seems very important to me. Otherwise I could also say that: "all even numbers are the same", when I actually mean: "all even numbers are the same (modulo 2)".
Would you care to convince me why we chose to ignore polynomial reductions and not some other complexity class?
The best explanation I see is the fact that different Turing machine formulations (single-tape, multi-tape, one-way infinite, two-way infinite, ...) and also the random access machines have polynomial reductions between them. But even this does not justify the importance we give to P vs NP in my eyes.
However, even in an exponential world, I am reminded of a quote:
"exponential algorithms make polynomially slow progress, while polynomial algorithms advance exponentially fast".
So, not only do you have the resource problem highlighted in sibling posts but also a recursion problem:
Vis, when the problem becomes solvable the optimisation must add the market transactions for the sale of resources to solve the optimisation, so now one needs to optimise that larger problem ... which again involves transactions, which shift the original optimisation.
If you can predict the optimisational perturbations needed to solve the enlarged system, then you might be able to break the cycle .. but won't you need to transact the processing of the perturbation, the optimisations of which will shift the inner optimisation.
The solution itself would be marketable, perturbing the market and negating the optimisation?
My instinct may be wrong but it suggests the market can't be [perfectly] optimised (but in practise that probably doesn't matter).
Optimising markets might be the extent goal of capitalism, but it's not the extent goal of the rich (in general) who would rather remain rich than have perfect allocation of resources.
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.
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.
We consider a 2-layer, 3-node, n-input neural network whose nodes compute linear threshold functions of their inputs. We show that it is NP-complete to decide whether there exist weights and thresholds for the three nodes of this network so that it will produce output consistent with a given set of training examples.
https://papers.nips.cc/paper/125-training-a-3-node-neural-ne...
I get the reasoning why people aren't sure if P = NP.
Here is another question.
What defines time? And what about a solution?
Consider the fact that in the theory of general relativity we have the twin paradox.
What if I sent a computer on a rocket at close to the speed of light and then on earth I had the same machine running the calculation that takes a million years, and then when the other computer gets back from it's interstellar vacation, I just have the computer ask the other what it's part of the solution is.
According to the computer that flew away the amount of time that it takes to solve the problem can be considered ~P in a way.
My intuition is telling me that this is probably the wrong way to think about time complexity though.
> 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
No it's not. You can't do reasoning on bullshit inaccurate analogies.
Without knowing too much about neural networks myself:
Theory stuff:
P, NP, NP-hard and NP-complete only refer to classes of complexity (of algorithms), i.e. you can "categorize" decision problems this way (by currently known solutions or mathematical proofs of lower and upper boundaries for complexity).
P contains any problem for which there is an algorithm that can decide it on a deterministic turing machine (read: abstract definition for a computer) in an amount of time that is growing polynomially with the size (n) of its input.
Example: Checking if a list contains a specific item can be achieved in O(n) time - just iterate through the list. Searching in a pre-sorted list (binary search) can be achieved in O(log(n)) time. This means that if your list is longer by a large factor, both algorithms will take accordingly more time, which means that the amount of computation necessary for the sorted case will grow much less than the generic case. Both problems are within P, though.
NP contains all problems that can be solved by a nondeterministic turing machine in polynomial time. If you think of your problem as an automaton with states, this machine could deal with ambiguous state transitions in an efficient manner, "magically" only picking those options that succeed. This is basically the promise of a quantum computer. P is thus a subset of NP, since the nondeterministic touring machine can do anything a deterministic one could do too.
You can still solve those problems on a normal computer, but not in polynomial time (unless P=NP, which is neither officially proven nor disproven until now).
Then there is the idea that you can solve problems using solutions for other problems merely by transforming the input in polynomial time.
NP hard problems are those which you could use to solve any other problem within NP this way. Those don't necessarily have to be in NP - their complexity could be even worse. There is an intersection with NP, though: Problems within NP that you can use to solve all other problems in NP. Those are called NP complete.
If you would now find a way to transform the input for an NP complete problem into one for any P problem in the same way (remember: in polynomial time for a DTM), then you would have effectively proven that P=NP.
On the NN comment:
I've always understood AI in general and especially trained algorithms to be heuristics. If you talk about P and NP, you're talking about mathematically proven solutions, so the comparison doesn't work out in the strict sense. On the same note, NNs are often used to solve problems that don't have strictly "correct" solutions. If your problem is "does image X depict a goat?", you won't get far with traditional means. A NN, on the other hand, trades accuracy (false positives and false negatives will happen) and up-front work (training with a dataset not provided by the actual problem instance) for speed.
It is related to the discussion though, since a generic trainig algorithm for neural networks actually will have a non-polynomial complexity as far as I understand (at least Google tells me so ;-) ). Note however that training a NN is also not a decision problem: The result is not true or false, but the resulting network.
Edit: Replaced a reference to sorting with searching for an item, since sorting is not a decision problem.
Aren't all proofs flawed in this way?
Like for example, 2 = fish. Prove that there isn't an undiscovered mathematical axiom that makes this not nonsense?
Let's take an example: China. While they keep the image of a purely capitalist environment, every company above a certain size is expected to have some sort of government control. That would be the inefficiency of that market, because at that point people stop making decisions based on what the company wants but rather what government wants. You can't have open access to the strategic planning by the government.
Besides, you're clearly trying to argue definitions rather than trying to take a step back and realising that I am arguing abstracts rather than specifics in the first place. In other words - what you're saying isn't denying what I said; it's just embodying the concepts in the real world.
For example: _any_ true real-life index fund would always need to trade at a certain point, and that has to be done by someone. So yes - an index fund is just a "glorified" version of a private fund; because people are still managing it at a certain point. But the reason it still makes money is because markets are efficient.
And asymptotically is not the right word either, because n^3 is asymptotically different from n^2. You probably meant poly-time reducible, whichs is quite different from "the same".
An example would be the Halting-Oracle, which can tell you if a program will halt or not without running it. (Of course, this oracle doesn't actually work since your program can have the oracle's output as input and simply do the opposite)
A NP/P Oracle might be an oracle that can tell you if a more efficient algorithm for your problem exists.
Such oracles can be setup to prove certain assumptions (or disprove) based on simply logical statements (see halting problem oracle above).
Oracle machines are also not really turing machines, it's usually assumed they can do the oracling in a single operation and they're usually a black magic box (there is no need to explain how they work, they're an abstract concept).
No it implies that efficient market states are an NP complete problem. And that we are likely approximating the optimization of efficiency (of the allocation of resources) using markets. Different approximation algorithms have different properties. Might markets be the best in every possible way, sure, but it's very unlikely given what we know about approximation algorithms. It's like one of the best variants in one way, perhaps that's the best way, but we should figure that sort of thing out. And that's what this paper is laying the ground work for.
> What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods and fix prices based on that determination.
In it's editorializing about markets. Which isn't incorrect. But the larger consequences of efficiency being an NP complete problem means that there are many possible algorithms we could use to solve them if they are given equivalent resources. If those equivalent resources are thousands (or millions) of government panels then we should be able to mathematically prove equivalency. That's my point.
There is a method of solving an NP complete problem with thousands (or millions) of government panels?
Your question is not related to my point. And you'd have to at least answer it for markets first before I would bother to try. My point is that it is an interesting area of research, we should answer both questions and their interrelationships.
The time a turing machine takes to solve the problem can be considered local and in absense of general relativity, it doesn't matter much.
When you talk about time in NP/P, you usually talk about the O Notation (Big O and friends) which gives you the driving factor of the time needed to solve.
Ie, O(n) = 2 + 3x + 9x^2 + 9^x is n^x complexity because this part of the equation will grow much quicker than the others. In reality of course, it can take a while for the biggest part to overtake which is why searching an array linearly in CPU cache can be faster than a hashmap.
The solution in NP/P is usually reduced to either a predicate being proven true or the answer being boolean or can be reduced to either. (ie, solving a jig-saw puzzle can be reduced to "is this jig-saw puzzle solvable" which can be proven by presenting a solution)
The problem you present is not in the scope of NP/P. You're already involving multiple computers and generally here, people still assume general relativity doesn't exist. Plus NP still holds because one computer simply accessed a blackbox function (oracle) while the other solved it in NP.
Time-complexity isn't the only complexity either, you also have space-complexity.
SC tells you how much memory you need to solve a problem. Or rather, how quickly that memory need will grow. You can trade a lot of NP problems to P problems if you have "NP" space complexity.
SC complexity won't spit out a byte-accurate estimation of memory but it can tell you that O(n) = 100 + 100*x will grow linearly in size (O = x) and O(n) = 100 + x^2 will grow exponentially in memory usage (O = x^2).
No, since it can only save a constant factor of time. (Also, dragging random physics into a mathematical model based on a different view of the world isn't really helpful to understanding it. "Time" is computational steps, not seconds)
But many markets (the labor market, the health care market, etc) work in such a way that it's ridiculous to assume that most participants know all public and private information all or most of the time.
Also what people mean when they say markets are efficient in other contexts means something very different. The EMH specifically describes how quickly and what kinds of information get incorporated into asset prices. It doesn't make claims about how markets organize production or optimize utility without centralized direction, which is usually what people mean when they say free markets are efficient.
I think a lot of confusion has arisen from the very general-sounding name of the hypothesis which does not reflect its relatively narrow claims. Not that I buy the EMH (no pun intended), but that's a different story.
Another requirement is that entrepreneurs have fair market access to capital. This assumption is true in many developed countries, but not in many developing countries where you need connections to obtain a loan. But even in developed countries, it's difficult to get extremely large loans on the merits of the financials alone, which explains why large infrastructure projects like highways, airports, and power-plants often don't get built solely by the private sector.
Also EMH, and that's the point Fama uses a lot to battle critics, does not put a time frame on when the price adjustment happens.
If you know markets are efficient, there is no reason to haggle about the price.
But haggling is the mechanism that enhances price efficiency.
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.
I gave you two Nobel prize recipients who actually wrote famous articles explicitly outlining market inefficiencies.
Regarding Steve Keen, I don't have my copy handy, but I am sure it has plenty of additional citations. While it is written in accessible style, it is certainly not unsupported. (I personally think that every student of economics should read him, but it's up to each individual what they want to do with their free time.) Many post-keynesians I have read expressed similar dismay about EMH.
> Debunking Economics exposes what many non-economists may have suspected and a minority of economists have long known: that economic theory is not only unpalatable, but also plain wrong.
Plainly alludes to the fact that the book is not mainstream economic theory. People arguing for minority views of complex subjects find — rightly — that the burden of proof is on them, and not the other way around.
Related: it’s not in the least bit surprising to see the book make an appeal to common sense over “those experts”. Truly we live in the age of Trump and Farage.
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 our knowledge of how different optimization algorithms can give results biased in different ways, it should be possible to find an algorithm that biases better towards equality than our current one.
But again that's a theoretical justification, which is why it's an interesting avenue of further research. I don't have any concrete answers because that would require research on the problem I haven't (and don't have the resources to) conduct(ed). And to make it quite clear, it's entirely possible the answer of this research could be markets are always the best (which would be disappointing, but possible), but it seems more likely that we would discover some new systems.
Edit: The economic calculation problem is the EMH rephrased (which this paper is making clear is a valid criticism only if P=NP). So that problem in specific is invalidated by this paper.
Edit 2: The principle agent problem is solved by the "equal number of people" component. And the fact that markets often involve selling other people's resources through their governments and other representatives anyway (see Saudi Arabia selling oil to enrich only their leaders on our open markets; while they use slaves), so it's not like markets are somehow a perfect solution to this problem as they currently stand.
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 understand what makes them better off.
If your solution is to take power away from an individual, with regards to how they spend their own resources, IE, by controlling their "means of production", you are going to run into the principle agent problem.
Also, with regards to the paper talking about P=NP is missing the entire point.
Sure, markets aren't 100% efficent. They could instead be 99.9999% efficent. And that's good enough and side steps the whole P=NP problem.
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.
"Our puny brains" have no problem constructing O(n^100) or similarly-ridiculous problems. Here is an informal survey [1] of several good examples. In my previous message, I indicated that matrix multiplication and CFG parsing are good examples; they are both cubic-time but we have come up with even cheaper algorithms for special cases, like sparse matrices or LR(k) grammars.
Whether P equals NP is not only a fundamental question, but it's the first of infinitely-many questions about the "polynomial hierarchy" or PH, a tower of ever-more-complex classes. And part of why the question is so important is that deciding whether P=NP is actually a problem in a higher rung of another complexity class further up in PH! P!=NP is like the first of an infinite family of very very difficult meta-proofs about complexity.
"RSA wouldn't break" because PRIMES is already known to be in P, via a famous paper titled "PRIMES is in P", and RSA keys are already sized to have impractical exponents.
What P=NP implies is much more powerful. First, let's consider the actual cost of a poly-time reduction. P is self-low, which means that P with a P oracle is equivalent to P. So if P=NP, then the cost of a poly-time reduction can be rolled in, and the entire problem is still in P.
Now, which problems would be transformable via P=NP? Well, we typically assume that the solution would include a poly-time reduction for 3SAT instances into some P-complete problem. Okay, great. However, we know that 3SAT can't be transformed opaquely; if this transformation exists, it must be able to examine and specialize the structure within each specific 3SAT instance. So we'd get one powerful theorem about logic (specifically, about SAT). But that wouldn't be the end.
We'd also get transformations for the following NP-complete problems, and each transformation would embody a free theorem about the nature of the structure of all instances of the problem ([2] for a bigger list):
* Graph theory: CLIQUE, HAMILTONIAN, K-COLORING (faster compilers!), COVER
* Number theory: TSP (faster packet routing!), KNAPSACK, SUBSET-SUM, PARTITION
* Formal systems: BOUNDED-POST-CORRESPONDENCE (holy shit, bounded Turing-complete analysis in P!?)
That's some serious free theorems! There's no reason to expect that whatever would give us so much stuff for free would be easy to prove. In fact, it's quite the opposite: The fact that any NP-complete problem, if it yielded, would give us deep insight into all of the others, should give us extreme pause before hoping that P=NP.
[0] https://www.scottaaronson.com/papers/pnp.pdf
[1] https://cs.stackexchange.com/questions/87073/what-are-the-ex...
[2] https://en.wikipedia.org/wiki/List_of_NP-complete_problems
But, I do have some comments:
1)
As far as a I can tell the fact that PRIMES is in P doesn't mean breaking RSA is. The problem in rsa is integer factorization for which we do not know whether it is in P. (But also do not know for it to be NP-complete.)
But here you are actually supporting my point: event in that case we could choose sufficiently sized keys.
2)
And yes, the fact that P is self-low does seem to be the best justification we have to give such importance to P vs NP. That's also somewhat related to what I was saying about Turing machines and random access machines having polynomial reductions between them. But that's just because we decided to ignore polynomial reductions.
Continuing my example with even number being the same: We can see that multiplying an even number by any number yields an even number. Does that in any way justify ignoring the multiplication alltogether?
P with a P oracle really is equivalent to P, but O(n) with a O(n) oracle is not O(n), it's O(n^2).
3)
We have many NP-complete problems that have practical algorithms that perform fast on real-world inputs. I don't see how getting a free theorem about K-COLORING would practically mean faster compilers if the polynomial exponent was galactic.
On RSA: You're right, but this is only the tip of the iceberg. There's a concept, "Impagliazzo's five worlds," which explains in fine detail how the various P!=NP and P=NP scenarios impact cryptography. Basically, whether P equals NP could be an easier question than another open question, whether one-way functions even exist. There are cryptographic practical implications.
On multiplication: You are correct that DTIME(n) ≤ DTIME(n^2). However, P = DTIME(n) + DTIME(n^2) + DTIME(n^3) + …
If you would like to consider that only some small sections of P are tractable, then that's an understandable stance to take. There is, as I've mentioned before, an entire subfield of computer science dedicated to trying to move matrix multiplication from DTIME(n^3) to DTIME(n^2).
On approximation: Integer programming is simply harder than approximation. That's all. The fact that the approximations are tractable doesn't slake our thirst for the precise answers. Moreover, we don't know how BPP and NP relate yet, so it could be that there are ways to solve problems exactly in NP by randomized algorithms. We've found a few hints at this already, but derandomization is a hard process. (We don't even know if BPP=P, although P≤BPP and BPP is self-low. The holy grail of derandomization would be to derandomize BPP to P.)
Finally, I really encourage you to take a bit of time to read the Aaronson paper I previously linked, because it explains all this in much more detail. You are free to continue to think that the problem is not interesting, but I encourage you to at least get a sense of why it is hard.
* 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 calculation problem.
* That you are wrong about the small epsilon. You can't make even that kind of guarantee in the face of NP hardness. What the market has a state may be wildly far away from the optimum, the market could be stuck in a local minima, and without P=NP you can't even know how far from optimum you are. Without a complexity class for markets you can't even begin to discuss it's properties, and that's what this paper is an attempt at.
It is your cleverness that misses the point, the author is trying to attach 21st century computational theory to economics (he may be wrong, but economic theories aren't going to help disprove it) and it's going to have some consequences.
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.
You can. https://en.m.wikipedia.org/wiki/Polynomial-time_approximatio...
> Any strongly NP-hard [which may include strongly NP-complete] optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP
I was criticizing someone for claiming the author's work is pointless. The author's work is an attempt to find a complexity class for markets (and the problem they solve). If we know the complexity class then maybe there is a PTAS. But without the author's work you can't begin to claim there is an epsilon.
In economics, yes. In real life, not so much.
Why not?
IE, if a person is only 1$ poorer than the efficient solution, that's not a big deal.
I'm well aware that P vs NP is a very hard question (I have studied quite some complexity theory, although I am a bit rusty), I'm saying that it does not seem as fundamental (or interesting) to computer science as people believe it to be.
There are problems that have approximations that can get arbitrarily close to the optimum. One particularly interesting case IMHO are so-called polynomial approximation schemes. These schemes can be used to create an approximation algorithm for any choice of approximation factor and that algorithm will have a polynomial time complexity, but the polynomial will depend on the actual approximation factor chosen.
I agree that it is an interesting problem to study, especially since it meshes well with my own biases that the efficient market hypothesis is too strong.
An equivalent system would have to have the same people, in control of their own resources.
If you just replace the people who are currently making decisions about themselves, with DIFFERENT people, them the principle agent is no longer making decisions for themselves. A different person is making thise decisions for OTHER people, which is the principle agent problem.
Surveys and computer generated questions sounds an aweful lot like other people making decisions over other people's utility functions and resources. IE, they are not the principle agent.
You'd have to prove that surveys or whatever are better at deciding what a person wants than the person themself.
Even if you have more resources, it is still different resources. It is still different people making decisions for what other people want.
The idea that the small number of countries with however many number of slaves distorts the markets is ludicrous.
My personal argument is that I don't believe markets solve either the principle agent problem or the economic calculation problem, and so to require them of other systems is hypocritical. But even if markets somehow do, then Turing completeness would strongly imply that there are other economic systems that also have those properties. Otherwise magic (which this paper is evidence against).