Equilibrium Point

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 = {x1..xn} of variables, a collection F = {F1..Fn} of integer product polynomials over the variables, and a set of “ranges” M = {M1..Mn} of subsets of the integers.  Can we find a sequence Y = {y1..yn}, where each yi ∈ Mi, and for all y ∈ Mi, Fi(y1, y2,…yi-1, yi, yi+1, …yn) ≥ Fi(y1, y2,…yi-1, y, yi+1, …yn)?

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 yi value to something else will not improve their personal Fi 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”.  F1 is defined by a table:

Player 2 stays silent Player 2 betrays
Player 1 stays silent -1 -3
Player 1 betrays 0 -2

F2 is defined similarly (the 0 and -3 scores switch places).

Notice that if we chose y1=y2 = 0 (both sides stay silent).  Then F1(0,0)= F2=(0,0) = -1.  But this is < F1(1,0), where player 1 betrays.  So this is not an equilibrium point.

y1=y2=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 fi for a clause Ci 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 hi(x’) to be 2* the product of all of the fi(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).  F1 (x’) = h1(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 F2 where F2 (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) = F1(x) + F2(x) * 2 – F1(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 F1 and -F1 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 fi 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) = F1(x)+F2(x)*(2-F1(x))

Now two things can happen.  If the formula was satisfiable, then F1(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 F1(x) is all 0’s, and so the scores in the F2 part influence the score for F, but the F2 part has no equilibrium, so F doesn’t either.

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

Leave a Reply

Your email address will not be published. Required fields are marked *