Resource placement (optimal strategy)

I know that this is not exactly the right place to ask this question, but maybe a wise guy comes across and has the solution.

I'm trying to write a computer game and I need an algorithm to solve this question:

The game is played between 2 players. Each side has 1.000 dollars. There are three "boxes" and each player writes down the amount of money he is going to place into those boxes. Then these amounts are compared. Whoever placed more money in a box scores 1 point (if draw half point each). Whoever scores more points wins his opponents 1.000 dollars. Example game:

Player A: [500, 500, 0] Player B: [333, 333, 334]

Player A wins because he won Box A and Box B (but lost Box C).

Question: What is the optimal strategy to place the money?

I have more questions to ask (algorithm related, not math related) but I need to know the answer to this one first.

Update (1): After some more research I've learned that these type of problems/games are called Colonel Blotto Games. I did my best and found few (highly technical) documents on the subject. Cutting it short, the problem I have (as described开发者_运维知识库 above) is called simple Blotto Game (only three battlefields with symmetric resources). The difficult ones are the ones with, say, 10+ battle fields with non-symmetric resources. All the documents I've read say that the simple Blotto game is easy to solve. The thing is, none of them actually say what that "easy" solution is.

Update (2): I wrote a small actionscript file to demonstrate the strategy in the paper mentioned by Tom Sirgedas. You can test it at megaswf. Instructions: Click a point inside the triangle. Red region represent winning cases. Blue region represents losing cases, tiny whitish lines represents draw.

---

I found an optimal strategy in this paper: http://www.rand.org/pubs/research_memoranda/2006/RM408.pdf

Let's call this Blotto's strategy.

Look at the diagram above. Any move you make can be represented by a point on the triangle. The strategy in the paper says to pick a point at random in the hexagon. Choose points closer to the edge of the hexagon with higher probability (0 probability for the center of the hexagon, and linearly scale up to the maximum probability at the hexagon outline. Every point on the hexagon outline has equal probability.)

This solution is for "continuous" Blotto, but I assume you are interested in the discrete case (dividing N troops into 3 groups). Applying Blotto's strategy to the discrete case works perfectly well, when N is a multiple of 3. For other values of N, I was able to make a small adjustment on the hexagon border that works very well, but not perfectly.

If there is a strategy that can defeat this one, there must be some static move which wins against Blotto's strategy. There is none, except for when N is not a multiple of 3, then it seems that a move on the line where the big triangle and hexagon meet (e.g. the move <0,.5,.5>) will win against Blotto's strategy slightly more than lose. For N=100, the difference seems to be less than 1%, and continues to shrink for larger N.

Code to implement Blotto's strategy:

// generate a random number in the range [0,x) -- compensate for rand()%x being slightly un-uniform
int rnd( int x ) { int r; while ( 1 ) { r = rand(); if ( r < RAND_MAX/x*x ) return r % x; } }

// distance from center of triangle/hexagon to (x,y,z), multiplied by 3 (trilinear coordinates)
int hexagonalDist3( int x, int y, int z, int N ) { return max(max(abs(N-x*3),abs(N-y*3)),abs(N-z*3)); }

void generateRandomSimpleBlottoMove( int& x, int& y, int& z, int totalTroops )
{
   int N = totalTroops;
   while ( true )
   {
      x = rnd(N+1);
      y = rnd(N+1);
      z = N-x-y;

      // keep only moves in hexagon, with moves closer to the border having higher probability
      double relativeProbabilityOfKeepingThisMove = hexagonalDist3(x,y,z,N) > N ? 0 : hexagonalDist3(x,y,z,N);

      // minor adjustment for hexagon border when N is not a multiple of 3 -- not perfect, but "very close"
      if ( N % 3 != 0 && hexagonalDist3(x,y,z,N) == N ) 
         relativeProbabilityOfKeepingThisMove = N*(N%3)/3; 

      // possibly keep our move 
      if ( rnd(N) < relativeProbabilityOfKeepingThisMove )
         break;
   }
}

---

So this actually is a game theory question (economics) not a discrete math problem, re-tagging your question might attract the kind of attention you want. In game theory, the idea of a "solution" is usually Nash equilibrium. for zero sum games, it turns out the algorithm you want to solve this is a linear programming problem. See this wikipedia page for an example of how to set it up.

---

It seems to me that it would be fairly easy to prove that this game has no pure Nash equilibrium. A pure strategy is a fixed one, like [333,333,334]. My sketch of a proof is as follows:

For any pure strategy played by player A, player B can find another pure strategy that gets B 2 points. For example, if A plays [500,500,0] then B plays [501,0,499], or if A plays [333,333,334] then B plays [500,500,0], and so on. There is always a way to get 2 points. Of course, this means that player A would get 1 point.

Similarly, for any strategy played by player B, player A can find another pure strategy that gets him 2. Thus, no pure Nash exists.

Also, I think that it can be proven that the strategy (for both) of

1/3 [500,500,0], 1/3 [500,0,500], 1/3 [0,500,500]

(play [500,500,0] with 1/3 probability and [500,0,500] with 1/3 probability and [0,500,500] with 1/3 probability) is a mixed Nash equilibrium for this game. Under this strategy their expected gain (#points) is 3/2. The proof seems laborious to me. Maybe someone else will have a simple proof.

A mixed Nash is as closed to "optimal" as we can get. There are probably other mixed Nash equilibria for this game.