Sunday, December 16, 2007

A paradoxical three-person game: numerical solution

The general form of the N-option Mediocrity game can be depicted as follows:

123456...3N-23N-13N
ABCABC...ABC

Let us assume A's optimum strategy is of mixed type:

SA = a1(A←1) + a2(A←4) + ··· + aN(A←3N-2),

with 0 ≤ ai ≤ 1, ∑ai = 1 (a pure strategy is just a particular case where some ai = 1). The critical point in our analysis is the obervation that the roles of A and C are perfectly symmetrical, and thus C's optimum strategy must be the following:

SC = a1(C←3N) + a2(C←3N-3) + ··· + aN(C←3).

This interdependency of A's and C's strategies allows us to regard the game as a two-person one: B against the "combined player" A+C. If the strategy adopted by B is written down as

SB = b1(B←2) + b2(B←5) + ··· + bN(B←3N-1),

with 0 ≤ bi ≤ 1, ∑bi = 1, then B's payoff is

UB = ∑bi(P(A<i)P(i<C) + P(i<A)P(C<i))=
bi((a1+···+ai)(1aN−i+2···aN) + (1−a1−···−ai)(aN−i+2+···+aN)),

where aN−i+2+···+aN is by convention taken to be zero when i = 1. We abbreviate this expression as

UB = ∑bisi.

Note that si = sN-i+1.

Case 1: N even. A strategy (a1,...,aN) giving si = 0 for i=1,...,N is clearly optimum (for A+C). We show that such strategy exists and is unique by solving the set of N/2 equations:

s1 = a1 = 0,
s2 = (a1+a2)(1−aN) + (1−a1a2)aN =0,
...
sN/2 = (a1+···+aN/2)(1−a(N/2)+2−···−aN)+(1−a1−···−aN/2)(a(N/2)+2+···+aN) = 0.

The first equation implies a1 = 0, so that the second equation reduces to a2(1−aN)+(1−a2)aN = 0, from which it follows that a2 = aN = 0. Going down the rest of equations in a similar way we conclude that every ai except a(N/2)+1 must be zero. Hence the unique optimum strategy for A+C has

a(N/2)+1 = 1,
ai = 0 otherwise,

which translates to

SA= A←(3N/2)+1,
SC = C←3N/2.

As UB = 0, B's strategy is immaterial and can be identified with

SB = (1/N)((B←2) + ··· + (B←3N-1)).

The winner is A or C depending on which side of A and C consecutive positions B plays. Their payoffs are UA = UC = 1/2.

Case 2: N odd, N ≥ 3. Let (a1,...,aN) be an arbitrary strategy for A and s1,...,sN its associated coefficients. We define a derived strategy (a'1,...,a'N) in the following manner:

a'(N+1)/2 = a1 + ··· + a(N+1)/2,
a'(N+3)/2 = a(N+3)/2 + ··· + aN,
a'i = 0 otherwise;

Then the associated coefficients s'i verify the following:

  • s'(N+1)/2 = (a'1 + ··· + a'(N+1)/2)2+ (1 − a'1 − ··· − a'(N+1)/2)2 =
    = (a'(N+1)/2)2+ (1 − a'(N+1)/2)2 =
    = (a1 + ··· + a(N+1)/2)2+ (1 − a1 − ··· − a(N+1)/2)2 =
    = s(N+1)/2.
  • For i < (N+1)/2,
    s'i = (a'1 + ··· + a'i)(1 − a'N−i+2 − ··· − a'N) +
    + (1 − a'1 − ··· − a'i)(a'N−i+2 + ··· + a'N) =
    = 0(1-0) + (1-0)0 = 0, as all the a'i coefficients involved are other than a'(N+1)/2 and a'(N+3)/2.
  • For i > (N+1)/2, s'i = s'N−i+1 = 0, since N−i+1 < (N+1)/2.

So, for any strategy for B of the form (b1,...,bN) we have ∑bisib(N+1)/2s(N+1)/2 = ∑bis'i, the inequality being strict if any of a1,..., a(N−1)/2,a(N+5)/2,...,aN is different from zero, hence we conclude that an optimum strategy for A must have all its coefficients set to zero except those at positions (N+1)/2 and (N+3)/2. We are then left with the task of finding positive values of a(N+1)/2 and a(N+3)/2 adding to 1 and minimizing the maximum of the expression

UB = b(N+1)/2s(N+1)/2 = b(N+1)/2((a(N+1)/2)2 + (1 − a(N+1)/2)2),

which is obviously reached at b(N+1)/2 = 1. The solution to this trivial problem is a(N+1)/2 = a(N+3)/2 = 1/2. So, the optimum strategies for each player are:

SA= (1/2)(A←(3N−1)/2) + (1/2)(A←(3N+5)/2),
SB= B←(3N+1)/2,
SC = (1/2)(B←(3N−3)/2) + (1/2)(B←(3N+3)/2),

yielding payoffs UA = UC = 1/4, UB = 1/2.

Although the numerical solution of the N-option Mediocrity game seems entirely satisfactory, the argument stating that optimum strategies for A and C must be symmetrical induces, for N odd, N ≥ 3, some psychological difficulties akin to those arising in the analysis of the Prisoner's dilemma. We will examine this issue in a later entry.

No comments :

Post a Comment