Thursday, November 09, 2006

Games and Groups: Part 2

A bit of notation: Z4 is the cyclic group with four elements, Z2xZ2 is the direct product of (you guessed it!) two cyclic groups of order 2. Z4 has one element of order 2 and two of order 4, whilst Z2xZ2 has three elements of order 2.

When we last left Greg and Kathleen, Kathleen had devised a strategy for guessing the group Greg had in mind.
Kathleen's strategy was (a snippet of my test implementation and sorry about the indentation):

int a00 = greg.ask(0, 0);
if (a00 == 0) {
// el. 0 is identity
if (greg.ask(1, 1) == 0) {
// el. 1 has order 2
if (greg.ask(2, 2) == 0) {
// el. 2 has order 2
return z2z2;
} else {
// el. 2 has order 4
return z4;
}
} else {
// el. 1 has order 4
return z4;
}
} else {
// el. 0 has order 2 or 4.
if (greg.ask(a00,a00) != a00) {
// el. 0 has order 4
return z4;
} else {
// a00 is the identity, 0 has order 2
int other;
if (a00 == 1) {
other = 2;
} else if (a00 == 2) {
other = 3;
} else {
other = 1;
}
if (greg.ask(other, other) == a00) {
return z2z2;
} else {
return z4;
}
}
}

If Greg has Z4 in mind, Kathleen needs 2+1/3 guesses on average, while if Greg has Z2xZ2 in mind, she needs 3 (not even on average, always!). I got these numbers by running the game repeatedly, but they seem reasonable. The "return z2z2" statement is always three 'if's down, as you need the identity and two elements of order two to get to Z2xZ2. In some cases, Z4 can be settled on more quickly.

So if Greg chooses randomly, Kathleen will need 2 + 2/3 guesses.

Greg, being the greedy bastard that he is, will however seek to maximize his gains. He could choose the more expensive Z2xZ2 more often. Not too often, though, as Kathleen could just blindly guess Z2xZ2 if Greg always chooses Z2xZ2 in the hope of getting 3 EUR from Kate every time. (This all depends on the penalty Kathleen has to pay when she guesses wrong).

Suppose Greg chooses Z2xZ2 with probabilty p, and Z4 only with probability (1-p). This ups Greg's revenue to p*3 + (1-p)*(7/3) = 7/3 + 2p/3.

So Kathleen had better come up with a strategy that costs her at most 7/3 in both cases! Does such a strategy exist? I don't know (yet!)....