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 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).

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 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.

The objective can be to score more points than your opponent or to score as many points as possible.

Assignment

Write a program called Blotto 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.
The second command-line argument will be either --win or --score to indicate whether to find or verify equilibrium strategies with the objective of maximizing the expected number of wins (with ties counting as ½ a win), or maximizing the expected total points scored.
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) and the sum of the probabilities will be within $10^{-6}$ 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 – as long as none of the inequalities are off by more than $10^{-6}$ 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).

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).

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.