There is an interval and say 3 players. Each player wants to capture the biggest subinterval, and each successive player can influence the subinterval gained by previous players. We want to find the best way to choose the subinterval for the first player(player A). I think we can write the problem something like this for 3 players: $$\max l_C | ( \max l_B | \max( l_A ) ) $$ $l_i$ - subinterval of the i-th player.
This puzzle looks like a problem from game theory domain. I have several players, which act one after another. They have a common resource they compete on. There is no cooperation. There is full information. But I never took a Game Theory course, nor I found anything meaningful online about it, except overview of the common problems with the closest problem about the cake. I have tried to write the puzzle as a Linear Programming (LP) problem: $$ \max l_A - (l_B+l_C)$$ but this is sick, as we want something like: $$\max l_B | \max l_A $$ i.e. player A chooses some good subinterval, then B chooses based on decision of A, best possible option and: $$\max l_C | ( \max l_B | \max l_A ) $$ finally the player C chooses after A and B, maximizing his own subinterval. The rest of conditions seems easy: $$\sum L_i = c_1$$ i.e. we have a one resource of fixed size and other reasonable constraints $$ L_i \in (0, c_1) \text{ for } i \text{ in } A,B,C, \text{ and } c_i - \text{ constants } $$
Unfortunately, while using Python library's cvxpy I get errors like:
status: infeasible
I was also looking at the problem as backward induction but did not get that far. Currently, I am reading a bit about minimax algorithm, but still have doubts how to implement it for N players setup. So, the questions are:
- is there any sense to think about the Linear Programming formulation of this problem? Or it does not capture the feature of the gradual optimization?
- Is there any paper/ tutorial, for "simple" people, on how to implement N-player minimax algo? (I am reading AN ALGORITHMIC SOLUTION OF N-PERSON GAMES by Luckhardt and Irani, but need more kids tutorial how to do it in my case)
EDIT: I can add my idea on how the subintervals are computed, but I think it does not matter that much and will only take space here.
First look at $C$’s move. Let $A$ choose $a$ and $B$ choose $b$. We can assume $a \lt b$, otherwise reverse them. $C$ can get (just less than) $a$, (just less than) $1-b$, or $(b-a)/2$. Those leave $B$ with $(1-a)/2, (b-a)/2, (1-c)/2$. If $a$ is at least $1/4$, $B$ should take just over $1-a$, and $C$ will move just below $a$. If $a \lt 1/4, B$ should take $2(1-a)/3$ so $C$ will move in the middle. If $C$ moves in the middle, he gets $(b-a)/2$ regardless of where he moves, but he gets to choose how the chances are distributed between $A$ and $B$. I don’t think we can give $A$ a good strategy because of the uncertainty.
If $A$ takes $1/4, B$ takes $3/4+, C$ moves in the middle. $C$ gets $1/4+$, $A$ gets $1/4, B$ gets $1/4-$ and there is $1/4+$ that $C$ gets to distribute between the others.