The first corollary that I see is that greedy algorithms will almost certainly suck for society at large. I'm looking specifically at the meme that public companies are somehow required to maximize short-term profits for their shareholders.

Some NP-complete problem classes have polynomial time approximation schemes, but not all, unless P=NP. That is to say, sufficiently large markets may be arbitrarily inefficient. I'm curious to see that dichotomy resolved.

In every case of problems classes I have seen, in my admittedly limited experience, polynomial time approximation schemes only fail under pathological circumstances. I'm not convinced that there's a connection between pathological problem instances and problem sizes, necessarily, and I'm even less convinced that real-world markets would reflect such pathological instances.

Granted, but such a PTAS would need to be agreed upon and faithfully executed by all market players.

Greedy algorithms suck compared to what? If the greedy algorithm still converges fastest and is closest to optimal compared to any other practical scheme, the paper's result still does not say anything of practical use.

They suck at escaping local minima, for one.

Your "if" is doing a ton of work there, and this paper is quite abstract market theory. The "practical use" is to better contextualize the efficient market hypothesis.

They don't escape local minimum at all. And that means they suck for society at large compared to what? Random guessing? A corrupt government price system? An omniscient one that can solve NP hard problems? The "if" motivates answering the question.

Anyway markets have a lot more going on than a simple greedy algorithm. For injecting noise into the optimization to get out of local minima. Markets clearly have a lot of this.

> And that means they suck for society at large compared to what? Random guessing? A corrupt government price system? An omniscient one that can solve NP hard problems?

There's an intriguing recent book (that, admittedly, I haven't read) called "The People's Republic of Walmart" https://www.penguinrandomhouse.com/books/564287/the-peoples-...

