*(Cross-posted from my blog)*

At a rough level:

- Decision theory is about making decisions to maximize some objective function.
- Zero-sum game theory is about making decisions to optimize some objective function while someone else is making decisions to minimize this objective function.

These are quite different.

## Decision theory and NP

Decision theory roughly corresponds to the NP complexity class. Consider the following problem:

Given a set of items, each of which has a integer-valued value and weight, does there exist a subset with total weight less than and total value at least ?

(It turns out that finding a solution is not much harder than determining whether there is a solution; if you know how to tell whether there is a solution to arbitrary problems of this form, you can in particular tell if there is a solution that uses any particular item.)

This is the knapsack problem, and it is in NP. Given a candidate solution, it is easy to check whether it actually is a solution: you just count the values and the weights. Since this solution would constitute a proof that the answer to the question is “yes”, and a solution exists whenever the answer is “yes”, this problem is in NP.

The following is a general form for NP problems: