Beautiful answer! I've been trying to compute whether the corresponding Alice strategy is $o(\log n)$: open $\log n / \log \log n$ boxes amongst the first $n(1 + 1/\log n)$ boxes, and open $\log n$ on the remaining boxes (since we the expected boxes we have to open in the worst case have to be $\Omega(\log n)$). This boils down to whether it is possible to generate a scenario in which (1) the probability that Alice goes to the remaining boxes is constant and (2) we placed a constant fraction of the red balls amongst the first set of boxes. This seems unlikely.

Can you clarify? I checked wiki just now and I think I'm using Jensen's inequality in the correct direction ($f(E(x)) \le E(f(x))$). Here I just used $f(x) = (1/3)^x$.

@domotorp: On second comment: That's correct. I thought parametrizing the thing make it more intractable -- if the number of balls were parametrized, I would not be able to prove the $O(\log \log n)$ lower bound, for example. However, if a general solution exists for the parametrized version, it would be more than welcome! However I am not even able to find an optimal strategy for very small values of $n$ (e.g., $n=2$).

@domotorp: On first comment: Yes, the balls are numbered -- ball number $i$ will be the $i$-th ball offered to Alice. However, she has to decide the colors of all balls before Alice is offered any ball (so she cannot change her strategy depending on whether or not Alice takes the first ball, for example). It can be assumed that they pick their strategies independently -- in particular for it to be a Nash equilibrium, no matter which strategy Alice decides to execute, the expected number of balls opened would still be the same.