Optimally played game

Question

Consider a game played on the tree above, where the "cost" at a leaf is paid by P1 to P2. Thus P1 wants the number to be as small as possible where P2 wants it to be large. What is the cost paid by P1 to P2 if both players play optimally?

When a question asks "optimally", does it mean that the players play trying to get the maximum amount after each move, and that the opposite player is also playing optimally? What I mean is:

in this graph, player 1 has to move left, since 0 is his goal. Now, player 2 can move left next which gives him a chance to get to 4, however, it could also get him to 0. if he moves right, he guarantees at least a 1.

So does it mean that to play optimally, player 2 would go right in his first move, even tough he has "a chance" of getting four if he goes the other way?

Answer 1

The meaning of an optimal strategy (here: Nash equilibrium) is that if one of the players diverges from the strategy he will get worse results. Since both player try to do their best, it makes no sense to hope that the opponent makes an error. Thus players try to optimize the worst case.

The graph has to be solved bottom up: in the last row, it is pretty clear that player 2 chooses always the better alternative.

In the third row, player 1 tries to maximize his worst case results, thus choosing (from left to right) R-L-R-R.

The action in the second row is now more difficult to compute. From above, we know all decisions further down, thus the we can predict the outcome of each move: first pair: L$\to0$, R$\to1$, second pair: L$\to2$, R$\to3$. So player 2 would choose always choose R in his first move.

For the first move: L would give $1$, R would give $3$, so player 1 chooses first L.

The actual game is then L-R-L-L, with result 1.

Answer 2

I would agree that optimally is ill-defined here.

The first definition you played with I would call greedy. In this case it would go LLR then either L or R with 0 being the result. The other way I would say is by average outcome. That is a player chooses the direction where the sum of the nodes is the highest (or lowest) in that direction. This ends up being less well defined as on $P_2$'s first turn both directions have sum of 6. As the question is expected to have a solution this must not be the correct definition.

Next we could the player being safe (ie avoid the worst case scenario). In this case the first move is ill defined so this must also not be our definition.

We could similarly to what you had purposed do a hybrid where we choose by average and decided with safe (we could do the same with greedy but we would get the same as greedy alone). This leads to LRLL with a cost of 1.

Finally we get to what I would call "optimally" that the players know everything their opponents are likely to do. $P_1$ does not benefit much this as he should still choose L first because the outcomes of L are 1 or 0 which is as good as it gets for him. Now we get to decision 2 where $P_2$ would like the 4 or 2 outcome that L offers him but knows that $P_1$ will definitely choose R if he does that resulting in 0. He also knows he gets the last say so if he chooses R here he will get at least 1. So I would say a cost of 1 is the correct answer here.

Answer 3

Other posts are great +1 for them, but it still took 30 mins to get the whole and missing parts to automate it to a computer program, so adding a comm wiki here:

1. Picture representation of the play

P1(min)                                   1*
P2(max)                  1*                                 3           
P1(min)            0            1*                   2             3
P2(max)         4     0     1*     3             3      2      4      3
A[0]           4 2   0 0   1 0    3 2           2 3    1 2    4 1    3 2

Above, we have to do bottom-up.

2. One question remains though:

Since we need to do bottom-up, who plays 1st while playing bottom-up?

Here, since the P1 plays 1st from (top-down), we need find who will play first if bottom-up.

So calculate Math.ceil(Math.log2(N))
If EVEN, OTHER player (P2) plays first when bottom-up.
If ODD, SAME player (P1) plays first when bottom-up.

N = number of costs/leafs = 16 here
Math.ceil(Math.log2(16)) = 4
4 is EVEN
so P2 plays first from bottom-up

If costs/leafs were only 9
then also it is 4
P2 plays first

If costs/leafs were only 8
then it is 3
P1 (same player this time) plays first

Please update this post if anything is anything.