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

21–30 of 176 posts

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

#21

Post by narnarpapadaddy »

vlovich123 wrote: post #5

> 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…

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.

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

#22

Post by hughw »

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.

For the older among us, that's .ne.

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

#23

Post by marcosdumay »

kibwen wrote: post #3

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.

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

#25

Post by super_mario »

FailMore wrote: post #19

Would anyone mind explaining what P and NP are?

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

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

#26

Post by Dibby053 »

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

So markets can only be (perfectly) efficient or competitive, not both at the same time. Largely theoretical but it tracks common sense!

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

#27

Post by AlotOfReading »

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.

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

#28

Post by convolvatron »

FailMore wrote: post #19

Would anyone mind explaining what P and NP are?

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.

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

#29

Post by moomin »

vlovich123 wrote: post #5

> 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…

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