Markets are Efficient if and Only if P = NP

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1773169

by ionfish • 15 years ago

154 83 15 years ago

papers.ssrn.com

It feels to me that all he's done is show that the "instantly" in the usual definition of markets being "efficient" is a nonsense. Prices must take time to compute, you can't know the correct price instantly even with access to all the past information.

He proves that, but it doesn't seem that surprising to me.

gfodor2• 15 years ago

If it's true it uproots a lot of conventional wisdom about trading and the ability to time the market.

mquander• 15 years ago

No, it doesn't. Relevant conclusions about markets in a theoretical sense all depend on (from the link) "current prices...[reflecting]...information available in past prices," which isn't even approximately true in the real world; current prices are driven by irrational actors with incomplete information.

peteretep2• 15 years ago

I was coming here to write almost exactly this.

Markets are provably not 'instantly' efficient because arbitrage exists. Arbitrage is simply not possible in an efficient market, because it's an exploit of inefficiency.

However, exploitation of abitrage (and of knowledge generally) is what makes markets largely efficient.

Rickasaurus• 15 years ago

The point though is that whoever has the most computational power has the most power to exploit arbitrage.

CWuestefeld11• 15 years ago

While I'm pretty much a free-market zealot, I'm also a Hayek groupie. It seems to me that Hayek's work should show us that markets approach perfect efficiency.

Because the market is a hideously complex system that only produces its information as an evolved, emergent system, then it is likely that its output is not precise but only extremely close to optimal.

jbooth9• 15 years ago

Was the fall of 2008 "extremely close" to optimal?

I'd submit that worldviews based on 1-dimensional criteria like "market!" or "hayek!" fall pretty far short of the mark. Although I can see the attraction. It's nice to simplify things to a level where a human being can actually have the answers with a high degree of confidence.

Both the tea-party-hayekians and the linked paper fall into this trap.. what about information asymmetry? What about borked incentives? What about just plain stupid? "I played golf with the guy so I'll buy it"? "I know these instruments are crap but I'll sell them to my clients to get them off my balance sheet"?

A friend was telling me at his old job, they actually worked in season tickets to a luxury booth at Yankee stadium into a very significant tech purchase. Is that market efficiency?

ChuckMcM• 15 years ago

Pretty much in a nutshell his exposition. For me, my interest lies in the economic value of information, and one way in which information gains value is by being 'timely.'

When explaining to folks I often use the example that the 15 minute delayed stock price feed (aka 'ticker') is less valuable than the real time stock 'ticker'. This is intuitive for many folks but the OP's work shows the math behind that intuition.

Stock price feeds are generally used by algorithms to anticipate the market price of a commodity and act when there is a delta between that and reality. They 'manufacture' new information by taking that real time stock feed and identifying trends. Their market value then becomes a function of their ability to identify trends sooner and thus allow for capturing the most value between the current price and the correct price.

3pt14159• 15 years ago

Title should read: "If markets are perfectly efficient P=NP" rather than "Markets are efficient if and only if P = NP". For example, say P = NP, but the only person that knows the proof is me. If I start using my knowledge that P = NP to trade I will not have enough capital to swing the market to truly reflect the efficient price. Therefore it does not follow that if P = NP the market will be perfectly efficient, which is required in an "if and only if" proof.

gwern• 15 years ago

> If I start using my knowledge that P = NP to trade I will not have enough capital to swing the market to truly reflect the efficient price.

How long would it take you to gain enough capital to start moving prices? If you have a systematic edge on all trades...

In any event, I didn't find OP interesting the first time and I don't know. Most people aren't using OP's extremely strong definition of efficient market, but merely saying that humans and current algorithms cannot over long periods extract money; it's a statement about the market vs other actors, not markets versus omniscient gods.

kragen• 15 years ago

Results like general equilibrium are conditional on the OP's extremely strong definition of efficient market. Whether or not you personally can get rich by beating the market is not the only possible interesting question about economics!

jsharpe• 15 years ago

Or maybe just "Markets can be perfectly efficient if and only if P = NP".

bugsy2• 15 years ago

In the paper he states "I also prove the converse", meaning the iff clause is justified.

tokenadult• 15 years ago

Hacker News submission and discussion from 540 days ago of previous version of same author's paper:

http://news.ycombinator.com/item?id=1144548

nopassrecover• 15 years ago

I also posted the author's video explanation here the other day: http://news.ycombinator.com/item?id=2867429

aklein• 15 years ago

"The majority of financial academics believe in market 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 efficient, or P ≠ NP and the markets are not efficient."

I'll hazard a guess the computer scientists are right, but most financial academics will probably get by just fine if markets are approximately efficient - if prices can be estimated in probabilistic polynomial time.

