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)
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.
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?
You absolutely can react, but in general, in a functioning competitive market, you can not alter your competitors' actions.
Examples of the former: cutting prices yourself; increasing product quality; differentiating yourself; spending more on advertising to get the word out about your product.
Examples of the latter: crafting exclusive deals with your distributors to prevent your competitors from getting shelf space; politically influencing regulatory bodies to declare your competitors' existence illegal; making direct agreements with the leadership of opposing firms to not drop prices or hike wages; assassinating, extorting, or kidnapping rival business leaders.
Basically it comes down to "control yourself, because you cannot control others". In a functioning market, you have no control over what rival firms offer. Your only legal reaction to competition is to improve your own offering until it is the best it can be. In pathological markets where the assumption is (as in the paper) that you can punish rivals for not colluding, you actively make your competitor's offering worse.
Those pathological markets exist today, but if you're analyzing markets economically, your root assumption should not be that pathology is normal and only the lack of information keeps it in check, it should be that information is abundant and it is the lack of ability that keeps it in check.
It's pretty easy on Linux with the compose key. To get "≠", you just hit compose, then "/", then "=". That's actually the same number of keystrokes as "!=" (since "!" requires the shift key).
For whatever reason, the OS documentation lacks a list of allowed compose key sequences. But they are intuitive enough that you can find many of them through experimentation. For example:
> I don't see how this follows, except in the most straightforward way.
A more capable actor can anticipate the actions of other participants to a greater degree. Imagine that all sellers are such actors. Consider that collusion happens (and is bad) because it enables sellers to extract much higher prices than the market would otherwise set. When all sellers are such "hyper rational" actors they can act cooperatively to maximize their profits without the need to explicitly coordinate in secret. The same end result without the illegal step sure feels like an end run around the spirit of the law.
> Edit: Isn't another implication of this, that increased compute -> collusion imply that increased compute -> communism becomes feasible?
That depends on what you think the problem that communism faced was. AI increases our ability to centrally plan but it probably doesn't do much in and of itself to combat various forms of corruption.
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.
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 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.
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.
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.
"Ahkchually the paperclip maximizer isn't maximizing [human] utility, just a dumb metric" isn't a particularly useful observation to make in the context of the world being gradually consumed by an army of nanobots.
I'm thinking of an earlier time when computers ran on "facts and logic" and you could probably stop the machine by giving it a logical conundrum. Vibes-based systems are a lot more resistant to this, but can still be distracted.
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 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).
I always thought of supply and demand as more defining a limit that the price approaches as the number of transactions and the size of the market approach infinity, barring structural obstacles or persistent information asymmetry to prevent it than as something that was supposed to happen immediately on any given transaction.
Businesses generally follow the rule "price is set to whatever the market will bear". Which is just an indirect way of setting price by supply and demand.
There are many ways that free and competitive markets can fail other than behavioural economics! Monopoly, informational asymmetry, externalities… All of these are plausibly pervasive.
Knowledge accumulation seems to have cyclical patterns where general observations are condensed into "laws", and common wisdom is to treat these as unassailable truths. As exceptions and contradictions are found, the popular wisdom is to entirely dismiss the overwhelming universal conformity with the earlier principles because it sounds smart to common people. A lot of normal people see the basic problems with most methodological maxims but are led to believe that the maxim is truth. It takes a podcaster with a "study" to then "debunk" the "myth" they were yesterday defending as unimpeachable. People are generally not well informed enough to know anything and the podcaster class is the worst imaginable vector for knowledge dissemination or popularization. Just clickbait garbage monkeys with foreign money and vicious antisocial tendencies.
Economics is one of the scientific sore spots for liberal ideology. If you are liberal and mostly swim in liberal circles, you probably believe that economics is mostly bunk pseudoscience. Akin to conservatives and climate change
To be fair, macroeconomics can hardly be called science, though. It is incredibly hard to falsify a lot of the theories given the lack of possibilities for experimentation. It is far closer to philosophy than to any of the even remotely hard sciences.
Nothing to do with ideology, but with the nature of the field. Take epidemiological research in the areas of food and medicine: incredibly hard and expensive to get right and even then with often tenuous results. Now try doing that with ridiculously heterogeneous nations influenced by potentially almost everything on the planet.
It's a small miracle that economists manage to get some useful insights out of the data, but we should definitely be aware of how weakly most of them are supported (don't start talking about "error bars" with economists).
An argument of the last couple of decades is that videogames have built incredible labs for macroeconomic experimentation. So far mostly what we learn are failure cases (mudflation, being such a big learning from videogames that the term itself is named after a type of them), but we are learning things (some of them exploitative, but that's a different ethical question).
You are overstating this. Mudflation does not transfer to the real world well, if at all. Very few skill-capped bits of DLC for real world activities.
These games do not include many of the complexities of the real world and can thus provide few insights that generalize to the real world on a macroeconomic level. They are toy universes. I'm not saying they are useless, far from it, but they are not "incredible labs for macroeconomic experimentation".
Try determining the effect of raising the central bank interest rate within a game of your choice. Or changing the minimum wage. Or the effects of investing in education. Etc.
They are incredible compared to "no labs at all" and "no way to run experiments" as the above poster lamented.
Mudflation aka hyperinflation aka situations where "the money printer goes brr too fast" have happened in the real world. Sometimes at "extremely" small scale (for macroeconomics) such as company town scrip, but they've happened and affected real people's lives.
But also, if Bitcoin is real then videogame economies are very real. You can trade USD for most in-game currencies. Sometimes directly in game as micro-transactions today ("diamond" or "platinum" middle funging currencies that convert to other game currencies), sometimes on trading platforms that are certainly against game terms of service and possibly illegal in some states, but that doesn't really stop them existing or people living in low wage countries making ends meet by grinding game currencies to sell for "realer" ones.
(Mudflation is also the answer to the why the book I read of "Ready Player One" was better than the one the author wrote because it seemed obvious the economy in the book was a textbook mudflationary one and much of the dystopia outside of its central game could easily be explained by how much of its economy was tied into its in game mudflationary currency. I appreciated that Hank Green's book "A Beautifully Foolish Endeavor" did a better job of doing that on purpose.)
> They are toy universes.
So are most experiments, fundamentally. You model the real world as best you can. You do what you can to eliminate variables. You learn from your experiment and you improve your model. You can't test the entire universe all at once, that's too many variables, you find the interesting toys that seem to look enough like our current understanding of our universe and then you play them until you break them (assert either the null hypothesis or the alternative hypothesis). Repeat until done.
Your examples seem easy to build toy universes for. The Animal Crossing series has decades of "research" in the effects of raising a central bank interest rate. (Look for Tom Nook memes, they alone are a modern study of macroeconomics and teenagers' direct relationships with them.) Many MMOs have "trades" and "crafts" that need to balance a minimum wage to get players interested and/or invested in them versus opportunity costs in other systems in the game. Funding Education is a similar problem explored in various RPG mechanics by sometimes direct analogies such as investments into player attributes and skill levels and skill trees.
And so on and so forth. The boundary between "real" and "virtual" economics seems nearly nonexistent, they are the same thing (and currency always wants to flow between them). In this case the map seems to be the territory. In this case the analogy seems to be the real thing. Because people are involved and people are ultimately irrational, but start to do really interesting economic things the more people you put in the same "place", whether virtual or real. Which is what macroeconomics has always been about.
> They are incredible compared to "no labs at all"
That is a nonsensically low bar. You basically destroy the entire scale by labeling the bare minimum as such.
> Mudflation aka hyperinflation aka situations where "the money printer goes brr too fast"
That is not what mudflation is at all.
>> They are toy universes.
> So are most experiments, fundamentally.
Nonsense. Most experiments are performed on actual real world stuff rather than an analogue of it: something like looking at how actual food affects actual humans rather than what happens when feeding virtual characters virtual apples. Limited or narrowly scoped real world experiments != toy universe experiments.
An inbetween category would be (human) drug experiments on mice, which are real world and where the results still don't generalize to humans often.
> Your examples seem easy to build toy universes for.
Yeah, no shit. My point was that those are horribly incomplete and don't generalize:
"These games do not include many of the complexities of the real world and can thus provide few insights that generalize to the real world on a macroeconomic level."
Your examples are incredibly inadequate compared to the real world and have exactly 0 predictive power in said real world. In recent decades, the entire field of economy has been dumbfounded by the (lack of) effects of quantitative easing and the central interest rate on inflation in the USA and the EU. Maybe try telling them that they should look into the economy of Animal Crossing /s.
>> Mudflation aka hyperinflation aka situations where "the money printer goes brr too fast"
> That is not what mudflation is at all.
No, I think it is more that you are used to the more straight-jacketed post-EverQuest form of the term rather than the original circumstances that gave rise to the term in the first place. MUDs didn't have "expansion packs" or DLC. The original form of the term had more to do with infinitely printable currency ("grindable" drops from game spawned enemies) and its effects in trying to balance a larger economy. EverQuest did help to popularize the term in the way its expansions packs particularly badly handled that inflation, but those expansion pack balancing woes were never the cause of that inflation, only a symptom. The cause was (and has always been) "grinding" and "grinding mindset".
> Maybe try telling them that they should look into the economy of Animal Crossing
That is exactly what I'm trying to do. We have some good science from videogames but not enough of it. Dismissing videogame economies as "toy universes" that don't matter doesn't help science. Animal Crossing has inadvertently demonstrated some of the symptoms of that economic question. Imagine if a game was designed to intentionally simulate that as a lab experiment.
I don't think we're going to agree on that, but I think on the spectrum of "macroeconomics isn't a science because it has no laboratories and isn't reproducible in experiments" to "macroeconomics is a science but its laboratories are videogames and we have under studied them and especially aren't building enough reproducible studies", I am happy to be on the side of it that sees hope in better macroeconomic science even if it isn't currently taken seriously enough.
"Hyperinflation is a very high and typically accelerating inflation."
"Mudflation is a term for the type of inflation found in MUDs (Multi User Dungeon) games. MMORPGs, these days. It's caused by fluctuations in the game economy, caused by player exploits or poorly designed patches. Mudflation almost always kicks in after a major patch or an expansion, when new, better quality items are added to the game economy. These generally have the effect of greatly lowering the value of all pre-existing items."
2.
> Dismissing videogame economies as "toy universes" that don't matter doesn't help science.
Straw man. I never said they did not matter, nor did I say that research of them isn't useful. I said that research is severely limited due to the lack of complexity and you have provided nothing to disprove that.
I would argue that your way of communicating about this is actually a bit of evidence that this kind of research is probably going to be detrimental to policy making: Overestimating the value and use of such research is exactly the same thing that happens with traditional macroeconomic research, with policy makers and the general public treating the theories and hypotheses like laws of nature.
> > They are incredible compared to "no labs at all"
> That is a nonsensically low bar. You basically destroy the entire scale by labeling the bare minimum as such.
Ah, yeah, I wasn't using it for "scale". "incredible" also often connotes "in ways that you wouldn't believe". Your long posts disputing me are somewhat validation that I used the right turn of phrase there.
In fact that there's both a liberal and conservative economics ideology, and what could form a scientific discipline in between is unfortunately cornered and sorely lacking visibility.
I see what you mean, but I'd disagree with the idea that there's “precisely zero ideological, ie political-economic, difference”.
That's true that since at least Clinton, the Democrats as a political party have mostly embraced the business-friendly view that is also the conservatives' position on the subject.
But the Democrat's leadership are only a (very) imperfect mirror of their electorate and of the intellectual left, and there is definitely a significant set of left-wing economists (Polanyi, Stiglitz, Piketti to name a few of the most prominent, in chronological order).
I was being deliberately facetious, I suppose, but because of our campaign finance problems any policy of major economic import has coordinated bipartisan pressure.
I've been picking up a different feeling that economics is sort of in a pre-calculus moment that conservatives/libertarians and liberals/progressives have sort of been building two different sciences of economics and are missing the "calculus" to reunite them (or at least choose the winner between them).
I mention calculus specifically because it does feel like more of the progressive movements in economics are focused on rate of change rather than point in time. I personally often tend to get into electrical circuit analogies that current/resistance/impedance are more useful than steady state voltage. I find I especially bring these metaphors up a lot when discussing cryptocurrencies (and why I distrust them: inflation/deflation is the wrong axis, in my opinion, some inflation is a useful sign of "impedance" in the circuit, the trick to a healthy economy is not "deflationary" [most of real world history states that the deflationary economies are the worst to live in] but carefully managing the rate of change of inflation).
That progressive science of economics is happening, slowly (this paper seems relevant), but so much of conservative discussions get trapped in (misreads of) Adam Smith still. From a progressive point of view it does seem easy to dismiss conservative views of economics as bunk pseudoscience if they begin and nearly always end with Adam Smith, ignore some of Adam Smith's own warnings (for instance, relevant to above conversation: Adam Smith was also often the first to admit that the "free market" is an ideal/a model and unlikely to ever be a reality because humans are messy and ultimately irrational as individuals), and also ignore centuries worth of work since then, especially a lot of the "pre-calculus" stuff.
Well yes, they're the very premise we've structured our entire economy around. How else could an economic process operate without being attacked by the state? But this is also why our market behaves so irrationally—these concepts have very obvious predictive limits that investors are struggling to grapple with and our politicians (and largely our electorate tbf) have blind faith in
The vast majority of cash transactions are fired by a computer model so the implication are significant. It goes a long way towards explaining why increasingly financialized countries aren't experiencing noticeable real world improvement while also becoming increasingly extractive.
Hmm. I am not so sure about that statement. There are many models at play in the market, not one model. What mechanistic patterns are driving those models that are falsified by this paper and lead to the outcome of increasingly extractive/stagnating economies?
Neoclassical economics is based around the idea that markets are 100% efficient. If they are only 99% efficient the whole thing falls apart, because the standard defense of neoclassicals against exponentially growing defects in the economy is that they never happen in the first place. The moment you permit a 1% defect rate, the cascade starts and it is only a matter of time for things to go wrong.
> 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.
Simple resolution: the market isn’t maximally efficient at all
information discovery but it is optimally efficient as far as is practical. The economist math still works.
I buy that markets are like a traveling salesman problem. “Impossible” in the general case, but good enough could algorithms exist. Where’s the economist formulation of that algorithm? What are the policy implications that fall out of that?
I admit I’m not particularly well versed in this space, but I’ve never come across that formulation, only the “pure” one the original researcher says is internally inconsistent. I don’t necessarily buy “it’s close enough it doesn’t matter” given what I perceive as many notable exceptions.
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”.
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.
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."
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.
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" ...
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?
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.
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.
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.
> just that they are sufficiently efficient that beating them is a genuinely hard job requiring heavy, expensive analysis
No expensive analysis is needed. Beating them just requires (1) having disproportionate capital to others, and (2) having disproportionate control (and therefore know in advance) whatever the markets are pricing.
It helps that there are enough believers (in the religious/cult sense) that markets are 100% efficient, that they will deny that any of that is happening - even while they lose their shirts to those who are doing the market manipulation.
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.
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.
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.
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 algorithms. For example there is a P algo to sort a list of numbers, but not to solve a sudoku.
However, the reason they are part of the same category is because you can solve any problem in P / 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.
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".
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. This would be immense because it would completely change the way we solve those algorithms and greatly reduce compute costs.
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.
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.
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/
Sorry, what's the significance of finiteness? The upper bound on an NFA is exponential steps of state transition splitting, thus P ⊆ NP ⊆ EXP, the class of exponential time algorithms.
the finiteness, in a sense, makes it non-exponential.
it boils down to the core characterstic of polynomials (equivalently "algebraic") of being finite series (compare with formal power series that don't have this limitation) of constant powers. Hence, given an input, you can get something that is a polynomial of that input, that makes it a finite sum of constant! powers of that input.
The sum is finite (vs formal power series which can be infinite)
The powers are constant (this is what makes it non-exponential)
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.
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.
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.
> First, this definition has always been circular: what’s the most accurate price? The one the market comes up with. More market, more accuracy!
Market makers and HFT don't determine price: price is usually purely determined by the net inflows and outflows as decided by humans. MMs just smooth it out over time so everyone gets good pricing at the time and in the size they want it.
> Second, there is never any reconciliation of the costs society is saddled with in order to chase arbitrarily more accurate prices
By definition market makers are earning a fraction of the price improvement they provide, ergo the costs to society have to be less that the benefits for better pricing for the companies to stay in business!
> Third, as an index investor, I more or less couldn’t care less
As an index investor you should absolutely care! How do you think you are able to buy into the fund at a reasonable price? And then how do you think the fund is able to rebalance without transaction costs destroying performance long-term?
It feels like you're intentionally omitting parts of what I said to make a point, and that I have no hope of correcting your world view, so just gonna clarify for any onlookers then stop arguing further.
> > price is usually purely determined by the net inflows and outflows as decided by humans.
> "as decided by humans", more than 90% of trades are led by bots, so no, price is not being determined by humans.
You skipped past the "MMs just smooth it out over time so everyone gets good pricing at the time and in the size they want it" right afterwards which exactly explains why most trading is between bots! Person A wants to buy 10 shares of Y at time T1, Person B wants to sell 20 shares of Y at time T2, Person C wants to buy 10 shares of Y at time T3. Those are all at different times, therefore bots have to take the other side of each trade, then trade with each other to smooth out prices in between each point.
> In fact, we have seen time and again how some weird companies get a huge inflow of purchases simply because of bots misinterpreting news articles.
I actually clearly see this happening more with humans than with bots. Can you think of a single example attributed to bots? A bot that can misinterpret a news article and lose money is fixed and/or disabled forever. There is no shortage of dumb humans willing to lose money due to a lack of literacy.
> By definition market makers are earning a fraction of the price improvement they provide
By definition, they’re making in aggregate essentially whatever the difference was between the “misprice” and the “true price”, assuming sufficient belief in both of these things. One of the parties in the hypothetically mispriced trade is bearing the loss. Their cut had to come from somewhere.
> As an index investor you should absolutely care! How do you think you are able to buy into the fund at a reasonable price?
You are relying on an interpretation of “reasonable” to intuitively mean “cheap” when in reality it means “accurate” in this context.
As an index investor, as long as it is accurate enough I don’t care. Any mispricing of assets up and down will come out in the wash.
Index funds existed well before HFTs were endemic. I have seen zero evidence that HFTs have caused index funds to net more of the gains from their underlying indexes.
"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."
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...
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
But you can just give computers to each of those millions of people and propagate the information, instead of having less reliable humans doing it? That's kind of what's already happening.
The problem isn't transmitting information, it's how the knowledge is created. Some information only exists in peoples head until they act on it. Sometimes they don't even know it themselves until they're forced to make a decision.
Problem of course is that a lot of this information is junk even at scale, which is how you get people "deciding" to pollute, destroy their own health, start wars, etc.
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.
163 comments
[ 2.8 ms ] story [ 39.2 ms ] thread"Markets are competitive if and only if P != NP"
Seems that HN's auto-headline rewriting in this case has made a critical error :)
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...
> 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.
Examples of the former: cutting prices yourself; increasing product quality; differentiating yourself; spending more on advertising to get the word out about your product.
Examples of the latter: crafting exclusive deals with your distributors to prevent your competitors from getting shelf space; politically influencing regulatory bodies to declare your competitors' existence illegal; making direct agreements with the leadership of opposing firms to not drop prices or hike wages; assassinating, extorting, or kidnapping rival business leaders.
Basically it comes down to "control yourself, because you cannot control others". In a functioning market, you have no control over what rival firms offer. Your only legal reaction to competition is to improve your own offering until it is the best it can be. In pathological markets where the assumption is (as in the paper) that you can punish rivals for not colluding, you actively make your competitor's offering worse.
Those pathological markets exist today, but if you're analyzing markets economically, your root assumption should not be that pathology is normal and only the lack of information keeps it in check, it should be that information is abundant and it is the lack of ability that keeps it in check.
“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.
For whatever reason, the OS documentation lacks a list of allowed compose key sequences. But they are intuitive enough that you can find many of them through experimentation. For example:
Musical sharp ("♯"): compose + "#" + "#".
Interrobang ("‽"): compose + "!" + "?".
Letter "ñ" as in "jalapeño": compose + "n" + "~".
Copyright ("ⓒ"): compose + "(" + c + ")".
Oops, I got one wrong.
Copyright("©"): compose + "c" + "o".
The one I had is bigger: Ⓒ vs. ©.
I'm eagerly awaiting the day someone proves that P != NP and HN edits the title of the announcement post in this exact same way.
A more capable actor can anticipate the actions of other participants to a greater degree. Imagine that all sellers are such actors. Consider that collusion happens (and is bad) because it enables sellers to extract much higher prices than the market would otherwise set. When all sellers are such "hyper rational" actors they can act cooperatively to maximize their profits without the need to explicitly coordinate in secret. The same end result without the illegal step sure feels like an end run around the spirit of the law.
> Edit: Isn't another implication of this, that increased compute -> collusion imply that increased compute -> communism becomes feasible?
That depends on what you think the problem that communism faced was. AI increases our ability to centrally plan but it probably doesn't do much in and of itself to combat various forms of corruption.
Software trying to be smart always runs that risk.
> 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.)
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.
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.
BASIC[1] came out in 1964, and Pascal[2] came out in 1970.
---
[1] https://en.wikipedia.org/wiki/Dartmouth_BASIC
[2] https://en.wikipedia.org/wiki/Pascal_(programming_language)
Most filters are to avoid sensational titles, AFAIK.
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.
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.
Nothing to do with ideology, but with the nature of the field. Take epidemiological research in the areas of food and medicine: incredibly hard and expensive to get right and even then with often tenuous results. Now try doing that with ridiculously heterogeneous nations influenced by potentially almost everything on the planet.
It's a small miracle that economists manage to get some useful insights out of the data, but we should definitely be aware of how weakly most of them are supported (don't start talking about "error bars" with economists).
These games do not include many of the complexities of the real world and can thus provide few insights that generalize to the real world on a macroeconomic level. They are toy universes. I'm not saying they are useless, far from it, but they are not "incredible labs for macroeconomic experimentation".
Try determining the effect of raising the central bank interest rate within a game of your choice. Or changing the minimum wage. Or the effects of investing in education. Etc.
Mudflation aka hyperinflation aka situations where "the money printer goes brr too fast" have happened in the real world. Sometimes at "extremely" small scale (for macroeconomics) such as company town scrip, but they've happened and affected real people's lives.
But also, if Bitcoin is real then videogame economies are very real. You can trade USD for most in-game currencies. Sometimes directly in game as micro-transactions today ("diamond" or "platinum" middle funging currencies that convert to other game currencies), sometimes on trading platforms that are certainly against game terms of service and possibly illegal in some states, but that doesn't really stop them existing or people living in low wage countries making ends meet by grinding game currencies to sell for "realer" ones.
(Mudflation is also the answer to the why the book I read of "Ready Player One" was better than the one the author wrote because it seemed obvious the economy in the book was a textbook mudflationary one and much of the dystopia outside of its central game could easily be explained by how much of its economy was tied into its in game mudflationary currency. I appreciated that Hank Green's book "A Beautifully Foolish Endeavor" did a better job of doing that on purpose.)
> They are toy universes.
So are most experiments, fundamentally. You model the real world as best you can. You do what you can to eliminate variables. You learn from your experiment and you improve your model. You can't test the entire universe all at once, that's too many variables, you find the interesting toys that seem to look enough like our current understanding of our universe and then you play them until you break them (assert either the null hypothesis or the alternative hypothesis). Repeat until done.
Your examples seem easy to build toy universes for. The Animal Crossing series has decades of "research" in the effects of raising a central bank interest rate. (Look for Tom Nook memes, they alone are a modern study of macroeconomics and teenagers' direct relationships with them.) Many MMOs have "trades" and "crafts" that need to balance a minimum wage to get players interested and/or invested in them versus opportunity costs in other systems in the game. Funding Education is a similar problem explored in various RPG mechanics by sometimes direct analogies such as investments into player attributes and skill levels and skill trees.
And so on and so forth. The boundary between "real" and "virtual" economics seems nearly nonexistent, they are the same thing (and currency always wants to flow between them). In this case the map seems to be the territory. In this case the analogy seems to be the real thing. Because people are involved and people are ultimately irrational, but start to do really interesting economic things the more people you put in the same "place", whether virtual or real. Which is what macroeconomics has always been about.
That is a nonsensically low bar. You basically destroy the entire scale by labeling the bare minimum as such.
> Mudflation aka hyperinflation aka situations where "the money printer goes brr too fast"
That is not what mudflation is at all.
>> They are toy universes.
> So are most experiments, fundamentally.
Nonsense. Most experiments are performed on actual real world stuff rather than an analogue of it: something like looking at how actual food affects actual humans rather than what happens when feeding virtual characters virtual apples. Limited or narrowly scoped real world experiments != toy universe experiments.
An inbetween category would be (human) drug experiments on mice, which are real world and where the results still don't generalize to humans often.
> Your examples seem easy to build toy universes for.
Yeah, no shit. My point was that those are horribly incomplete and don't generalize: "These games do not include many of the complexities of the real world and can thus provide few insights that generalize to the real world on a macroeconomic level."
Your examples are incredibly inadequate compared to the real world and have exactly 0 predictive power in said real world. In recent decades, the entire field of economy has been dumbfounded by the (lack of) effects of quantitative easing and the central interest rate on inflation in the USA and the EU. Maybe try telling them that they should look into the economy of Animal Crossing /s.
> That is not what mudflation is at all.
No, I think it is more that you are used to the more straight-jacketed post-EverQuest form of the term rather than the original circumstances that gave rise to the term in the first place. MUDs didn't have "expansion packs" or DLC. The original form of the term had more to do with infinitely printable currency ("grindable" drops from game spawned enemies) and its effects in trying to balance a larger economy. EverQuest did help to popularize the term in the way its expansions packs particularly badly handled that inflation, but those expansion pack balancing woes were never the cause of that inflation, only a symptom. The cause was (and has always been) "grinding" and "grinding mindset".
> Maybe try telling them that they should look into the economy of Animal Crossing
That is exactly what I'm trying to do. We have some good science from videogames but not enough of it. Dismissing videogame economies as "toy universes" that don't matter doesn't help science. Animal Crossing has inadvertently demonstrated some of the symptoms of that economic question. Imagine if a game was designed to intentionally simulate that as a lab experiment.
I don't think we're going to agree on that, but I think on the spectrum of "macroeconomics isn't a science because it has no laboratories and isn't reproducible in experiments" to "macroeconomics is a science but its laboratories are videogames and we have under studied them and especially aren't building enough reproducible studies", I am happy to be on the side of it that sees hope in better macroeconomic science even if it isn't currently taken seriously enough.
"Hyperinflation is a very high and typically accelerating inflation."
"Mudflation is a term for the type of inflation found in MUDs (Multi User Dungeon) games. MMORPGs, these days. It's caused by fluctuations in the game economy, caused by player exploits or poorly designed patches. Mudflation almost always kicks in after a major patch or an expansion, when new, better quality items are added to the game economy. These generally have the effect of greatly lowering the value of all pre-existing items."
2.
> Dismissing videogame economies as "toy universes" that don't matter doesn't help science.
Straw man. I never said they did not matter, nor did I say that research of them isn't useful. I said that research is severely limited due to the lack of complexity and you have provided nothing to disprove that.
I would argue that your way of communicating about this is actually a bit of evidence that this kind of research is probably going to be detrimental to policy making: Overestimating the value and use of such research is exactly the same thing that happens with traditional macroeconomic research, with policy makers and the general public treating the theories and hypotheses like laws of nature.
> That is a nonsensically low bar. You basically destroy the entire scale by labeling the bare minimum as such.
Ah, yeah, I wasn't using it for "scale". "incredible" also often connotes "in ways that you wouldn't believe". Your long posts disputing me are somewhat validation that I used the right turn of phrase there.
"This kid is good at hockey in ways you wouldn't believe."
Which of these sentences means the same as the above?
A. This kid is incredibly good at hockey.
B. This kid is surprisingly good at hockey.
> Your long posts disputing me are somewhat validation that I used the right turn of phrase there.
I think you've just invented a new fallacy.
That's true that since at least Clinton, the Democrats as a political party have mostly embraced the business-friendly view that is also the conservatives' position on the subject.
But the Democrat's leadership are only a (very) imperfect mirror of their electorate and of the intellectual left, and there is definitely a significant set of left-wing economists (Polanyi, Stiglitz, Piketti to name a few of the most prominent, in chronological order).
I was being deliberately facetious, I suppose, but because of our campaign finance problems any policy of major economic import has coordinated bipartisan pressure.
I mention calculus specifically because it does feel like more of the progressive movements in economics are focused on rate of change rather than point in time. I personally often tend to get into electrical circuit analogies that current/resistance/impedance are more useful than steady state voltage. I find I especially bring these metaphors up a lot when discussing cryptocurrencies (and why I distrust them: inflation/deflation is the wrong axis, in my opinion, some inflation is a useful sign of "impedance" in the circuit, the trick to a healthy economy is not "deflationary" [most of real world history states that the deflationary economies are the worst to live in] but carefully managing the rate of change of inflation).
That progressive science of economics is happening, slowly (this paper seems relevant), but so much of conservative discussions get trapped in (misreads of) Adam Smith still. From a progressive point of view it does seem easy to dismiss conservative views of economics as bunk pseudoscience if they begin and nearly always end with Adam Smith, ignore some of Adam Smith's own warnings (for instance, relevant to above conversation: Adam Smith was also often the first to admit that the "free market" is an ideal/a model and unlikely to ever be a reality because humans are messy and ultimately irrational as individuals), and also ignore centuries worth of work since then, especially a lot of the "pre-calculus" stuff.
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.
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 admit I’m not particularly well versed in this space, but I’ve never come across that formulation, only the “pure” one the original researcher says is internally inconsistent. I don’t necessarily buy “it’s close enough it doesn’t matter” given what I perceive as many notable exceptions.
Markets are efficient if and only if P = NP https://arxiv.org/abs/1002.2284
:)
> 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.
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.
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.
No expensive analysis is needed. Beating them just requires (1) having disproportionate capital to others, and (2) having disproportionate control (and therefore know in advance) whatever the markets are pricing.
It helps that there are enough believers (in the religious/cult sense) that markets are 100% efficient, that they will deny that any of that is happening - even while they lose their shirts to those who are doing the market manipulation.
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
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.
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.
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.
I feel like I have not yet found the proper explanation. Or I'm just too dense to get it.
However, the reason they are part of the same category is because you can solve any problem in P / 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.
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".
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. This would be immense because it would completely change the way we solve those algorithms and greatly reduce compute costs.
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.
Every single problem in P is in NP. What is believed but unproven is that some problems in NP are not in P.
- 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/
The sum is finite (vs formal power series which can be infinite) The powers are constant (this is what makes it non-exponential)
Now seriously, I wonder if AI collusion/use in investments would add to the market inefficiency and create opportunities for observing investors.
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.
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.
Want to buy/sell a stock?
Humans need to manually submit in the system.
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.
Market makers and HFT don't determine price: price is usually purely determined by the net inflows and outflows as decided by humans. MMs just smooth it out over time so everyone gets good pricing at the time and in the size they want it.
> Second, there is never any reconciliation of the costs society is saddled with in order to chase arbitrarily more accurate prices
By definition market makers are earning a fraction of the price improvement they provide, ergo the costs to society have to be less that the benefits for better pricing for the companies to stay in business!
> Third, as an index investor, I more or less couldn’t care less
As an index investor you should absolutely care! How do you think you are able to buy into the fund at a reasonable price? And then how do you think the fund is able to rebalance without transaction costs destroying performance long-term?
"as decided by humans", more than 90% of trades are led by bots, so no, price is not being determined by humans.
In fact, we have seen time and again how some weird companies get a huge inflow of purchases simply because of bots misinterpreting news articles.
> > price is usually purely determined by the net inflows and outflows as decided by humans.
> "as decided by humans", more than 90% of trades are led by bots, so no, price is not being determined by humans.
You skipped past the "MMs just smooth it out over time so everyone gets good pricing at the time and in the size they want it" right afterwards which exactly explains why most trading is between bots! Person A wants to buy 10 shares of Y at time T1, Person B wants to sell 20 shares of Y at time T2, Person C wants to buy 10 shares of Y at time T3. Those are all at different times, therefore bots have to take the other side of each trade, then trade with each other to smooth out prices in between each point.
> In fact, we have seen time and again how some weird companies get a huge inflow of purchases simply because of bots misinterpreting news articles.
I actually clearly see this happening more with humans than with bots. Can you think of a single example attributed to bots? A bot that can misinterpret a news article and lose money is fixed and/or disabled forever. There is no shortage of dumb humans willing to lose money due to a lack of literacy.
By definition, they’re making in aggregate essentially whatever the difference was between the “misprice” and the “true price”, assuming sufficient belief in both of these things. One of the parties in the hypothetically mispriced trade is bearing the loss. Their cut had to come from somewhere.
> As an index investor you should absolutely care! How do you think you are able to buy into the fund at a reasonable price?
You are relying on an interpretation of “reasonable” to intuitively mean “cheap” when in reality it means “accurate” in this context.
As an index investor, as long as it is accurate enough I don’t care. Any mispricing of assets up and down will come out in the wash.
Index funds existed well before HFTs were endemic. I have seen zero evidence that HFTs have caused index funds to net more of the gains from their underlying indexes.
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."
NP problems gets solved with heuristics every day.
You don't know that!
You do realise that you'll never work in this town again? \s :)
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...
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.