Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Markets are competitive if and only if P != NP

arxiv.org

Post reply on HN
Print view View original

91–100 of 176 posts

Re: Markets are competitive if and only if P != NP

#91

Post by calfuris »

dpweb wrote: post #60
FailMore wrote: post #19

Would anyone mind explaining what P and NP are?

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…

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.

Re: Markets are competitive if and only if P != NP

#93

Post by falcor84 »

nok22kon wrote: post #38
cs702 wrote: post #4

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.

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.

Re: Markets are competitive if and only if P != NP

#94

Post by ThrustVectoring »

api wrote: post #9

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."

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.

Re: Markets are competitive if and only if P != NP

#95

Post by peder »

throwaway27448 wrote: post #89
ajkjk wrote: post #48

Earlier quoted context omitted.

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.

Re: Markets are competitive if and only if P != NP

#96

Post by samrus »

dheera wrote: post #84
silentmafia wrote: post #7

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

Re: Markets are competitive if and only if P != NP

#97

Post by xxpor »

pwdisswordfishq wrote: post #80
xxpor wrote: post #2

The actual paper's title is "Markets are competitive if and only if P != NP" Seems that HN's auto-headline rewriting in this case has made a critical error :) >Artificial intelligence, by expanding firms' computational capabilities, is pushing markets from the competitive regime toward the collusive regime, explaining the empirical emergence of algorithmic collusion without explicit coordination. I have to dig more i…

The 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.

Re: Markets are competitive if and only if P != NP

#98

Post by sgt101 »

jopsen wrote: post #68

This offers little because while P != NP, in most practical cases it doesn't matter. NP problems gets solved with heuristics every day.

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 :)

Re: Markets are competitive if and only if P != NP

#99

Post by random3 »

FailMore wrote: post #19

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/

Re: Markets are competitive if and only if P != NP

#100

Post by j05ev1f3 »

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
Post reply on HN