Scientists Prove Toxic Assets are Impossible to Regulate • Hacker News Board

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#11

Post by gojomo » Fri, Oct 23, 2009, 12:46 AM UTC

jrockway wrote: post #8

It's also impossible for a traveling salesman to find the best route between cities, but that doesn't mean that salesmen don't travel. Approximations are often Good Enough, and there are a variety of polynomial algorithms that produce Good Enough solutions to NP problems. Everything in the real world is impossible, but we can try and get good results anyway.

Exactly. And as the work of this year's Economics Nobel Elinor Ostrom has highlighted, communities often work out cultural norms that resolve difficult coordination and trust issues.

A regulator trying to preempt unfair dealings with rules may have no chance, no matter how wise and disinterested, but people trying diverse strategies over time eventually settle on something that's good enough. (And some scams and business cycles are an inevitable part of that discovery process.)

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#12

Post by kurtosis » Fri, Oct 23, 2009, 1:19 AM UTC

jrockway wrote: post #8

It's also impossible for a traveling salesman to find the best route between cities, but that doesn't mean that salesmen don't travel. Approximations are often Good Enough, and there are a variety of polynomial algorithms that produce Good Enough solutions to NP problems. Everything in the real world is impossible, but we can try and get good results anyway.

I believe that the paper argues that this is one of those cases where approximations are not good enough. You cannot read RSA encrypted email with approximate factorization algorithms. You can't forge a document and fool anyone with an approximate SHA collision. I'm not entirely convinced by this analogy but it was made by Appell, and others pointed out in an earlier HN thread that the authors are experts in approximation algorithms.

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#13

Post by cma » Fri, Oct 23, 2009, 1:26 AM UTC

Likewise, we should outlaw tide-charts since we haven't solved the n-bodies problem.

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#14

Post by slackenerny » Fri, Oct 23, 2009, 1:33 AM UTC

kurtosis wrote: post #12

jrockway wrote: post #8

It's also impossible for a traveling salesman to find the best route between cities, but that doesn't mean that salesmen don't travel. Approximations are often Good Enough, and there are a variety of polynomial algorithms that produce Good Enough solutions to NP problems. Everything in the real world is impossible, but we can try and get good results anyway.

I believe that the paper argues that this is one of those cases where approximations are not good enough. You cannot read RSA encrypted email with approximate factorization algorithms. You can't forge a document and fool anyone with an approximate SHA collision. I'm not entirely convinced by this analogy but it was made by Appell, and others pointed out in an earlier HN thread that the authors are experts in approxim…

Sanjeev Arora, paper's coauthor, but also leading expert on approximations to NP-hard problems, has posted a FAQ detailing why he thinks no approximation would help,

http://www.cs.princeton.edu/~rongge/derivativeFAQ.html

And also his response to RJ Lipton who believes approximation ought to work (but then again Lipton believes P=NP, so for him nothing is impossible):

http://rjlipton.wordpress.com/2009/10/22/helping-wall-street...

These are mostly practical reservations, carefully stated as to convince of intractability in the real-world case (which they do) but not prove in theory. Excerpt:

   current pricing and rating algorithms use monte carlo methods
   and would not solve densest subgraphs even for moderate parameters.
   So at the very least those should be changed.

Turns out problem they reduced their model to is open in terms of finding good approximation to it. Excerpt from the FAQ:

   The paper relies upon a stronger form of "P not equals NP", namely,
   that the planted dense subgraph problem does not have an efficient
   algorithm. (In fact it is conjectured that there is no algorithm
   to even compute any approximate solutions to this problem).

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#15

Post by jerf » Fri, Oct 23, 2009, 1:35 AM UTC

A lot of people are complaining that NP-hard doesn't mean you can't get good approximations.

I would like to remind you people that we are not talking about abstract problem spaces where you can count on the problems being essentially "randomly selected" for some suitable definition of random. We are talking human-created financial instruments, being created by agents with every incentive to game the system. Complexity analysis is a whole different kettle of fish when you have to assume a malicious agent generating the problems! Everything you think you know about approximation may or may not apply, and probably doesn't apply, because approximation algorithms never (or virtually never) start out with "Assume a hostile malicious agent has constructed your problem instance..."

The correct mindset here is probably the security mindset, where no matter how small or trivial the "arbitrary command execution as root" vulnerability is, you damn well better close it, because in the computing world the smallest crack can be easily widened large enough to drive a truck through.

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#16

Post by aaronblohowiak » Fri, Oct 23, 2009, 1:43 AM UTC

jrockway wrote: post #8

It's also impossible for a traveling salesman to find the best route between cities, but that doesn't mean that salesmen don't travel. Approximations are often Good Enough, and there are a variety of polynomial algorithms that produce Good Enough solutions to NP problems. Everything in the real world is impossible, but we can try and get good results anyway.

>It's also impossible for a traveling salesman to find the best route between cities

It is not impossible, merely Hard.

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#17

Post by anamax » Fri, Oct 23, 2009, 2:06 AM UTC

Why would anyone think that the value of a non-trivial asset could be expressed as a single number?

Let's consider a house. Clearly the amount of money that someone would pay for said house varies from person to person. Which value is "correct"?

Before you jump in with some clever aggregation function, suppose that the owners want to sell said house. Will they agree to the value that your aggregation function produces? (They can choose to delay the sale, so if they don't agree, your function may well deprive someone of the ability to buy said house at a price that its acceptable to said someone.)

Ah, but you say that stock is stock. That's true, but again, different people have different priorities. I probably weight dividend paying history differently than you do. I have different expectations on inflation. I need to go liquid at different times. The end result is that we disagree about the value of the same share of Microsoft stock.

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#18

Post by crc32 » Fri, Oct 23, 2009, 2:18 AM UTC

anamax wrote: post #17

Why would anyone think that the value of a non-trivial asset could be expressed as a single number? Let's consider a house. Clearly the amount of money that someone would pay for said house varies from person to person. Which value is "correct"? Before you jump in with some clever aggregation function, suppose that the owners want to sell said house. Will they agree to the value that your aggregation function produce…

The single number does not have to be 100% accurate to be useful. The end result is that though we disagree about the value of the Microsoft stock, it nonetheless has been assigned a price by some invisible hand.

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#19

Post by [deleted] » Fri, Oct 23, 2009, 2:56 AM UTC

andylei wrote: post #5

hold the phone, just because a problem is NP complete does not mean that it is computationally intractable. most algorithms in the real world are NP complete, but people still try to solve them. just because there's no way to prove which CDOs have been tampered with doesn't mean that you can't figure it out. there are local search algorithms that may be able to give you a pretty good answer, even if you don't know fo…

[deleted]

Re: Scientists Prove Toxic Assets are Impossible to Regulate

#20

Post by gloob » Fri, Oct 23, 2009, 4:09 AM UTC

aaronblohowiak wrote: post #16

jrockway wrote: post #8

It's also impossible for a traveling salesman to find the best route between cities, but that doesn't mean that salesmen don't travel. Approximations are often Good Enough, and there are a variety of polynomial algorithms that produce Good Enough solutions to NP problems. Everything in the real world is impossible, but we can try and get good results anyway.

>It's also impossible for a traveling salesman to find the best route between cities It is not impossible, merely Hard.

Which, once translated out of engineering jargon, means "Practically impossible in the general case, assuming you are not willing to accept an approximation."