So markets can only be (perfectly) efficient or competitive, not both at the same time. Largely theoretical but it tracks common sense!
The title on this HN submission is just wrong. Click on the link and find out.
The title is wrong but you’re also wrong. Read the abstract of the paper. Here’s the relevant section:
> Combined with Maymin (2011), who proved that market efficiency requires P = NP, this yields a fundamental impossibility: markets can be informationally efficient or competitive, but not both.
Markets are competitive if and only if P === NP! Now seriously, I wonder if AI collusion/use in investments would add to the market inefficiency and create opportunities for observing investors.
NP factorial sounds like NP-ultra-hard.
NP! should be something like NP^NP, which is well known to be Σ^2_P. Slightly larger, but still inside PH.
Yeah, the most obvious recent example of this is RealPage’s YieldStar product. It advised property managers on what they should set their rental rates to, and allegedly established a cartel in which RealPage’s customers coordinated in pricing their units. YieldStar was technically an “AI” product, but I don’t really think the computational abilities were what enabled the collusion. RealPage’s employees (according to…
I’m not sure the use of a common algorithm was the most damming part of that. They also pooled otherwise proprietary information and penalized landlords who failed to follow the “recommendations” You could imagine the exact same scheme without the use of a computer.
A lot of things are only true if P != NP but says nothing about P being within epsilon of NP.
Not quite sure what you're suggesting here; perhaps it's satire? If P!=NP then it is arbitrarily smaller, for the same reason that e^x > Cx^N for any constants C and N, as long as x grows big enough. There is no epsilon in that can overcome that, no matter how big you make it, because x will eventually dominate the equation. There are a lot of cases where pragmatically x remains small enough that it doesn't matter, a…
No, it's not satire. The difficulty of finding the optimal solution says nothing about what it takes to come within 99.999% of optimal with 99.999% probability.
So I'm not talking about the number of steps needed to prove optimality with a correct P algorithm versus an exponential one.
I'm only talking about how this applies to the efficient market hypothesis.
These things should not be submitted here unless there is meaningful editorial/peer commentary about it being significant or correct. There are dozens of bogus attempts to prove and disprove this
There's a long history of proving results like this.
NP-Completeness is the norm, not the exception. Any system that's complex enough is almost surely NP-Complete. For similar reasons, Turing Machine Equivalence is also the norm, not the exception.
These results are interesting but not unexpected. A more interesting question is under what conditions is the problem difficult to find solutions for. Many NP-Complete instance ensembles turn out to effectively have polynomial time solutions (3-SAT w/ uniform clause variable choice, Hamilton Cycles in Erdos-Renyi random graphs), so proving NP-Completeness is not a death knell for approximation.
The actual paper's title is "Markets are competitive if and only if P != NP" Seems that HN's auto-headline rewriting in this case has made a critical error :) >Artificial intelligence, by expanding firms' computational capabilities, is pushing markets from the competitive regime toward the collusive regime, explaining the empirical emergence of algorithmic collusion without explicit coordination. I have to dig more i…
The paper seems to be based on an invalid assumption. From the abstract: > If P != NP, the collusion detection problem is computationally infeasible for markets satisfying a natural instance-hardness condition on their demand structure, rendering punishment threats non-credible and collusion unstable. ...and then from the paper: > Stigler (1964) famously argued that the “chief difficulty” of collusion is detecting “s…
Why can’t my firm react if we find out we’re being undercut by a competitor? Or are you saying that we “know” only in a theoretical, “we can’t prove we’re not being undercut” sort of way, but without “proof” we can’t take action?
The fact that free markets don't exist, and that supply and demand is not a natural law that implies efficient markets has never stopped people acting like both are true and stuffing fingers in their ears. But, both free markets and supply/demand are useful enough concepts to talk loosely about processes to understand the interest that I'll enjoy digging into this.
They're not just useful concepts tho, they're how every business operates, and the concepts cover the vast majority of situations. The behavioral economics/Freakonomics thing was like "Hey, here's this thing that might if you squint real hard fall outside of efficient market theory" and then for a decade people took that to mean that that the base concepts were worthless , which was a severe overcorrection from peopl…
The vast majority of real world businesses create prices based on cost plus systems, not on supply/demand, which are generally impossible to measure directly. Another good chunk of smaller businesses simply copy the prices of larger businesses, at least in b2c markets. Sure, if their goods are not selling, they might reduce price, but they might try other tactics as well (marketing, targeted discounts, etc).