Assignment 3: Simultaneous Games
Objectives
- to use a linear programming solver to find equilibria for simultaneous games
- to use Barron Theorem 1.3.8 to verify equilibria of simultaneous games
Introduction
Blotto is a simultaneous game for two players in which the players distribute military units over a number of battlefields. Each player has a set number of units to distribute, each unit is equivalent to each other unit, and a unit must be allocated entirely to a single battlefield. Each battlefield is worth a given number of points, and in the standard version of the game, the scoring is deterministic: the player who allocates more units to a battlefield wins the points for that battlefield (with the points split evenly in case of a tie, inlcuding a 0-0 tie).An alternative probabilistic scoring scheme gives the player with the most units in a particular battlefield a higher probablity of winning the points for that battlefield: if player 1 has allocated $u_1$ units in a battlefield, and player 2 has allocated $u_2$ units, then the probablity that player 1 wins the battlefield and all the points for it is $\frac{u_1^2}{u_1^2+u_2^2}$, and the probability that player 2 wins the battlefield and all the points for it is $\frac{u_2^2}{u_1^2+u_2^2}$. (If $u_1 = u_2 = 0$ then the winner of the battlefield is determined by a fair coin flip.)
For example, suppose there are four battlefields worth 1, 2, 3, and 4 points respectively and each player has 10 units to distribute. If player 1's distribution is $(1, 0, 4, 5)$ and player 2's distribution is $(1, 1, 3, 5)$ then, under the deterministic scoring scheme, player 1 wins battlefield 3, player 2 wins battlefield 2, and the players tie on battlefields 1 and 4. Player 1's score is then 5.5 and player 2's score is 4.5. In the probabilistic scoring scheme, battlefields 1 and 4 are both tossups (each player wins with probability $0.5$), player 2 always wins battlefield 2, and player 1 wins battlefield 3 with probability $\frac{16}{25}$.
The objective can be to win the game by scoring more points than your opponent (so margin of victory does not matter), or to score as many points as possible.
Assignment
Write a program calledBlotto
that
calculates and verifies equilibrium strategies for Blotto given a point
value for each battlefield and the number of units each player has to
distribute across those battlefields.
The task for the program to perform (calculate or verify), the parameters of the game (number of units and point value for each battlefield), and the objective (maximize wins or points) will be given as command-line arguments as follows.
-
The first command-line argument will be either
--find
or--verify
to indicate whether to find an equilibrium or verify the equilibrium read from standard input in the format described below. Both arguments can be followed by an optional argument--tolerance
which it itself followed by a floating point number between 0.0 (exclusive) and 1.0 (inclusive) giving the tolerance (see below). If--tolerance
is not given then $10^{-6}$ is used as the default value. -
The next command-line argument will be either
--win
,--score
, or--lottery
to indicate whether to find or verify equilibrium strategies with the objective of maximizing the expected number of wins under the deterministic scoring scheme (with ties counting as ½ a win), or maximizing the expected total points scored under the deterministic or probabilistic scoring schemes (we will not consider the objective of maximizing expected wins under the probabilistic scoring scheme). -
For
--find
, the third and fourth command-line arguments will be--units
and a positive integer giving the number of units to distribute. (For--verify
the number of units is determined by the values read from standard input.) - The remaining arguments are positive integers giving the value of each battlefield starting with battlefield 1. The number of battlefields is determined by the number of these arguments and will be positive.
For --verify
, the mixed strategy to check will be read from
standard input where each line gives a unique pure strategy as
the number of units to allocate to each battlefield, starting with
battlefield 1, and the probability of playing that pure strategy.
All values will be separated by a comma with no whitespace.
Each number of units will be a positive integer. Each pure strategy
will have the same total number of units and the same number of
battlefields. Each probability will be
a number between 0.0 (exclusive) and 1.0 (inclusive),
the input will be non-empty, and the sum
of the probabilities will be within the given tolerance of 1.0.
Your program
should determine whether both players playing the strategy read
from input is an equilibrium. Note that because of the imprecision
of the linear programming solver and the general imprecision of
floating point arithmetic, you will have to allow for some slack
in the inequalities (and in the sum of probabilities of the
inputs) – as long as none of the inequalities
are off by more than the given tolerance then consider the strategy an
equilibrium.
Your program should be able to perform any computation up to 10 units and 4 battlefields in a few seconds and up to 15 units over 5 battlefields in several minutes (all times measured in CPU time; on multi-core systems the real time elapsed may be less).
Output
For--find
, the output should be a mixed strategy in a format
readable by --verify
(the test scripts will run your output
through a verifier rather than checking for a character-by-character
match with some expected output, so the output needn't be in any specific
order) containing only pure strategies with probabilities that
exceed the tolerance.
For --verify
, the output should be either
PASSED
if the strategy is an equilibrium strategy for
both players, or any output that does not contain PASSED
as a substring otherwise (the public tests will discard any lines
that do not contain PASSED
and will perform a
character-by-character comparison on the lines that do contain
PASSED
).
Time and Space efficiency
The payoff matrices grow very quickly with the number of battlefields and the number of units, so it is essential to avoid unnecessary work and memory usage. There are two major considerations.
- Space to store the matrix: while you need to store the entire
matrix for
--find
since you need to pass it to the solver, for--verify
you only use each entry a small number of times after you've computed it. Since you only need to use each value a constant number of times, can you trade space for time by avoiding storing them all together in one place and recomputing them when you need them again.1 - Time to compute the payoff matrix: again, for
--find
, there is not much that can be done to optimize. But for--verify
, the matrix will usually be sparse (containing many zeros); can you avoid calculating entries in the payoff matrix that have no effect on the results for the the mixed strategy given as input?
If your implementation passes the public tests within the memory and time limits, then you should be confident that it will pass the private tests.
Examples
Note that there may be multiple equilibria, so your results may not match these for --find. Your solution will processed by a verifier as in the last two examples for grading. For the public tests, that will be your verifier, so it is essential to ensure that your verifier works correctly before testing your solver. For the provate tests, a known-working verifier will be used instead.[jrg94@cobra code]$ ./Blotto --find --score --units 4 1 2 0,4,1.0 [jrg94@cobra code]$ ./Blotto --find --score --units 5 2 4 5 0,0,5,0.14045462101642173 0,1,4,0.15496211495866577 0,2,3,0.04541673569373383 0,3,2,0.05992422986845587 1,0,4,0.08473480443797905 1,1,3,0.09503788495378677 1,2,2,0.17977268944230548 1,3,1,0.1404546206153363 1,4,0,0.04962114905424416 2,3,0,0.04962114943279007 [jrg94@cobra code]$ ./Blotto --find --lottery --units 5 2 3 5 1,1,3,1.0 [jrg94@cobra code]$ ./Blotto --find --tolerance 1e-05 --win --units 5 2 4 5 0,0,5,0.07428558119961398 0,1,4,0.0628572491429189 0,2,3,0.0514285583023659 0,3,2,0.10857121203986661 1,0,4,0.13142860782053217 1,1,3,0.01714278781855886 1,2,2,0.017143017862373943 1,3,1,0.13142851264458152 2,0,3,0.10857157877490509 2,1,2,0.05142853222724512 2,2,1,0.06285716721342921 2,3,0,0.074285740412162 3,2,0,0.10857132632298054 [jrg94@cobra code]$ ./Blotto --find --win --units 5 2 4 5 | ./Blotto --verify --win 2 4 5 PASSED [jrg94@cobra code]$ ./Blotto --find --lottery --units 5 2 3 5 | ./Blotto --verify --lottery 2 3 5 PASSED [jrg94@cobra code]$ ./Blotto --find --tolerance 1e-05 --win --units 5 2 4 5 | ./Blotto --verify --tolerance 1e-05 --score 2 4 5 E[X, (0, 0, 5)] = 5.25999904741337 < 5.499998589596961