81–90 of 176 posts
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.
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…
Earlier quoted context omitted.
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?
A 2010 entry by the same author: Markets are efficient if and only if P = NP https://arxiv.org/abs/1002.2284 :)
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.
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.
Earlier quoted context omitted.
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…
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.
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.
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 implications are not significant..? the real world is messy enough that this will not ever apply.
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.
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.