Problem
To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount of units is non-discrete (e.g. 1.2).
Game
The game for two players ($\alpha$ and $\beta$) is over an undirected graph consisting of nodes connected by edges. Each node has a connection to itself and can hold at most $M$ units. Initially, each player has 1 unit on 1 node. A player owns a node when he has more than $\epsilon$ units on the node. A bonus set is a set of nodes with a bonus. If a player owns all nodes of a bonus set, he owns the bonus set. The income of a player is the sum of the bonuses of his bonus sets.
Each turn has three phases:
- Deployment: Each player distributes his income over his nodes. This distribution adds a non-negative number of units to the existing units on the nodes.
- Transfer: Each player distributes units from each node $X$ to nodes directly connected to node $X$.
- Resolution: For each node, calculate the absolute difference between the total numbers of units sent to the node by the players. If this absolute difference exceeds $\epsilon$, the number of units on the node is this absolute difference and the player who sent more units owns the node. Otherwise, the number of units on the node is zero and no one owns the node.
Conventions
We will omit an equation for the $\beta$ player if replacing $\beta$ by $\alpha$ yields the corresponding equation for the $\alpha$ player. The equations for the constraints are boxed. All vectors are column vectors.
Definitions
Constraints
Figure 1. Dependency graph for the variables. Constants and calculations are not shown.
Bonus set ownership: Since owning a bonus set means owning all nodes in the bonus set, $s_{k}^{\alpha} = 1$ is equivalent to $\forall i \in \mathscr{B}_{k}: w_{i}^{\alpha} = 1$. Therefore, $$\tag{1} \boxed{ \forall k: \forall i \in \mathscr{B}_{k}: w_{i}^{\alpha} \ge s_{k}^{\alpha} \ge 0 }$$
Notice that optimizing the objective will push $s_{k}^{\alpha}$ to $1$ if possible. This is because the continuous variable $s_{k}^{\alpha}$ is equivalent to giving the $\alpha$ player a choice to voluntarily give up the contribution of the $k^{\mathrm{th}}$ bonus set to his income.
Income: A player's income is sum of the bonuses for his bonus sets. $$\begin{align} \tag{2} c_{\alpha} = \sum_{k} b_{k}s_{k}^{\alpha} = \vec{b} \cdot \vec{s}_{\alpha} \end{align}$$
Transfer: The total number of units transferred from a node is sum of the units on the node before deployment and the deployment to the node. Therefore, $$ \begin{align} \left( \mathcal{R}_{\alpha}\vec{1} \right)_{i} &= \sum_{j} R_{ij}^{\alpha} = \left( \vec{u}_{\alpha} + \vec{d}_{\alpha} \right)_{i} \\ \tag{3} \implies \vec{d}_{\alpha} &= \mathcal{R}_{\alpha}\vec{1} - \vec{u}_{\alpha} \end{align} $$ Each transfer moves a non-negative number of units.
$$\tag{4}\boxed{ \forall i,j: R_{ij}^{\alpha} \ge 0 }$$
Deployment: The deployment to a node is non-negative. A player must deploy a number of units that is equal to his income. $$ \tag{5} \boxed{ \mathcal{R}_{\alpha}\vec{1} - \vec{u}_{\alpha} = \vec{d}_{\alpha} \ge \vec{0} } $$ $$ \tag{6} \boxed{ \left (\mathcal{R}_{\alpha}\vec{1} - \vec{u}_{\alpha} \right) \cdot \vec{1} = \vec{d}_{\alpha} \cdot \vec{1} = c_{\alpha} } $$
After deployment, each player has at most $M$ units on nodes that he owns and at most $0$ unit on nodes that he does not own.
$$\tag{7} \boxed{ M\vec{w}_{\alpha} \ge \vec{d}_{\alpha} + \vec{u}_{\alpha} = \mathcal{R}_{\alpha}\vec{1} }$$
Resolution: The total transferal to a node is the sum of transferals from each node to the node.
\begin{align} \tag{8} \left( \vec{q}_{\alpha} \right)_{j} &= \sum_{i} R_{ij}^{\alpha} \\ \implies \vec{q}_{\alpha} &= \mathcal{R}_{\alpha}^{\mathsf{T}}\vec{1} \end{align}
The differences between the total transferals to the nodes by the $\alpha$ and $\beta$ players are: $$ \begin{align} \tag{9} \vec{v}_{\alpha} &= \vec{q}_{\alpha} - \vec{q}_{\beta} \\ \tag{10} \vec{v}_{\beta} &= \vec{q}_{\beta} - \vec{q}_{\alpha} = - \vec{v}_{\alpha} \end{align} $$
The $\alpha$ player owns a node if his total transferal to the node exceeds the $\beta$ player's total transferal to the node by $\epsilon$.
$$\tag{11}\label{11}\boxed{ (M - \epsilon)\vec{w}_{\alpha}[t + 1] \ge \vec{q}_{\alpha} - \vec{\epsilon} \ge (M + \epsilon)(\vec{w}_{\alpha} - 1) }$$ $$\tag{12}\label{12}\boxed{ M(1 - \vec{w}_{\alpha}) + \vec{q} \ge \vec{u}_{\alpha}[t + 1] }$$ $$\tag{13}\label{13}\boxed{ M\vec{w}_{\alpha} \ge \vec{u}_{\alpha}[t + 1] }$$
Notice that maximizing the objective would require maximizing each player's number of units. That would make $\vec{u}_{\alpha}$ as large as possible. Consequently, the constrains and the objective together leads to:
\begin{align}\tag{14}\label{14} \left( \vec{w}_{\alpha} \right)_{i} &= \begin{cases} 1 \quad &\mathrm{if } \left(\vec{q}_{\alpha}\right)_{i} \ge \epsilon \\ 0 \quad &\mathrm{otherwise} \end{cases} \end{align}
\begin{align}\tag{15}\label{15} \left( \vec{u}_{\alpha} \right)_{i} &= \begin{cases} \left(\vec{q}_{\alpha}\right)_{i} \quad &\mathrm{if } \left(\vec{q}_{\alpha}\right)_{i} \ge \epsilon \\ 0 \quad &\mathrm{otherwise} \end{cases} \end{align}
Objective
Minimax objective: Following the minimax strategy, the $\alpha$ player would choose moves that minimize his maximal loss over all possible moves of the $\beta$ player. Expressing this objective in terms of score instead of loss, we have: $$ \tag{16} \max_{\vec{\alpha}}\min_{\vec{\beta}} f(\vec{\alpha}, \vec{\beta}) $$ where $\vec{\alpha}$ and $\vec{\beta}$ are the moves of the $\alpha$ and $\beta$ players respectively and $f$ is the $\alpha$ player's score.
Since the game is zero-sum, sum of the scores of the two players is 0. Consequently, the minimax objective for the $\beta$ player is: $$\tag{17} \max_{\vec{\beta}}\min_{\vec{\alpha}} -f(\vec{\alpha}, \vec{\beta}) $$
Notice that the minimax objectives of both players are equivalent. Therefore, optimizing the minimax objective would find the moves of both players if they both use the minimax strategy.
Objective of the game: Choosing the $\alpha$ player's unit advantage at turn $T$ as the score, we have:
$$ \tag{18} f^{(T)} = a_{\alpha}[T] = \vec{1} \cdot ( \vec{u}_{\alpha}[T]- \vec{u}_{\beta}[T]) $$ where $f^{(T)}$ denotes the $\alpha$ player's score at turn $T$.
The minimax optimization of the objective is: $$\tag{19} \max_{\mathcal{R}_{\alpha}[0]} \min_{\mathcal{R}_{\beta}[0]} \max_{\mathcal{R}_{\alpha}[1]} \min_{\mathcal{R}_{\beta}[1]} \cdots \max_{\mathcal{R}_{\alpha}[T]} \min_{\mathcal{R}_{\beta}[T]} f^{(T)} $$
