4 ms·
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 comp
by klyrs 6y ago
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.
- whoisburbansky 6y agoIn 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.
- klyrs 6y agoGranted, but such a PTAS would need to be agreed upon and faithfully executed by all market players.
- unishark 6y agoGreedy 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.
- klyrs 6y agoThey 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.
- unishark 6y agoThey 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.
- jabl 6y ago> 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-republic-of-walmart-by-leigh-philips-and-michal-rozworski/ 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.
- unishark 6y agoI'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.
- klyrs 6y ago> 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.
- mcbits 6y agoGreedy 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.
- xondono 6y ago> 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..
- refurb 6y agoIndeed. 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.