0
$\begingroup$

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:

  1. 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?
  2. 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.

$\endgroup$
  • $\begingroup$ What are the rules of the game? How do players capture intervals? $\endgroup$ – Ross Millikan Sep 8 '18 at 19:10
  • $\begingroup$ Original rules are: Players A,B,C chose numbers in the interval (0,1). They choose different numbers. Then the referee chooses a number randomly ( from uniform distribution). The player who is closest to this random number wins. $\endgroup$ – Ant Sep 8 '18 at 19:19
  • $\begingroup$ In order not to deal with numbers, which are real, I decided to discretize the problem. Lets say we have 2 players A and B. We have queue of 10 balls: oooooooooo. If player A chooses third ball:ooAooooooo and the player B chooses ninth ball: ooAoooooBo A controls 2 balls from the left side. The 5 balls shared by A and B will be divided equally. So lets say 2 balls go to A, 2 balls go to B and 1 ball is controlled by neither of them. Finally B controls 1 ball at the right. To sum up, we get A = 4, B = 3. This is my attempt to "discretize" and the interval is my queue of balls. $\endgroup$ – Ant Sep 8 '18 at 19:22
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I agree with the logics you suggest, the tricky part is that then in the puzzle it is asked for the strategy for A when we have 4 players :) I was thinking that there is some symmetry. Once we have 2 players, the best for A is get half of the interval and get draw with B. Once we have 3 players the best for A is to get close to 1/3, i.e. it should be a point such that is provides C less appeal to put the point between (0,a) and (a,b) than the (b,1)( similar to what you describe). And for 4 players it should be close to a quarter. But, I do not know how to simulate and show it... $\endgroup$ – Ant Sep 8 '18 at 20:18
  • $\begingroup$ A can’t guarantee any finite interval because B and C could take points just each side of his. That is their optimum response to A taking $1/2$ $\endgroup$ – Ross Millikan Sep 8 '18 at 20:40
  • $\begingroup$ I think we misunderstood each other. Once we have 2 players, each player can reserve at most 1/2, by hitting at the center of the interval. Of course, once we have 3 players, the best strategy for A is not 1/2, as player B will chose e.g. 1/2+$\delta_1$, and player C will chose e.g. 1/2-$\delta_2$. $\endgroup$ – Ant Sep 8 '18 at 20:49
  • $\begingroup$ I was working from the rules you posted. You talk about reserving intervals, but the rules said each person named a number and the intervals were determined from the numbers they named. What is it? When you have multiplayer games it is hard to prevent collusion. If $A$ assumes the others try to maximize their score he can assure $1/4$ by picking $1/4$. If he picks anything else I believe he accepts less if $B,C$ play well, but as I said last time $B$ and $C$ can collude to give $A$ almost nothing. I believe the optimal $3$ player game is the last paragraph in my answer. $\endgroup$ – Ross Millikan Sep 9 '18 at 3:59
  • $\begingroup$ Please look at the second comment under the post question. It is the original problem formulation. When I said each player can reserve at most 1/2 in game of 2 players I meant that the best decision for 2 players will be to choose points close to the center of the interval, hence they each player will reserve 1/2 of the interval. I.e. in case of discrete formulation the best choice for both players is: ooooABoooo, all other options which number ( or the point on interval or ball in the queue) to choose will lead to one of the players to win and other to loose. $\endgroup$ – Ant Sep 9 '18 at 6:54

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.