?

Log in

Previous Entry | Next Entry

a few links

Is the Efficient Market Hypothesis equivalent to P=NP? Bizarre (and probably wrong) but intriguing idea:
http://arxiv1.library.cornell.edu/abs/1002.2284

Nice visual representation of 2011 budget breakdown:
http://www.nytimes.com/interactive/2010/02/01/us/budget.html

The Dalai Lama on Technological Change:
http://www.youtube.com/watch?v=_CgZ2qkRSpo

I have a ticket to see the Dalai Lama speak in person 2 months from now in Indiana. I'm looking forward to hearing what he has to say. In the above link, he sounds a lot like a transhumanist when he says he thinks one day humans should be improved by becoming part machine and "that would be good". Out of context I can't tell what exactly he means by that. But it's an interesting comment.

Comments

( 9 comments — Leave a comment )
puellavulnerata
Mar. 7th, 2010 12:15 am (UTC)
I'm pretty sure the Weak EMH implies P = NP direction of that one is wrong because he's redefined the semantics of placing orders on the market in such a way that brokers need to solve an NP-complete problem to decide transaction prices, but it's subtle and I'm not sure and need to think about it more. Applying computational complexity to economics is an interesting idea whether or not this application of it is valid.

Speaking of subtly wrong but interesting approaches to P vs. NP, there's another paper on arxiv (which I couldn't dig up the link to easily and am short on time at the moment) that argues P = NP because soap films minimizing surface area solve NP-complete problems and you can simulate the underlying physics in polynomial time in the system size, but he never justifies the assumption that the corresponding physical system settles to equilibrium in polynomially many time steps, and I suspect on thermodynamic grounds that this is false; the energy gap between the lowest and next-lowest energy configurations decreases exponentially in system size.
onhava
Mar. 7th, 2010 04:17 am (UTC)
I suspect on thermodynamic grounds that this is false; the energy gap between the lowest and next-lowest energy configurations decreases exponentially in system size.

Indeed, Scott Aaronson did the experiment with soap bubbles (scroll down the page a bit) and found they often get stuck in local minima, just as one would expect.
firmament
Mar. 7th, 2010 04:26 pm (UTC)
What do you think about the economists arguing that the global financial crisis falsifies the EMH (or, perhaps more broadly, strongly implies that it is wrong-headed).
spoonless
Mar. 7th, 2010 06:41 pm (UTC)
I think it depends on which version of the Efficient Market Hypothesis you're talking about. This EMH <-> P=NP paper deals specifically with the weak EMH. And not everyone even agrees on what the right definition for weak, semi-strong, and strong version of it are.

I don't have strong opinions on the EMH, realizing that it is a complicated subject and I'm not an economist. However, I tend to lean towards agreeing with this essay, which indicates that some form of the weak EMH probably holds but stronger forms do not:


http://johnquiggin.com/index.php/archives/2009/01/02/refuted-economic-doctrines-1-the-efficient-markets-hypothesis/


According to this, it's the semi-strong version that will have to be rejected after the financial crisis (and may have been widely accepted before it). While the weak form still holds up to a lot of empirical data.

So the claim in this P=NP paper is far bolder, and upon reading it I find a lot of the reasoning seems skethcy... it's an interesting analogy, but I just don't think I buy the idea that you have to search the entire possible exponential pattern space in order to identify patterns. I think both people and computers have more efficient ways of pattern recognition, whereas the case he's thinking about is a worst-case scenario which would almost never be relevant in practice. At least that's my take on it; could be wrong.
spoonless
Mar. 7th, 2010 09:46 pm (UTC)
This book looks like it will be excellent:

http://zombiecon.wikidot.com/start
firmament
Mar. 7th, 2010 11:43 pm (UTC)
Yeah, I saw some early chapters of this when he was posting it on Crooked Timber. In general, I wish I had a better grasp of econ.
spoonless
Mar. 8th, 2010 12:27 am (UTC)
me too

I did several interviews with Goldman Sachs and other financial firms last year, which gave me a good excuse to learn about some of this stuff, like the Capital Asset Pricing Model. But there is still a lot of the picture missing that I don't understand. Then again, I get that impression that economics is just one of those subjects that still nobody really understands.
easwaran
Mar. 7th, 2010 10:41 pm (UTC)
Not having read this particular discussion about the connection between EMH and P=NP, I would have thought that EMH was much stronger. Just as you can come up with market problems that are NP-complete, it seems to me that you should be able to come up with non-Turing-computable market problems, so that full efficient markets would be required to solve uncomputable problems. Perhaps there's a natural way to reduce the logical strength needed by weakening the EMH, but I should think about this.
spoonless
Mar. 8th, 2010 12:37 am (UTC)

I would have thought that EMH was much stronger. Just as you can come up with market problems that are NP-complete, it seems to me that you should be able to come up with non-Turing-computable market problems, so that full efficient markets would be required to solve uncomputable problems.

I'm not sure exactly what you are saying, but I think you must be addressing an entirely different issue from what this paper is addressing.

His claim is that you can solve any problem in NP in polynomial time just by placing trades on the open market and watching what happens to the asset prices, if the weakest efficient market hypothesis is true. Conversely, he also claims that if P=NP, then the weak efficient market hypothesis must be true (this seems far more believable).

So when you say you'd have thought the EMH is "must stronger", are you talking about the strong EMH (if so, he's not even considering that in the paper)? And assuming you think it's plausible that the weak EMH is true, do you really think you can exploit that to solve NP-hard problems?

Edited at 2010-03-08 12:38 am (UTC)
( 9 comments — Leave a comment )

Profile

blueshirt
spoonless
domino plural

Latest Month

May 2017
S M T W T F S
 123456
78910111213
14151617181920
21222324252627
28293031   

Tags

Powered by LiveJournal.com
Designed by Lizzy Enger