3
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.