Here's a partial answer: No, these are not the only strategies. For $n=3$, there are $10752$ different strategies, only $24$ of which arise in the manner you describe. (Let's call them "product strategies".)
First, to count the product strategies, we can make use of the fact that there is only one group with three elements and it is abelian. Thus the order in the product is irrelevant, and the only things to choose are the $l_k$ and the three bijections between the colours and the group elements for each logician. That makes four choices with $3!$ possibilities each, but many of these lead to the same strategies. To see this, note that the permutations of the remainders modulo $3$ can all be written as $r\to\sigma r+t$ with $\sigma=\pm1$. The additive constants $t$ of all four options can be assembled into a single one, so we only have one additive constant (three possible values) and four signs. However, we can multiply the entire equation by $-1$, which leaves only three independent signs, with two possible values each, for a total number $3\cdot2^3=24$ of possibilities. This is confirmed by a computer search.
Below I give a listing of a program that finds all strategies for $n=3$. It finds $10752=2^9\cdot3\cdot7$ of them. Here's one that isn't a product strategy:
$$
\begin{array}{c|ccccccccc}
&00&01&02&10&11&12&20&21&22\\\hline
d_0&0&0&1&0&1&2&1&2&2\\
d_1&2&1&2&0&2&1&0&1&0\\
d_2&2&2&1&1&0&2&1&0&0\\
\end{array}
$$
You can check that it's a strategy by going through the $3^3$ cases, and you can see it's not a product strategy because a product strategy couldn't have $d_0(0,0)=d_0(0,1)=0$.
Some interesting facts that may point towards a solution: For $n=3$, there is no individual choice left in any of the strategies; that is, for any two individual strategies $d_0$ and $d_1$ there is never more than one strategy $d_2$ to complete them. Also, for $n=3$ in each strategy each player guesses each colour for the same number of combinations. And generally (not just for $n=3$) only one player guesses correctly for each combination; this follows because the expectation value of a correct guess is $1/n$, so if there were combinations with more than one correct guess there would have to be one with no correct guess. All this may point to some magic-square-like description of the solutions.
Here's the code:
import java.util.Set;
import java.util.HashSet;
public class Hats {
final static int n = 3;
final static int UNKNOWN = -1;
static int [] [] [] strategy = new int [n] [n] [n]; // [player] [first hat seen] [second hat seen]
static int [] [] permutations = {
{0,1,2},
{0,2,1},
{1,2,0},
{1,0,2},
{2,0,1},
{2,1,0}
};
static int [] [] inversePermutations = new int [6] [3];
static {
for (int i = 0;i < 6;i++)
for (int j = 0;j < 3;j++)
inversePermutations [i] [permutations [i] [j]] = j;
}
static Set<Integer> productStrategies = new HashSet<Integer> ();
public static void main (String [] args) {
// generate all product strategies
int [] p = new int [3];
for (p [0] = 0;p [0] < 6;p [0]++)
for (p [1] = 0;p [1] < 6;p [1]++)
for (p [2] = 0;p [2] < 6;p [2]++)
for (int g = 0;g < 6;g++) {
for (int player = 0;player < 2;player++)
for (int first = 0;first < 3;first++)
for (int second = 0;second < 3;second++)
strategy [player] [first] [second] =
inversePermutations [p [player]]
[(permutations [g] [player] -
permutations [p [(player + 1) % 3]] [first] -
permutations [p [(player + 2) % 3]] [second] + 9) % 3];
productStrategies.add (getCode ());
if (!isCorrect ())
throw new Error ();
}
System.out.println ("Found " + productStrategies.size () + " different product strategies");
// generate all strategies
recurse (0);
System.out.println ("Found " + count + " different strategies in all");
}
final static int [] colours = new int [n];
static int count;
static int total;
// returns a unique integer code for the strategies of the first two players
static int getCode () {
int result = 0;
for (int player = 0;player < 2;player++)
for (int first = 0;first < 3;first++)
for (int second = 0;second < 3;second++)
result = 3 * result + strategy [player] [first] [second];
return result;
}
// checks whether the strategies of the first two players allow for a strategy of the third player
// returns true if there is one strategy, false for none, throws an error if there is more than one
static boolean isCorrect () {
for (int i = 0;i < n;i++)
for (int j = 0;j < n;j++)
strategy [2] [i] [j] = UNKNOWN;
// for each combination of hat colours, check whether one of the first two players guesses correctly;
// if not, this fixes a value in the third player's strategy
for (colours [0] = 0;colours [0] < n;colours [0]++)
for (colours [1] = 0;colours [1] < n;colours [1]++)
for (colours [2] = 0;colours [2] < n;colours [2]++) {
if (strategy [0] [colours [1]] [colours [2]] != colours [0] &&
strategy [1] [colours [2]] [colours [0]] != colours [1]) {
// neither of the first two players guesses this combination correctly
int s = strategy [2] [colours [0]] [colours [1]];
int s0 = colours [2];
if (s == UNKNOWN)
// fix the third player's strategy in this case
strategy [2] [colours [0]] [colours [1]] = s0;
else if (s != s0)
// or conclude that there is no strategy if it was already otherwise determined
return false;
}
}
// check that there's only one strategy left for the third player
for (int i = 0;i < n;i++)
for (int j = 0;j < n;j++)
if (strategy [2] [i] [j] == UNKNOWN)
throw new Error ();
return true;
}
static boolean first = true;
// generate all 3^18 combinations of strategies for the first two players
static void recurse (int depth) {
if (depth == (n - 1) * n * n) {
if (isCorrect ()) {
// this combination allows for a successful strategy of the third player -- count it...
count++;
if (first && !productStrategies.contains (getCode ())) {
// and if it's the first non-product strategy, print it as a TeX array
System.out.println ("non-product strategy:");
for (int player = 0;player < 3;player++) {
for (int first = 0;first < 3;first++)
for (int second = 0;second < 3;second++)
// internally first and second are cyclic; for output the order is reversed for the second player
System.out.print ("&" + strategy [player] [player == 1 ? second : first] [player == 1 ? first : second]);
System.out.println ("\\\\");
}
first = false;
}
}
}
else {
int player = depth / (n * n);
int first = (depth / n) % n;
int second = depth % n;
for (int guess = 0;guess < n;guess++) {
strategy [player] [first] [second] = guess;
recurse (depth + 1);
}
}
}
}
After writing up this answer I found this paper that comes to the same conclusions and also generalizes the problem to $q$ hat colours. I'm posting the answer anyway to have it here on math.SE in self-contained form.
As described in the Wikipedia article Gerry linked to and this book it references, an optimal strategy concentrates the wrong guesses onto as few configurations as possible. Each individual player guesses incorrectly exactly half the time if she doesn't pass, and ideally these incorrect guesses should all be concentrated on configurations where everyone guesses incorrectly whereas the correct guesses should ideally be spread out one per configuration.
Let's denote the set $\def\red{\text{red}}\def\blue{\text{blue}}\def\pass{\text{pass}}\{\red,\blue\}$ of hat colours by $H$ and the set $\{\red,\blue,\pass\}$ of guesses by $G$. Then a strategy for $n$ prisoners is a function $H^n\to G^n$ such that the $k$-th entry of the value doesn't depend on the $k$-th entry of the argument.
Given a strategy, we're interested in the proportion of vectors of $H^n$ for which the strategy prescribes a value which is not the constant $\pass$ vector and in which all non-pass entries match the corresponding entries in the argument. Let's call such vectors good and the others bad.
Adjacent to every good vector $g\in H^n$ is at least one bad vector $b\in H^n$ that differs from $g$ only in the hat colour of one of the prisoners who guess correctly for $g$ (of which there is at least one). Conversely, given a subset $S\subseteq H^n$ of bad vectors such that every vector is adjacent to at least one bad vector in this sense, we can make all other vectors good by assigning an adjacent bad vector to each of them (arbitrarily if there's more than one) and letting only the prisoner in whose entry the two vectors differ guess.
Thus, an optimal strategy is defined by a minimal subset $S\subseteq H^n$ such that all vectors in $H^n$ are adjacent to at least one element of $S$. Such a minimal subset is called a binary optimal covering code of length $n$ and radius $1$, and the number of vectors in such a minimal subset is denoted by $K(n,1)$. This table (linked to from this page) gives the known bounds on $K(n,1)$ up to $n=33$.
For $n=2^k-1$ the Hamming codes described in the article and the book are optimal binary covering codes with $2^{n-k}$ vectors, with winning probability $1-2^{n-k}/2^n=1-2^{-k}=n/(n+1)$. For other values of $n$, the values of $K(n,1)$ are only known up to $n=9$, and for $n$ a power of $2$; the lower bound for $K(27,1)$ was improved only recently.
Best Answer
I'm not solving the general problem, just answering about this apparent paradox about independent variables influencing the probability.
You are right that for each person separately, the chance to get it right or wrong in repeated executions of this procedure is the same. But this game is about $n$ players playing the game simultaneously, and the information those players have is highly correlated: Player $A$ and player $B$ see the absolute same hats from all the other $n-2$ players, the only difference is in hat $A$, that player $B$ sees, and hat $B$, that player $A$ sees.
So a pre-discussed strategy, while not allowing each person to guess their own hat color with more than 50% probability, by allowing passes allows the 'good' outcome defined in the problem to succeed with probability > 0.5.
As another argument, assume that players could not pass, each one had to state the color of their hat. It would seem that the probability that everyone guesses correctly would now plunge down to almost 0 for big $n$, right? Not correct, with a prediscussed strategy the probability that everyone guesses correctly can be made 0.5. Everybody simply assumes that the number of overall red hats among all players is even, then states their own hat color based on what they can see to make the assumption true.
First to note is that with this strategy, all players simultaneously get it right or get it wrong. That's due to the highly correlated information they get to make their decision. Second to note is that using binomial coefficients, the number of red hats being even is happening in exactly half of the $2^n$ cases, so the probabiliy of being right is 0.5.
It should be clear that allowing passes might increase the probability, as you've shown for $n=3$.