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
!B
!C
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.

A substance consists of molecules and has a temperature. The molecule kinds and the temperature of the substance determine whether the substance is fluid or solid. The phase transition point is a property of the molecule kinds present in the substance. Statistical mechanics is about averaging. To find the right method of averaging is the fundamental principle of the statistical method for investigation of macroscopic systems. The derivation of general physical laws without consideration of the atomic-molecular structure is the main principle of the thermodynamic approach.
A program consists of components and has a temperature. The component kinds and the temperature of the program determine whether the program is fluid or solid. The phase transition point is a property of the component kinds. To play the Evergreen game well you must find the right method of averaging.
A constraint program consists of constraints and has a satisfaction level f: the fraction of constraints we want to satisfy. The relations are the molecule kinds. The temperature of the program is 1-f. When the temperature is high the program is fluid (always easy to solve, the answer is always true, fast). When the temperature is low the program is solid (maybe hard to solve, the answer is maybe, slow).

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.

Surprise

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