Effecient way to find optimal solution in a 2 player game

Question

I have a function: \begin{equation*} f(a_1,\ldots,a_7,b_1,\ldots,b_4)=-14-7 a_1+30 a_1 a_2-7 a_4-2 a_4 a_5+21 a_6+21 a_7+16 a_1 b_1-24 a_1 a_2 b_1+6 a_4 b_1-6 a_4 a_5 b_1+6 a_1 b_2-6 a_1 a_2 b_2+8 a_4 a_5 b_2-6 a_6 b_3-24 a_7 b_3+8 a_6 b_4-6 a_7 b_4 \end{equation*}

$$\begin{array}{cc} \forall i: 0.0 \le a_i \le 1.0, & \forall j: 0.0 \le b_j \le 1.0 \end{array}$$

Two players are playing a game, where player $A$ is trying to maximize the function by picking $a_i$, and player $B$ is trying to minimize it by picking $b_j$. Player A goes first and picks all $a_i$ variables. Player B goes next, knows what player A picked, and picks all $b_j$ accordingly.

What's player A's best pick? And what's B's corresponding pick? Turns out one of the answers is: $a_1=0, a_2=1, a_4=0, a_5=0, a_6=1, a_7=0; b_1=1, b_2=0, b_3=1, b_4=0$
This way the function evaluates to 1, which is the best player A can ever do.

What's the most efficient way to compute this, especially when you have a lot more variables? Are there shortcuts that you can see or is the only option brute force? May be the optimal solution always has a form with $\forall i: a_i=0.0 \lor a_i=1.0$?

Answer 1

This is a sequential game theoretic problem with complete information. Accordingly, you are looking for a subgame perfect Nash equilibrium.

One usually solves this recursively, i.e., backwards. The last player to move is player 2. You assume that the moves by player 1 ($a_1,\ldots$) have already been made, and player 2 knows the values. The optimal strategy of 2, given the strategy of player 1, is to set $b_j$ to 1 whenever the term is negative, and set it to 0 whenever the term is positive. This is a fairly simple strategy.

Now we look at the strategy of the second player. The second player anticipates the strategy of player 2 (which we just determined) and chooses his actions accordingly. First, he look how many points he can get on himself (i.e., in terms that only involve $a_i$s). Second he will look whether he can realize a positive number by looking at $a_i$s that for at least one term do not involve $b_j$s, but may for others.

Accordingly, as you figured out, he will set $a_i=0, a_6=1$. Note that he can do both set $a_2=0$ or equal to 1. Since $a_1$ is zero, this doesn't change the payoff. Note also that it is possible to set $a_1,a_2=1$, which also results in 1 for player 1. Now you just go back to player 2 and use the above strategy to determine the $b_j$s.

This doesn't make the task easier; basically, we also just do brute force, but in a certain order. You are right that an equilibrium can (!) always involve weights 1 or 0 (the only time this does not have to be the case is if the terms are zero anyway. For example, for $-6a_6b_3$ you can set $b_3$ to anything if $a_6$ is zero). Thus, it is without loss of generality to look only at weights 1 or 0 if you want to find one equilibrium of the game. If you want to find all, then you also have to consider all those where you can set a parameter to everything in $[0,1]$.