If large corporations are the shining beacons of capitalism, how come they are run internally as top-down planned economies? And to the extent they prove than planning can work at scale, could planning work society-wide? Not saying I agree or disagree (again, I haven't actually read it), but dusting off the ye olde calculation debate and updating it for today seems like an interesting idea.

The worst part of centrally planned economies is that they are prescriptive and essentially authoritarian in nature. If they make mistakes then nothing prevents them from repeating the same mistake. There is no threat of the central planner being replaced.

If all Walmart does is make mistakes then they go out of business. Central planning won't work but federated planning with 20 super corporations that are in competition with each other might actually be good enough. The only problem is that we both need and want the underdogs(startups) and this would undermine them.

> There is no threat of the central planner being replaced

You are conflating an economic model with a political one. In fact, the central planner doesn't even need to be a person, but a set of assumptions and strategies that can be measured against the benefit they provide and be continually adjusted.

You touch an important point, however. The people most affected by Walmart's central planning, their employees, have no say in what strategies and assumptions the central planner uses and that removes any incentive to provide benefit to them.

The EMH is also conflating an economic model with a political belief system.

The notion that these huge corporate bureaucracies are somehow "efficient" at anything except trashing the environment and homogenising and controlling - if not ultimately economically cannibalising - their own workers and customer base is clearly counterfactual.

> The worst part of centrally planned economies is that they are prescriptive and essentially authoritarian in nature. If they make mistakes then nothing prevents them from repeating the same mistake. There is no threat of the central planner being replaced.

From reading the book synopsis (again, I haven't read the book itself), it seems the authors are proposing some kind of democratic socialism rather than USSR-style authoritarianism. Is it workable? I have no idea. To me it seems that USSR-style authoritarianism and current Western neoliberal capitalism are but two small dots on the political economy spectrum. There are other ways of organizing society as well; certainly worth thought experiments to see what kind of other options there might be and what we might learn from them.

I'd say startups are a much better example. But I didn't come here to argue politics, just asked for someone to describe their superior optimization process (math being my actual interest, so still waiting to hear it). I wouldn't describe "do what walmart did" as a particularly useful optimization strategy.

> But I didn't come here to argue politics, just asked for someone to describe their superior optimization process

Look. I don't believe that P=NP. I can't describe a superior optimization process, and if I did, I would claim the Clay Math prize. I'm also not an economist.

My takeaway is that any simple strategy is almost certainly bad in the long term. You can optimize your own personal take, but in doing so, "the invisible hand" isn't going to somehow flip that into a benefit for all.

The fact that large corporations are certainly top-down, planned, and successful in a meaningful sense is certainly a rhetorical blow to anyone who believes in a simplistic way that "markets" and "decentralization" are literally the only way to be large and successful.

But if large corporations prove the efficacy of planning at scale, then they surely prove the drawbacks as well. What are the society-wide central planning equivalents of layoffs and maximizing shareholder value? Does a centrally planned corporation outsourcing their supply chain or HR department represent a fundamental failure of central planning?

It seems quite obvious that 'competition' between the various 'planned economies' and choice between them by consumers is generally a good thing. One that would not work for a fully centrally planned economy.

That said, it is indeed quite interesting to figure out at what size such central planning starts to become non viable. And for that the observations: "It is viable for wallmart, but not for all of the USA" give some interesting bounds.

I’ve always seen this debate as kind of moot. The thing with optimizing, is that you always optimize with a target.

Large corporations rule top-down because goals are set at the top. That’s very different from a society problem.

Greedy algorithms can be arbitrarily bad on large NP-hard problems. But if we're using terms metaphorically, we could also say each greedy company is just a Monte Carlo sample of the whole economy. Some fail or stagnate in local optima; others succeed for longer. But the economy is too complex to expect anyone to ever find a global optimum, so continuous exploration of the landscape is important for overall growth. Thus we can aim for and admire success but should be vigilant against anticompetitive behaviors that stifle the sampling.

> I'm looking specifically at the meme that public companies are somehow required to maximize short-term profits for their shareholders.

I love that meme for how wrong it is. Public companies don’t maximize short-term profits, maximize profits (with future profits discounted).

The fact that to a lot of people “profits” == “short term profits”, reveals quite a lot about our assumptions and time preferences..

Indeed. I can think of plenty of examples where companies strongly focus on long-term profits, I mean, if they don't it's likely the company won't exist.

Now if someone said companies focus on continuous quarterly growth, and sometimes sacrifice a portion of long-term growth for short-term growth, I could agree with that.

Well what I think is interesting as an amateur with an interest in economics and investing, is that if P!=NP then it would cast a great deal of doubt on so-called Technical Market Analysis or "Technicals" which are predicated on the Efficient Market Hypothesis being true.

My own suspicions have been for quite some time now that fundamentals are what move markets and that technicals are mostly bullshit and are only valid because algo-traders school like fish based on technicals.

The efficient market hypothesis doesn't say anything about the amount of time it might take for markets to iron out inconsistencies and take into account new information; "the market can remain irrational longer than you can stay solvent." It's the sort of thing that's hard to falsify because you can always say "oh, it'll eventually become consistent." Given that, I don't think this fundamentally changes anything about "technicals," even if P!=NP, but my intuition a priori is also the same as yours, that "technicals" are mostly window dressing anyways.

>The efficient market hypothesis doesn't say anything about the amount of time it might take for markets to iron out inconsistencies and take into account new information

Actually it does. The central premise of the Efficient Market Hypothesis is that all relevant information is already priced in.

>"the market can remain irrational longer than you can stay solvent."

Irrational behaviour by uninformed investors is theoretically already priced in, if the market is efficient.

Taking that literally, it's clearly false; information can't affect prices faster than the speed of light.

We're literally talking about a paper comparing emh to np=p, isn't pointless pedantry the name of the game?

Ah, but here's an interesting topic for an ambitious research project, "Efficient relativistic markets". The proposal would score cross-disciplinarity brownie points in the evaluation committee.

You might be surprised to learn that the well-known economist Paul Krugman wrote in the late 70s about trade in relativistic scenarios, see https://en.wikipedia.org/wiki/The_Theory_of_Interstellar_Tra... and http://www.standupeconomist.com/pdf/misc/interstellar.pdf (for the paper itself).

Ah, but of course. When you're not a subject matter expert what you think is a novel idea is something the actual experts have already investigated decades ago. sigh, oh well.

I mean, in that sense the efficient market theory is immediately false, since someone must be the first to learn some new information and price it in.

Thing is, the hypothesis can be useful whilst being only approximately true. If it is true to with 0.1% then, in most cases, it is quite appropriate to model it as being perfectly true. And obviously, there are other cases where that model isn't useful. In those cases, it would probably still be useful to take the 0.1% number into account.

I thought technical analysis (as opposed to fundamental analysis) assumes markets aren't efficient and subject to things like herd behavior and other psychological effects of human decision making. Otherwise things like momentum trading wouldn't work (i.e. price would just gap to the true value if markets were indeed efficient). If tech analysis works at times for me it would show that markets aren't that efficient as a whole.

IMO markets can't be efficient because we as humans aren't - our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc.

> our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc.

The intuition behind the efficient market hypothesis is that each of these deviations from "homo economicus", if it occurs in a market, is an opportunity for someone else to make money. EMH says that opportunity won't be wasted, at least for very long.

That still means efficiency is lost. E.g. the market might fluctuate between non-optimal state. And then again in case monopolies build up, then there is no easy way to get out of a suboptimal state, because there are no real opportunities for someone else.

Technical analysis doesn't depend on EMH being true, in fact it depends on EMH being false. It is not evidence based in any way.

>How much does this matter given that in the vast majority of cases, we don't care about exact/perfect solutions to problems that might be NP complete in the general case, but usually have heuristic methods that work well enough for most practical purposes?

Well, define "well enough"...

We do get results. Are they "well enough"?

Even better, in practice we have amazing tools nowadays that can solve practical NP complete problems in a reasonable amount of time (I mean, optimal solutions, not OK-ish ones).

Well given that this assumes rational actors and humans aren't really rational, it's probably not very important in practice.