This next reduction is confusing to me, and I wonder if it’s because there is a typo in the paper.

**The problem: **Equilibrium Point. This is problem AN15 in the appendix.

**The description: ** Given a set X = {x_{1}..x_{n}} of variables, a collection F = {F_{1}..F_{n}} of integer product polynomials over the variables, and a set of “ranges” M = {M_{1}..M_{n}} of subsets of the integers. Can we find a sequence Y = {y_{1}..y_{n}}, where each y_{i} ∈ M_{i}, and for all y ∈ M_{i}, F_{i}(y_{1}, y_{2},…y_{i-1}, y_{i}, y_{i+1}, …y_{n}) ≥ F_{i}(y_{1}, y_{2},…y_{i-1}, y, y_{i+1}, …y_{n})?

**Example: **This concept of “Equilibrium point” is best through of from the perspective of Game Theory. The functions F are the utility functions for each player. The sequence Y is the set of choices each player makes. We are asking whether we can find a set of values in Y where any player i changing their y_{i} value to something else will not improve their personal F_{i }score.

So the classic “Prisoner Dilemma” problem can be represented in these terms: There are 2 players, so n is 2. Each range is with in {0,1}, where 0 means “stay silent” and 1 means “betray”. F_{1} is defined by a table:

Player 2 stays silent | Player 2 betrays | |

Player 1 stays silent | -1 | -3 |

Player 1 betrays | 0 | -2 |

F_{2} is defined similarly (the 0 and -3 scores switch places).

Notice that if we chose y_{1}=y_{2} = 0 (both sides stay silent). Then F_{1}(0,0)= F_{2}=(0,0) = -1. But this is < F_{1}(1,0), where player 1 betrays. So this is not an equilibrium point.

y_{1}=y_{2}=1 is an equilibrium point, where both functions return -2. Any player changing their choice from 1 to 0 will see their F function go from -2 to -3.

**Reduction: **Sahni does this in his “Computationally Related Problems” paper that we’ve used in the past to do some graph reductions. This reduction is from 3SAT. I’ll just say now that he could have avoided a lot of manipulation if he’d have used One-In-Three 3Sat. From a 3SAT instance, we build a game where there is one clause for each player, and the range of choices for each player is between {0,1}. The goal is to make a function f_{i} for a clause C_{i} that is 1 iff the corresponding clause is true. I’ll skip over the manipulations he does because he’s using a harder SAT problem than he needs to.

Define h_{i}(x’) to be 2* the product of all of the f_{i}(x’) values (for some literal x’. If x;’ is a positive literal, use the variable. If it’s a negated literal, use 1- the variable). F_{1} (x’) = h_{1}(x’) for all players. This means that if the formula was satisfiable, everyone could score 2, but if it wasn’t, they’d always score 0.

Now it gets weird. We’re going to set up a *second* game G, a 2 player game with no equilibrium point, then define a second payoff function for our original game F_{2} where F_{2} (x) = the g function of x for the first 2 players, but 0 for everyone else.

The paper says that the actual payoff for the actual game we’re creating is: F(X) = F_{1}(x) + F_{2}(x) * 2 – F_{1}(x)

The “2” is a payout of 2 for all players- since the above depends on matrix math, it’s an nx1 vector of all 2’s. This formula is very weird to me because the F_{1} and -F_{1} should cancel out. This is where I think there might be a typo. I’m pretty convinced there *is* a typo on the previous page where he was building his little f_{i} function (he uses a + where there should be a -). I’m thinking that there are missing parentheses in this formula, and it should be F(X) = F_{1}(x)+F_{2}(x)*(2-F_{1}(x))

Now two things can happen. If the formula was satisfiable, then F_{1}(x) is all 2’s, and that is the max payout for everyone and is an equilibrium point. If the formula was not satisfiable, then F_{1}(x) is all 0’s, and so the scores in the F_{2} part influence the score for F, but the F_{2} part has no equilibrium, so F doesn’t either.

**Difficulty: **8. I think I found the typo though.