mseebach• 15 years ago

I'm pretty sure financial academics don't claim that markets are efficient, but that they tend towards efficiency.

wpietri• 15 years ago

For those wanting to know more about the efficient-markets hypothesis, Wikipedia has a good article: http://en.wikipedia.org/wiki/Efficient_markets

My amateur understanding is that most academics get that it's a simplifying assumption, but that a lot of other people treat it as a guarantee. It's sort of like people who learn a little about evolution and then conclude that a) we are the most highly evolved organism on the planet, and b) we are therefore perfect.

zeteo• 15 years ago

Even if the problem that markets are trying to solve is NP hard, this doesn't mean anything. Market forces are always subject to random factors. For practical purposes, randomized approximation algorithms are actually a great choice for tackling NP hard problems.

tmeasday• 15 years ago

Sometimes. I think the simple answer to that is 'it depends on the problem'.

knowtheory• 15 years ago

That's not an answer, that's an IOU for an answer, unless you can begin to describe broad classes of problems and how they differ.

bradshaw1965• 15 years ago

People get tied up in knots about the Efficient Market Hypothesis. The factor that often gets ignored when approaching the problem is the costs factor. Trading fees, Analysis, Commissions, etc. make it very hard in practicality to beat passive investment with the markets only being passably efficient.

artsrc4• 15 years ago

I think that analysis ignores tax effects. To have a stable excess return you need some collection of people accept a stable lower return. This is possible if you have different tax regimes. Tax advantaged entities can accept coupons/dividends, and highly taxed entities want capital gains.

hahaonlysirius• 15 years ago

Since politicians have no business trying to solve NP problems, perhaps we'd better deregulate the market.

rvkennedy• 15 years ago

Been there, done that, bought the recession. Regulation, of course, isn't "solving the NP problem", it's modifying the boundary conditions to prevent the system from getting too far out of whack.

imogynn• 15 years ago

Free markets are a great heuristic.

aphyr3• 15 years ago

If we allow that large, computationally capable entities are likely to form in free markets, it is probable that individuals will be faced with a market in which the prices of major goods vary wildly from minute to minute, from person to person, and are predicated on both fantastically complicated loyalty programs and data collected about the individual and current market circumstances, processed in statistical models that no human has ever understood or evaluated. A market in which machines algorithmically game humans and each other by adjusting prices and the nature of the goods themselves to exploit cognitive or algorithmic flaws in other actors.[1]

The classical model of efficient, free markets ignores computational complexity and time bounds, as the article notes. These were reasonable approximations for a hundred or even twenty years ago, but I can forsee environments in which these factors lead to significant asymmetry. I question whether humans can really compete successfully in this environment, and whether the process of doing so is really best for us.

[1] Cases in point: Amazon, insurance companies, grocery stores, every major retailer, Google, high-frequency trading firms, airline ticket sales.

artsrc4• 15 years ago

Even fairly simple tools must be able to game humans. We must be so bad at making rational decisions that prices typically are set just below a psychologically significant level for example $2.99. This of course assumes the market is correct in its assessment of us.

NY_Entrepreneur• 15 years ago

He's mostly smoking funny stuff: He's talking applications of optimization. Okay. Optimization contributes problems, e.g., integer linear programming, in set NP-complete only if one insists on exact optimality down to the last tiny fraction of a penny of cost in the worst problems that can occur, even in principle, in execution time that grows no faster than a polynomial in the size of the problem. That's a LOT of very special and quite unrealistic context.

E.g., it's not the least bit clear that finance needs to attack the worst case problems. Even if so, finance, anywhere close to reality, doesn't need to get solutions that save all of the last tiny fraction of a penny.

If relax worst case problems and saving the last tiny fraction of a penny, then the situation is MUCH different. E.g., once I got a feasible solution to an ILP with 40,000 constraints and 600,000 variables within 0.025% of optimality on a 90 MHz Intel processor in 905 seconds. More generally, here's an easy approach to the ILP problems: Just drop the integer constraints, solve with LP, and then round to integer values. For the LP solution, if insist, then use a polynomial LP solver. Crude? Sometimes. Always crude? No.

He's making a common mistake: He's assuming that because in general ILP is in NP-complete that good work on all practical ILP problems has to be too challenging, and that's nonsense.

bugsy2• 15 years ago

Just the concept of the proposition of this paper is pretty amazing. The author Philip Maymin is a serious bad ass for doing this proof. What a dude.

adas6• 15 years ago

shut up!!!

adas6• 15 years ago

FUCK YOU

adas6• 15 years ago

YOU'RE GAY

adas6• 15 years ago

ASSS

adas6• 15 years ago

PENIS

Markets are Efficient if and Only if P = NP

Related Stories