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.
Very interesting. The author claims to have proved that markets can be informationally efficient or competitive, but not both. The implications for policy and regulation are significant.
The author looks credible:
https://philipmaymin.com/about-philip
Thank you for sharing this on HN.
--
To the mods: The title needs to be edited to replace the equal sign with not-equal.
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 people that didn't understand economics.
Well, for better or worse, markets are becoming increasingly dominated by "non-biological utility maximizers" - mostly hft bots, but now also llm-based reasoning agents.
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
In a P=NP world, it still takes only one uninformed participant to make the market inefficient. I don't think the implication is bidirectionally true unless you assume every single player is rational, infinitely smart, and has access to the same set of information.
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.
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 into the paper but I don't see how this follows, except in the most straightforward way. Basically, if everyone uses the same methods to derive price, of course there will be "collusion", or in other words, everyone will have the same price. But this doesn't seem like a result of compute per se, but simply better communication networks and information flows. You could have gotten the same result in medieval England by having everyone post their selling prices on the town square board.
Again, I haven't dug into the paper yet, but it seems like what really matters for firms is "compute"/$ (if the "compute" is an LLM or an assistant that has to go walk the 10 minutes down to the square makes little difference)
Edit: Isn't another implication of this, that increased compute -> collusion imply that increased compute -> communism becomes feasible?
I think this goes to my point above though, the primary problem preventing fully automated luxury communism isn't compute per se, but actually observing the information flows to make it possible. Capitalism famously solves this information problem through the pricing mechanism. So in effect, he's arguing that extra compute makes information gathering more efficient, and at the limit you get perfect information. Which, yeah, I guess so. Assuming everything can be perfectly measured, even theoretically.
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 the DoJ[0]) would actively monitor whether companies were following their pricing recommendations and call up companies that defected. And the software itself used dark patterns to make it easier to simply follow the YieldStar pricing suggestions, rather than set a lower rental rate and be more competitive. The algorithmic pricing I think did allow people to launder their own judgement and simple “trust the process” in a way that in the past would have required knowing complicity with the cartel, but I don’t think it required substantial compute capacity.
(This isn’t a comment on the paper by the way, which I glanced at but did not have the background knowledge to fully comprehend)
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.
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 “secret price-cutting.”
The thing is that Stigler's insight is far from proven, and indeed, the primary difficulty in collusion is often not the detection of defection. Firms know they're being undercut all the time. The problem is that very often, there is nothing they can do about it. Markets are specifically structured as firm-to-firm transactions, where competing firms have no leverage over what your firm can do or what sort of transactions you can conduct, and as long as this condition holds it doesn't matter if you know that a competitor is fucking you over, you can't do anything about it.
I'd argue that the increase in collusion and anticompetitive behavior lately is because these conditions increasingly don't hold. When you intersperse another party in the transaction, eg. a regulatory agency, permitting body, or exclusive distribution deal, you introduce a leverage point for incumbents to punish competitors who choose to undercut them.
This feels like it's pointing in the same direction Hayek was already pointing 80 years ago. This paper says that even if we had enough computing power to solve these problems, Hayek's argument was that we still wouldnt have all the information needed to do those calculations in the first place. That information is spread across millions of people, constantly changing, and often only known locally. So even if the computation became easy, getting all the inputs would still be impossible to achieve
I don't have the mathematical chops to really analyze this on my own. Is this a bigger deal than the fact that real world markets already violate all the theoretical assumptions (e.g. unimpeded access to new entrants, perfect information, etc.etc), and so, in practice are never perfectly competitive or efficient?
Defi does a pretty good job regarding unimpeded access in comparison to the more traditional venues. This isn’t just about getting money into the system, but also what instruments you have access to.
The term ‘perfect information’ is a bit of a mirage, and has been shown to be impossible in physics (uncertainty principle).
What really matters is information advantage: Does your inexact expected value function consistently beat others’ calculations in the market. Here, the true value - value really is just a word and is dependent on people - is irrelevant.
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, and a P algorithm will give you an answer more quickly. (For the same reason I only ever write bubble sorts: I would only write my own at all if I knew that the list would never be bigger than 10. Even then it's only when using the library is too much trouble for some reason.)
But we care about P and NP when the number can potentially be very, very large.
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.
I don’t think anyone in the business thinks that the markets are 100% efficient, just that they are sufficiently efficient that beating them is a genuinely hard job requiring heavy, expensive analysis.
The argument structure is interesting, and reminds me a lot of Solomonoff Induction, but constrained into NP by the assumptions. I'm not sure the front half is enough to support the back half of the paper arguing that the current LLM craze means firms are actually running collusion detection algorithms, even unintentionally.
When everyone uses AI to study the same indicators and figures out how the prices move with those indicators they all start investing at the same time and the prices move together. AI silently gets everyone on the same page.
next stage - a single AI which computes the "correct" price that everyone else agrees on, and instantly reprice all financial instruments without trading them, thus not paying transaction costs
I hate to make the worn out AI to RNG comparison, but this kind of simultaneous "collusion" is really like assuming that everyone is using the same RNG seed to make their calls.
This is interesting. Adam Smith said "People of the same trade seldom meet together, even for merriment and diversion, but the conversation ends in a conspiracy against the public, or in some contrivance to raise prices."
The annoying part is that, as the same Adam Smith says, regulating industries would end up enforcing such assemblies, reinforcing the problem... after all, industries can share information via the market itself...
And proposed solutions end up being controversial: employees ownership, open source, paying taxes over stocks ownership... or just hoping that colluders will be broken by a randomly ocurring incumbent...
It's a vast generalization of the cost to verify a problem/solution.
- P means polynomial
- NP means nondeterministic polynomial
Roughly polynomial (P) represents the upper bound of the cost to verify, and the polynomial characterization says that given a problem with a certain input (e.g. the input can be the number of training examples in ML training set or the number of constraints/conditions in a general problem— e.g. all the places you want to visit on your next trip, given many "wants" in a group)
When the cost is polynomial relative to the input size it means it can only be finitely larger than the input - that's a characteristic of the polynomial which is just a finite sum of powers of x (the input).
When the cost is nondeterministic polynomial, one way to think about it in what is called a nondeterministic Turing machine. The nondeterministic part refers to the "states" that the machines can transition to from any current state. When the transition can happen to more than one state, we say it's non-deterministic— and can imagine it's determined by some probability.
The general assumption is that polynomial (P) is easier than nondeterministic polnomial (NP). This isn't necessarily the case as there can be arbitrarily large finite numbers (making P solutions intractible)
The P vs NP problem is one of the main open problems and generally considered a crank magnet and general confusion. For a good (likely the best) resource see https://scottaaronson.blog/
A problem in P can be solved in polynomial time - the computation required grows relatively slowly as the input size increases. Like sorting a list of numbers.
A problem in NP requires exponential time or greater, but a proposed solution can be verified quickly. For example, checking a completed Sudoku puzzle.
It is believed but unproven that all problems in NP are NOT in P.
A problem in NP can have a (positive) solution verified in polynomial time. That's it. Requiring more than polynomial time to solve isn't part of the definition, and in fact it's an open question whether any problems in NP require more than polynomial time to solve.
Every single problem in P is in NP. What is believed but unproven is that some problems in NP are not in P.
I have never really understood this, from the time it was first introduced to me in my undergraduate education nearly 40 years ago. It seems to boil down to saying "all unsolvable problems are not in the set of solvable problems" which seems like a tautology. I don't get why "P != NP" is considered so profound.
I feel like I have not yet found the proper explanation. Or I'm just too dense to get it.
Not sure you're wanting an explanation, but it comes down more to equivalent algorithms than rigid categories. For example there is a P algo to sort a list of numbers, but not to solve a sudoku (NP). However there is a polynomial algo to check sudoku (spaces ^ 2 if you check every space against every other space for rule violation).
However, the reason all NP algos are part of the same category is because you can solve any problem in NP by switching the problem into another problem in the same category and solving that. For example, you can turn sudoku into a graph coloring problem, which is also NP. You can turn sorting (P) into something like balancing a tree, which is also P.
The major question is "is there any algorithm that would allow us to change some NP problems into P problems, solve it, then use it for the original problem". E.g. could we take graph coloring and turn it into sorting a list of numbers?
So basically, if there is any way to bridge the two, then it might mean every NP problem is actually solvable by a P algorithm, under some transformation. This would be immense because it would completely change the way we solve those algorithms and greatly reduce compute costs.
While this seems far-fetched, realize that there are some problems that seem extremely expensive if done the naiive way, but are actually solvable in P. For example, you _could_ write an exponential sorting algo (try every element in every position), but clever people found a way to make it efficient (P). So its possible we just need the right algo to completely change the landscape of computing.
However, as you say, its almost self-evidently true that P != NP, but has never been proven so (to do so, we need to prove that no such algorithm can exist). But clearly, solving an exponentially complex problem using a O(log n) algo would be remarkable.
To take a concrete example, currently the best algos to exhaustively check a board game like chess or go are exponential (NP). Its easy to verify the winner, but its exponential to enumerate every possible move (e.g. 80^turns states). If we found a polynomial way to solve this (even by converting to something simplified), then it would mean we could exhaustively search chess polynomial to the number of moves (e.g. turns^100). This changes it from "cannot be done in the lifespan of universe" to "its possible with a powerful computer in measurable time". We already use heuristics and estimates to explore the exponential space in efficient time, so if we had a polynomial algo chess, markets, optimization, and other NP problems would be extremely efficient to solve.
In short, P means Polynomial time (i.e. markets can solve computation problems efficiently) and NP means Non-Deterministic Polynomial time (i.e. markets can verify solutions of computation problems efficiently but solutions are found by luck).
If P != NP, it means luck CANNOT be engineered and markets are competitive.
in CS we define a complexity class as a set of problems that have the same growth characteristic. that is for a problem size N, how long does it take in the worst case to find the solution for that problem.
one such class is the Polynomial class, or P, where the time to solution is some fixed exponent of N (like N^2, or 3).
the next big step is NP, which require a polynomial number of nondeterministic steps, whose solution can only be verified in polynomial time. usually solutions to NP problems are exponential in cost with respect to N (like 2^N), but thats not part of their definition.
problems in NP are generally identified by mapping them into a well known problem known to be in NP, where the mapping has to occur in polynomial time.
its an open question as to whether NP as a class can actually be solved in P time, but most people doubt that that is really the case.
If markets were perfectly efficient, entrepreneurship would not exist. An entrepreneur is, at this level, someone who looks for an arbitrage opportunity in correcting a market inefficiency, usually of the form "there is a market for X, X could be provided, but X is not currently provided."
That seems to stretch the meaning of market inefficiency. Is the lack of unlimited free energy an inefficiency in a market? Because an entrepreneur who achieves that is going to do pretty well. I’d say that would be creating value not optimizing market efficiency.
Yeah, and arbitrage. Arbitrage is exploiting the difference in prices of the same asset between two markets. Arbitrage is also risk-free or darn close to it. Entrepreneurship is anything but. Arbitrage is not "gee this product doesn't exist, I'll start a company and invent it and manufacture it and sell it" ...
In perfectly efficient markets, arbitrage gets paid exactly as much as it costs to discover and execute the arbitrage. Entrepreneurs would still exist, they would just be ambivalent between finding new arbitrage opportunities and seeking market-rate employment for their skills in finding arbitrage.
Seems like t is a very critical variable then. For example, you could imagine a particular market is "perfectly" efficient at the moment (however you want to define the boundaries of a particular market), and there is no opportunity. But then a completely unrelated company or university makes a fundemental advancement in materials science that fundamentally changes the landscape. An exogenous shock in other words.
In a certain sense I guess this is why every anti-trust suit fundamentally comes down to defining the market bubble more than anything else.
Ok so the market is perfect... but I exist and have labor to provide. Am I not naturally an "inefficiency" by not participating in the market? Therefore by participating alone, I have a new wrinkle to work from?
Keeping in mind the mistake in the HN title (should be "P != NP"), the interesting part of the abstract is this:
> 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.
The idea that markets are an optimizing algorithm is kinda old already, and well established.
Both papers seem to be jokes about it, based on complete caricatures of competitiveness and efficiency. It's kinda like a recent paper that was posted here proving "general intelligence" impossible while ignoring that humans exist.
Except Maymin 2011 fails to even establish that his narrow definition of "markets are efficient" (specifically, finding a profitable technical analysis) is actually in NP.
The argument is not that you get better prices, it’s that you get accurate prices.
First, this definition has always been circular: what’s the most accurate price? The one the market comes up with. More market, more accuracy!
Second, there is never any reconciliation of the costs society is saddled with in order to chase arbitrarily more accurate prices, the most obvious of which is the massive quantity of fat skimmed off by the financial services sector.
Third, as an index investor, I more or less couldn’t care less. This hyperfixation on accuracy only really matters to people who are actively trading, which is already a fool’s game.
"Third, I propose computational antitrust: the principle that market complexity itself is a competitive safeguard, and that regulators should consider computational difficulty as a design parameter."
This "should" is doing a lot of work here. The paper is mainly about a game-theoretic model allegedly corresponding to real markets, but establishing what regulators ought to do requires far more rationale than mere math. It requires a bridge from "is" to "ought." It reminds me of Hume's warning about this kind of non-sequitur:
"In every system of morality, which I have hitherto met with, I have always remarked, that the author proceeds for some time in the ordinary ways of reasoning, ... ; when all of a sudden I am surprised to find, that instead of the usual copulations of propositions, is, and is not, I meet with no proposition that is not connected with an ought, or an ought not. This change is imperceptible; but is however, of the last consequence."
> 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 yet we’ve clearly observed stable price fixing cartels. Maybe the word “unstable” means too much or the game theory model used doesn’t describe the real world accurately. When theory is contradicted by the evidence, it would be wise to consider the theory is flawed.
Game theory here is applied to two fundamental market theorems. It’s a way to analyze the validity of those assumptions, rather than to build a new model. Empirical evidence to the contrary is expected given mutually inconsistent premises, which is what the author’s results predict. The author has simply used game theory math to disprove economist math.
Nuclear has been in maintenance mode for so long that there are doubts about if anyone could right now detonate one without shitting their pants on account if it would even go off.
I suspect this is a standard mathematical “it is computationally impossible to do this in the general case despite it being entirely feasible in many cases”.
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.
Very interesting. The author claims to have proved that markets can be informationally efficient or competitive, but not both. The implications for policy and regulation are significant.
The author looks credible:
Thank you for sharing this on HN.--
To the mods: The title needs to be edited to replace the equal sign with not-equal.
The implications are not significant..? the real world is messy enough that this will not ever apply.
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 people that didn't understand economics.
the abstract itself explains why there is a problem even if the real world is messy; markets are a social construct
So it pulls exclamation marks. . .angle brackets maybe?
It removes a lot of things when posting, but submitter can edit and put them back.
Most filters are to avoid sensational titles, AFAIK.
UTF8 to the rescue: ≠
Fun fact, pascal uses <> for inequality
Sql too
For the older among us, that's .ne.
You had lower case? In my day...
assuming the typical "spherical market in a vacuum where the agents are maximally rational non-biological utility maximizers"
Well, for better or worse, markets are becoming increasingly dominated by "non-biological utility maximizers" - mostly hft bots, but now also llm-based reasoning agents.
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
A 2010 entry by the same author:
Markets are efficient if and only if P = NP https://arxiv.org/abs/1002.2284
:)
In a P=NP world, it still takes only one uninformed participant to make the market inefficient. I don't think the implication is bidirectionally true unless you assume every single player is rational, infinitely smart, and has access to the same set of information.
Its game theory so perfect play is assumed. Spherical cows and all that
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.
isn't that what they're saying with "not both at the same time"? the papers both have opposite signs, one has != and the other has =
Assuming the original result is correct, isn’t the linked paper simply a corollary?
The newer paper expands on the work of the former.
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 into the paper but I don't see how this follows, except in the most straightforward way. Basically, if everyone uses the same methods to derive price, of course there will be "collusion", or in other words, everyone will have the same price. But this doesn't seem like a result of compute per se, but simply better communication networks and information flows. You could have gotten the same result in medieval England by having everyone post their selling prices on the town square board.
Again, I haven't dug into the paper yet, but it seems like what really matters for firms is "compute"/$ (if the "compute" is an LLM or an assistant that has to go walk the 10 minutes down to the square makes little difference)
Edit: Isn't another implication of this, that increased compute -> collusion imply that increased compute -> communism becomes feasible?
I think this goes to my point above though, the primary problem preventing fully automated luxury communism isn't compute per se, but actually observing the information flows to make it possible. Capitalism famously solves this information problem through the pricing mechanism. So in effect, he's arguing that extra compute makes information gathering more efficient, and at the limit you get perfect information. Which, yeah, I guess so. Assuming everything can be perfectly measured, even theoretically.
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 the DoJ[0]) would actively monitor whether companies were following their pricing recommendations and call up companies that defected. And the software itself used dark patterns to make it easier to simply follow the YieldStar pricing suggestions, rather than set a lower rental rate and be more competitive. The algorithmic pricing I think did allow people to launder their own judgement and simple “trust the process” in a way that in the past would have required knowing complicity with the cartel, but I don’t think it required substantial compute capacity.
(This isn’t a comment on the paper by the way, which I glanced at but did not have the background knowledge to fully comprehend)
[0] See the section labeled “RealPage Uses Multiple Mechanisms To Increase Compliance With Price Recommendations” https://www.federalregister.gov/documents/2026/01/21/2026-01...
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.
I think "cartel" might be the word to look for.
I was always skeptical of the algorithmic cartel argument in that case. Turns out it was just a regular cartel all along.
HN is competitive if and only if != != =
The actual paper’s title is
“Markets are competitive if and only if P ≠ NP”
It’s 2026, people, you don't have to use crude ASCII approximations of mathematical symbols any more.
Unless and until desktop OSes make typing symbols not on the keyboard as easy as iOS or Android, I can't be bothered.
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 “secret price-cutting.”
The thing is that Stigler's insight is far from proven, and indeed, the primary difficulty in collusion is often not the detection of defection. Firms know they're being undercut all the time. The problem is that very often, there is nothing they can do about it. Markets are specifically structured as firm-to-firm transactions, where competing firms have no leverage over what your firm can do or what sort of transactions you can conduct, and as long as this condition holds it doesn't matter if you know that a competitor is fucking you over, you can't do anything about it.
I'd argue that the increase in collusion and anticompetitive behavior lately is because these conditions increasingly don't hold. When you intersperse another party in the transaction, eg. a regulatory agency, permitting body, or exclusive distribution deal, you introduce a leverage point for incumbents to punish competitors who choose to undercut them.
HN materially changed the title to something surprising!
or maybe compute allows simulating a lot of possible cooperation strategies, and arriving at the one maximizing profits for the colluding parties
This feels like it's pointing in the same direction Hayek was already pointing 80 years ago. This paper says that even if we had enough computing power to solve these problems, Hayek's argument was that we still wouldnt have all the information needed to do those calculations in the first place. That information is spread across millions of people, constantly changing, and often only known locally. So even if the computation became easy, getting all the inputs would still be impossible to achieve
I don't have the mathematical chops to really analyze this on my own. Is this a bigger deal than the fact that real world markets already violate all the theoretical assumptions (e.g. unimpeded access to new entrants, perfect information, etc.etc), and so, in practice are never perfectly competitive or efficient?
Defi does a pretty good job regarding unimpeded access in comparison to the more traditional venues. This isn’t just about getting money into the system, but also what instruments you have access to.
The term ‘perfect information’ is a bit of a mirage, and has been shown to be impossible in physics (uncertainty principle).
What really matters is information advantage: Does your inexact expected value function consistently beat others’ calculations in the market. Here, the true value - value really is just a word and is dependent on people - is irrelevant.
the same author 14 years ago. Markets are Efficient if and Only if P = NP and now Markets are competitive if and only if P != NP https://papers.ssrn.com/sol3/papers.cfm?abstract_id=1773169&...
Which would in turn imply that markets cannot be simultaneously efficient and competitive.
This offers little because while P != NP, in most practical cases it doesn't matter.
NP problems gets solved with heuristics every day.
> while P != NP
You don't know that!
In a minute you'll be tellin' folks that those quantum fangdoodles aren't going to revolutionise their stock pickin'!
You do realise that you'll never work in this town again? \s :)
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, and a P algorithm will give you an answer more quickly. (For the same reason I only ever write bubble sorts: I would only write my own at all if I knew that the list would never be bigger than 10. Even then it's only when using the library is too much trouble for some reason.)
But we care about P and NP when the number can potentially be very, very large.
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.
In case P /= NP the gap doesn't necessarily have to be exponential, just superpolynomial (e.g. n^loglogn).
This paper has all the hallmarks of being crackpot with GPT.
[delayed]
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.
I don’t think anyone in the business thinks that the markets are 100% efficient, just that they are sufficiently efficient that beating them is a genuinely hard job requiring heavy, expensive analysis.
The argument structure is interesting, and reminds me a lot of Solomonoff Induction, but constrained into NP by the assumptions. I'm not sure the front half is enough to support the back half of the paper arguing that the current LLM craze means firms are actually running collusion detection algorithms, even unintentionally.
When everyone uses AI to study the same indicators and figures out how the prices move with those indicators they all start investing at the same time and the prices move together. AI silently gets everyone on the same page.
next stage - a single AI which computes the "correct" price that everyone else agrees on, and instantly reprice all financial instruments without trading them, thus not paying transaction costs
I hate to make the worn out AI to RNG comparison, but this kind of simultaneous "collusion" is really like assuming that everyone is using the same RNG seed to make their calls.
Sounds like soviet communist Sci-Fi with a planned economy managed objectively by The Computer.
It’s a great excuse for collusion
This is interesting. Adam Smith said "People of the same trade seldom meet together, even for merriment and diversion, but the conversation ends in a conspiracy against the public, or in some contrivance to raise prices."
The annoying part is that, as the same Adam Smith says, regulating industries would end up enforcing such assemblies, reinforcing the problem... after all, industries can share information via the market itself...
And proposed solutions end up being controversial: employees ownership, open source, paying taxes over stocks ownership... or just hoping that colluders will be broken by a randomly ocurring incumbent...
Would anyone mind explaining what P and NP are?
It's a vast generalization of the cost to verify a problem/solution.
- P means polynomial - NP means nondeterministic polynomial
Roughly polynomial (P) represents the upper bound of the cost to verify, and the polynomial characterization says that given a problem with a certain input (e.g. the input can be the number of training examples in ML training set or the number of constraints/conditions in a general problem— e.g. all the places you want to visit on your next trip, given many "wants" in a group)
When the cost is polynomial relative to the input size it means it can only be finitely larger than the input - that's a characteristic of the polynomial which is just a finite sum of powers of x (the input).
When the cost is nondeterministic polynomial, one way to think about it in what is called a nondeterministic Turing machine. The nondeterministic part refers to the "states" that the machines can transition to from any current state. When the transition can happen to more than one state, we say it's non-deterministic— and can imagine it's determined by some probability.
The general assumption is that polynomial (P) is easier than nondeterministic polnomial (NP). This isn't necessarily the case as there can be arbitrarily large finite numbers (making P solutions intractible)
The P vs NP problem is one of the main open problems and generally considered a crank magnet and general confusion. For a good (likely the best) resource see https://scottaaronson.blog/
P and NP are classes of computational problems.
A problem in P can be solved in polynomial time - the computation required grows relatively slowly as the input size increases. Like sorting a list of numbers.
A problem in NP requires exponential time or greater, but a proposed solution can be verified quickly. For example, checking a completed Sudoku puzzle.
It is believed but unproven that all problems in NP are NOT in P.
A problem in NP can have a (positive) solution verified in polynomial time. That's it. Requiring more than polynomial time to solve isn't part of the definition, and in fact it's an open question whether any problems in NP require more than polynomial time to solve.
Every single problem in P is in NP. What is believed but unproven is that some problems in NP are not in P.
I have never really understood this, from the time it was first introduced to me in my undergraduate education nearly 40 years ago. It seems to boil down to saying "all unsolvable problems are not in the set of solvable problems" which seems like a tautology. I don't get why "P != NP" is considered so profound.
I feel like I have not yet found the proper explanation. Or I'm just too dense to get it.
Not sure you're wanting an explanation, but it comes down more to equivalent algorithms than rigid categories. For example there is a P algo to sort a list of numbers, but not to solve a sudoku (NP). However there is a polynomial algo to check sudoku (spaces ^ 2 if you check every space against every other space for rule violation).
However, the reason all NP algos are part of the same category is because you can solve any problem in NP by switching the problem into another problem in the same category and solving that. For example, you can turn sudoku into a graph coloring problem, which is also NP. You can turn sorting (P) into something like balancing a tree, which is also P.
The major question is "is there any algorithm that would allow us to change some NP problems into P problems, solve it, then use it for the original problem". E.g. could we take graph coloring and turn it into sorting a list of numbers?
So basically, if there is any way to bridge the two, then it might mean every NP problem is actually solvable by a P algorithm, under some transformation. This would be immense because it would completely change the way we solve those algorithms and greatly reduce compute costs.
While this seems far-fetched, realize that there are some problems that seem extremely expensive if done the naiive way, but are actually solvable in P. For example, you _could_ write an exponential sorting algo (try every element in every position), but clever people found a way to make it efficient (P). So its possible we just need the right algo to completely change the landscape of computing.
However, as you say, its almost self-evidently true that P != NP, but has never been proven so (to do so, we need to prove that no such algorithm can exist). But clearly, solving an exponentially complex problem using a O(log n) algo would be remarkable.
To take a concrete example, currently the best algos to exhaustively check a board game like chess or go are exponential (NP). Its easy to verify the winner, but its exponential to enumerate every possible move (e.g. 80^turns states). If we found a polynomial way to solve this (even by converting to something simplified), then it would mean we could exhaustively search chess polynomial to the number of moves (e.g. turns^100). This changes it from "cannot be done in the lifespan of universe" to "its possible with a powerful computer in measurable time". We already use heuristics and estimates to explore the exponential space in efficient time, so if we had a polynomial algo chess, markets, optimization, and other NP problems would be extremely efficient to solve.
NP contains P. You're thinking of NP-hard problems.
I have taken algorithms courses.
This video explains in detail: https://www.youtube.com/watch?v=YX40hbAHx3s
In short, P means Polynomial time (i.e. markets can solve computation problems efficiently) and NP means Non-Deterministic Polynomial time (i.e. markets can verify solutions of computation problems efficiently but solutions are found by luck).
If P != NP, it means luck CANNOT be engineered and markets are competitive.
Wikipedia is a good source on this
P complexity class
https://en.wikipedia.org/wiki/P_(complexity)
NP complexity class
https://en.wikipedia.org/wiki/NP_(complexity)
P vs NP question
https://en.wikipedia.org/wiki/P_versus_NP_problem
well obviously N=1
in CS we define a complexity class as a set of problems that have the same growth characteristic. that is for a problem size N, how long does it take in the worst case to find the solution for that problem.
one such class is the Polynomial class, or P, where the time to solution is some fixed exponent of N (like N^2, or 3).
the next big step is NP, which require a polynomial number of nondeterministic steps, whose solution can only be verified in polynomial time. usually solutions to NP problems are exponential in cost with respect to N (like 2^N), but thats not part of their definition.
problems in NP are generally identified by mapping them into a well known problem known to be in NP, where the mapping has to occur in polynomial time.
its an open question as to whether NP as a class can actually be solved in P time, but most people doubt that that is really the case.
If markets were perfectly efficient, entrepreneurship would not exist. An entrepreneur is, at this level, someone who looks for an arbitrage opportunity in correcting a market inefficiency, usually of the form "there is a market for X, X could be provided, but X is not currently provided."
That seems to stretch the meaning of market inefficiency. Is the lack of unlimited free energy an inefficiency in a market? Because an entrepreneur who achieves that is going to do pretty well. I’d say that would be creating value not optimizing market efficiency.
Yeah, and arbitrage. Arbitrage is exploiting the difference in prices of the same asset between two markets. Arbitrage is also risk-free or darn close to it. Entrepreneurship is anything but. Arbitrage is not "gee this product doesn't exist, I'll start a company and invent it and manufacture it and sell it" ...
How would creating unlimited free energy allow an entrepreneur to do pretty well? It it's free, there's no money to be made.
In perfectly efficient markets, arbitrage gets paid exactly as much as it costs to discover and execute the arbitrage. Entrepreneurs would still exist, they would just be ambivalent between finding new arbitrage opportunities and seeking market-rate employment for their skills in finding arbitrage.
Seems like t is a very critical variable then. For example, you could imagine a particular market is "perfectly" efficient at the moment (however you want to define the boundaries of a particular market), and there is no opportunity. But then a completely unrelated company or university makes a fundemental advancement in materials science that fundamentally changes the landscape. An exogenous shock in other words.
In a certain sense I guess this is why every anti-trust suit fundamentally comes down to defining the market bubble more than anything else.
Ok so the market is perfect... but I exist and have labor to provide. Am I not naturally an "inefficiency" by not participating in the market? Therefore by participating alone, I have a new wrinkle to work from?
Keeping in mind the mistake in the HN title (should be "P != NP"), the interesting part of the abstract is this:
> 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.
(Note that Maymin is the author of both papers.)
Yet neither paper seems to eliminate the case of markets being neither. So both titles are incorrect.
Yeah using time complexity for computers to describe markets is simultaneously awesome and stupid.
The idea that markets are an optimizing algorithm is kinda old already, and well established.
Both papers seem to be jokes about it, based on complete caricatures of competitiveness and efficiency. It's kinda like a recent paper that was posted here proving "general intelligence" impossible while ignoring that humans exist.
Except Maymin 2011 fails to even establish that his narrow definition of "markets are efficient" (specifically, finding a profitable technical analysis) is actually in NP.
It's time to forbid bots and HFT.
Want to buy/sell a stock?
Humans need to manually submit in the system.
Why? Don't you prefer getting better prices when you want to go buy a stock?
I prefer a better price delta between buy and sell, which is blind to price hikes across the board.
That's exactly what "better prices" means...
If I get a better price when I buy then someone else gets a better price when they buy too. (S + k) - (B + k) = S - B.
The argument is not that you get better prices, it’s that you get accurate prices.
First, this definition has always been circular: what’s the most accurate price? The one the market comes up with. More market, more accuracy!
Second, there is never any reconciliation of the costs society is saddled with in order to chase arbitrarily more accurate prices, the most obvious of which is the massive quantity of fat skimmed off by the financial services sector.
Third, as an index investor, I more or less couldn’t care less. This hyperfixation on accuracy only really matters to people who are actively trading, which is already a fool’s game.
"Third, I propose computational antitrust: the principle that market complexity itself is a competitive safeguard, and that regulators should consider computational difficulty as a design parameter."
This "should" is doing a lot of work here. The paper is mainly about a game-theoretic model allegedly corresponding to real markets, but establishing what regulators ought to do requires far more rationale than mere math. It requires a bridge from "is" to "ought." It reminds me of Hume's warning about this kind of non-sequitur:
"In every system of morality, which I have hitherto met with, I have always remarked, that the author proceeds for some time in the ordinary ways of reasoning, ... ; when all of a sudden I am surprised to find, that instead of the usual copulations of propositions, is, and is not, I meet with no proposition that is not connected with an ought, or an ought not. This change is imperceptible; but is however, of the last consequence."
> 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 yet we’ve clearly observed stable price fixing cartels. Maybe the word “unstable” means too much or the game theory model used doesn’t describe the real world accurately. When theory is contradicted by the evidence, it would be wise to consider the theory is flawed.
Game theory here is applied to two fundamental market theorems. It’s a way to analyze the validity of those assumptions, rather than to build a new model. Empirical evidence to the contrary is expected given mutually inconsistent premises, which is what the author’s results predict. The author has simply used game theory math to disprove economist math.
where do nuclear weapons fit in? do they make markets more/less efficient/competitive?
Way above my pay grade. I’m not an expert in game theory, economics, warfare, or nuclear proliferation. :)
Where do conventional weapons fit it?
Nuclear has been in maintenance mode for so long that there are doubts about if anyone could right now detonate one without shitting their pants on account if it would even go off.
I suspect this is a standard mathematical “it is computationally impossible to do this in the general case despite it being entirely feasible in many cases”.
Or maybe the markets are actually proof that P = NP :^)
Or, P=NP
This gave me shivers