Consumer theory proves that P=NP?

Economics Economics Questions
1

We were learning about P and NP in computer science today. All that is relevant to the conversation is that a certain set of problems P is a subset of another set NP.

A big question is whether P=NP.

Now, it has been proved that there are certain problems in NP called NP-complete. If these NP-complete problems can be shown to be part of the set P, then all NP problems are in P.

(To those interested, P is the set of problems that can be solved in polynomial time, while NP is the set of problems that can have their solutions verified in polynomial time. Showing that P=NP proves that if you can check the solution in polynomial time, you can also solve it from scratch in polynomial time).

One of the NP-complete problems is the knapsack problem:

You have a certain number of items. You also have a knapsack. The knapsack can only carry some limited amount of weight. The different items have a certain value. The knapsack problem is to maximize the total value of the items you put in the knapsack, constrained by the maximum weight the knapsack can carry.

If this problem can be shown to be P, then all NP problems are P.

My idea is as follows:

In consumer theory in economics, we know that people solve constrained optimization problems when buying things. That is, they maximize the utility they gain from the stuff they buy, constrained by the budgets they have. This problem is equivalent to the knapsack problem. Since the human brain is just a computer, then it seems that people solve the knapsack problem quickly, which shows P=NP.

If, on the other hand, the human brain cannot solve the knapsack problem, then the field of consumer theory in economics is wrong.

The assumption of economics that must be true is that of completeness. That is, given any two bundles of goods, a person may choose between them or be indifferent.

My intuition is that people do not in fact satisfy completeness, and instead think of only a limited number of bundles that they rank.

But if people’s valuation is indeed complete, then I’ve just proved that P=NP and should win a million dollars.

2

People do not solve the problem exactly* when they decide what’s to consume, they stop at a suboptimal solution, because the cost of computing the very optimal solution soon becomes greater than the benefit expected froma actually finding it.

It’s actually a very deep notion, it’s called “satisficing”, a port-manteau of satisfy and suffice, and it’s one of the main concepts introduced by the nobel prize Herbert Simon in his decision making theory.

  • except for very simple combinatorial problems where the number of elements to search is very small and the (exponential) time it takes to find the optimal solution is accordingly small.
3

In any case, your insight is somewhat in the right direction.

It is not the individual brain who solve the NP-hard problem of individual optimal consumption.

But in larger scale, the market price system provides an online dynamic-programing pseudo-optimal solution to the economic problem of resource allocation, and it’s able to do it due to it’s distributed structure of computation, where each decision taker is actually processing his share of consequential information throughout the whole economy, and incorporating his evaluation in the prices being communicated.

The whole von Mises argument of economic calculation is actually a intuitive grasp on this computer theory problem, something that the soviets would discover in practice when they had four million prices to affect. Some interesting contributions came from soviet mathematicians working on this practical problem, such as A. Kolmorogov and L. Kantorovich.

But in any case, the price system work does not provide a mathematical proof to the NP=P problem. That would require a perfect algorithm for finding the optimal solution in polynomial time (or the proof that such algorithm does not exist).

The large-scale combinatorial optimization performed by the price system coordination in a market is not “perfect”, it’s only “good enough”.

(I’m trying to write this things the mathematically possible, but then I’m not sure if I’m making any sense…)

4

I’ve also thought about how much time people choose to use in making decisions, since time itself is something to be economized. Therefore, you ration your amount of time you want to spend on matching up your means to your ends.

5

I don’t really understand the CS jargon. I designed a function that does this for the game I’m making. It took a few days to work out the instruction set. What I realized during this process is that the way real people do this is very flawed/incomplete. It’s the same situation in chess. As I competed in chess tournaments as a kid I realized at some point that it’s basically down to who pre-generates and remembers the most win paths. To make it realistic some laziness checks need to be added.

6

Yes. But the algorithm that solve’s in optimal time is not necesseraly polynomial in practice.
That’s because the polynomial algo might have a constant factor that makes it very costly for small cases.

In any case, you’re right to think that time of computation itself is economized.
In practice, what people do is to follow rules of thumb when taking these decisions, and these rules of thumb are not perfect but are good enough.
And then when they have to take similar decisions in the future, they may make some adjustments and refinements and thus get better results.

That’s what is called in mathematics an adaptive approximation algorithm.