Playing the game:

benefits of derandomization:
Benefit from irrational behavior by Anna.
Protect against irrational behavior by Anna.
will guarantee in any case t[G].
If Anna should act irrationally, then computing the maximal k
and setting the first k variables to true, could lead to very bad results.

So the reasoning goes:
Best strategy for Bob:

1. Derandomized algorithm to benefit from and protect against
   irrational behavior by Anna. If Anna is irrational, we are protected
   against not finding a good enough assignment. Whatever satisfaction level
   we find, we will be able to construct an instance for which we don't
   have to pay more than what we received.
   We benefit from Anna's irrational behavior because of the potential
   of the derandomized algorithm to find a really good assignment.

Not that this is not an empty statement. We could not just give back the 
instance we got from Anna, because Anna might find a better assignment than we did.

Guaranteeing a tie:

Anna can force a tie by giving to Bob a symmetric instance with
the maximum number of variables and optimal multiplicities so that
the best move for Bob will be to give back the same instance.

So the goal for Bob is to achieve a tie.
The derandomized algorithm is guaranteed to achieve a tie in polynomial time.
If Anna acted rationally, ...
If Anna acted irrationally, the derandomized algorithm guarantees
an assignment fraction so that we can find an instance for Anna
that has <= satisfaction level.

The Evergreen Tie Problem: 
How can Bob achieve a tie or better in one Anna-inst/Bob-solve/Bob-inst/Anna-solve
macro move of the Evergreen game.

I claim that we don't need MAX-CSP solvers to solve the 
Evergreen Tie problem.
The derandomized algorithm guarantees that Bob
will find an assignment that will bring in enough money
so that he does not have to pay more than that amount in the next move.
If Anna acts irrationally, Bob might profit significantly.

Note that the following strategy does not work for Bob to achieve a tie or better:
Give back the same instance that Anna gave him because Anna might
be able to find a better assignment (if she acted irrationally).

Note: Anna can force a tie by giving to Bob the worst possible instance.
Then he Bob must give back the same instance.


2. Use a good MAX-CSP solver for the remaining time.

In this solution concept, players are assumed to be rational and so strictly dominated strategies are eliminated from the set of strategies that might feasibly be played. A strictly dominated strategy is one for which there is a strategy that a player is always better off playing and so a rational player would never play such a strategy. (Strictly dominated strategies are also important in minimax game-tree search). For example, in the (single period) prisoners' dilemma (shown below), cooperate is strictly dominated by defect for both players because either player is always better off playing defect, regardless of what his opponent does.

Nash equilibrium

    Main article: Nash equilibrium

    A Nash equilibrium is a strategy profile (a strategy profile specifies a strategy for every player, e.g. in the above prisoners' dilemma game (cooperate, defect) specifies that prisoner 1 plays cooperate and player 2 plays defect) in which every strategy is a best response to every other strategy played. A strategy by a player is a best response to another player's strategy if there is no other strategy that could be played that would yield a higher pay-off in any situation in which the other player's strategy is played.

Nash-equilibrium for Evergreen:

Anna: Use only a subset of the CSP(G) programs, called the S-CSP(G)-programs.

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).
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.