The Evergreen(r,s) Game

The game is named after our Evergreen Project. It is not to be confused with the famous chess game of Anderssen against Dufresne in 1852. r and s are at least 2. The game is already interesting with r=s=2.

Anna and Bob, the players, agree on a protocol P1 to choose a set G of s Boolean relations (of at most rank r). A CSP(G)-program (a constraint program) is a bag of constraints only involving the relations in G (allowing constraints to be duplicated). Anna chooses a CSP(G)-program H with at most v_max=1000 variables. The total number of constraints is at most a 10 digit decimal number. Bob solves H and gets paid by Anna the fraction times a million dollars that Bob satisfies in H. Anna will choose a program that will minimize Bob's profit. Take turns. Bob will choose a program and Anna solves it. The program iterates, say four times, and a new set of relations is chosen. The alternation of the game is: Anna: program, Bob: solves, Bob: program, Anna: solves for one round of the game. Each player has a fixed amount of time for each move, say 5 minutes. If the player fails to move in that time, the cost is $ 1 million and the game starts with a new set of relations.

The time that Anna spends on instance generation is A_inst. The time that Bob spends on solving the instance is B_solve. Bob's

As an example, the protocol P1 chooses the following set G={R1, R2} of relations (we could choose any pair of relations): R1(a) = !a and R2(a,b) = or(a,b). This is an Evergreen(2,2) game.

For G={R1,R2}, a program is:

A or B
B or C
B or C
and the maximum assignment is M={!A B !C} which satisfies all but one constraint, i.e., the satisfaction is 5/6.

What H should Anna choose for the G above? Should she use the full set CSP(G)-programs or should she limit herself to a subset?

Physics analogies

Those analogies are helpful in playing the game optimally.

Other Game properties

Iterated game of base zero-sum game. Perfect information game.

If Anna acts irrationally, we can transform her program into an S-CSP(G)-program in which fewer constraints can be satisfied by the best assignment.

Bob can always find efficiently an assignment J for the program H that Anna gives him so that J is as good as if Anna would have used her best answer.

In the game Evergreen(2,2) using the relations R1(a) = !a and R2(a,b) = or(a,b), the Fibonacci numbers play a role.

Nash Equilibrium

Anna: Use only a subset of the CSP(G) programs, called the S-CSP(G)-programs. Given G, Anna can compute an element in S-CSP(G) in P.

Bob: Compute a maximum-bias for H to get a coin to generate assignments flipping that coin. Use the derandomized version of this algorithm to achieve an assignment that is best possible provided Anna has acted rationally (played her best strategy). Computing the maximum bias and the derandomized algorithm are in P. To benefit from irrational play by Anna, use a MAX-CSP algorithm (like several algorithms provided by UBC-SAT), to search for a better assignment within the time left.


It is surprising that the two strategies, when Anna and Bob both play optimally, are in P. The game looks at first to be in Sigma-2.

Karl J. Lieberherr, CCIS, Nostheastern University, March 2007