Timeline for Finding an optimal strategy for a combinatorial sequential game
Current License: CC BY-SA 4.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 18, 2020 at 7:01 | comment | added | domotorp | @Timothy I doubt choosing a number uniform at random in each round would be optimal. Suppose that we have already reached the state where $n-1$ locations are occupied (which we of course cannot know in the real game, but let's suppose we do). Then for the $n$-th player it's better to always pick a new number than to try an older one. | |
| Dec 16, 2020 at 14:06 | comment | added | Timothy Chow | @Let101 : If you have no application in mind, then I would say that the problem is interesting if the solution is interesting. | |
| Dec 16, 2020 at 12:49 | comment | added | Let101 | @TimothyChow this is something I was thinking about. I will add it when I will find it. Thank you for your message. By the way, do you think that the problem becomes more interesting if each player can always distinguish between an attempt to occupy the same location chosen by another player during the same round, and a location which was already occupied in the previous rounds? | |
| Dec 16, 2020 at 4:16 | comment | added | Timothy Chow | @Let101 : Your question could be improved if you did a few calculations. For example, what is the expected waiting time if all players adopt the obvious strategy of choosing a number uniformly at random in every round? Do you have an example, for some small value of $n$, where this obvious strategy is not optimal? | |
| Dec 15, 2020 at 21:35 | history | edited | Let101 | CC BY-SA 4.0 |
deleted 7 characters in body
|
| Dec 15, 2020 at 10:08 | history | edited | Let101 | CC BY-SA 4.0 |
Clarification
|
| Dec 14, 2020 at 22:26 | comment | added | Let101 | Thank you @JamesMartin . For the moment, I would start to focus on (i). I just added a question in the "Edit section" about the problem itself: I am now wondering whether the problem becomes more interesting if each player can always distinguish between an attempt to occupy the same location chosen by another player during the same round, and a location which was already occupied in the previous rounds. | |
| Dec 14, 2020 at 22:18 | comment | added | James Martin | For example for n=2 the best strategy of type (ii) is for one player to always switch after round 1 and the other to always stay in the same place. For higher n there are different notions of symmetry over the locations you could consider. You could ask for the strategies to be invariant under any permutation of the locations; or something weaker like that they are invariant under rotations. The second case would allow for example some players to search clockwise, while others search anticlockwise. | |
| Dec 14, 2020 at 22:13 | comment | added | James Martin | Yes, I would suggest two different problems might be interesting: (i) the strategies must all be the same (but may treat different locations differently); (ii) the strategies may be different for different players, but everyone's strategy must be symmetric over the locations (so indeed everyone's choice of location on round 1 is uniformly random, but thereafter maybe some players are more likely to stick in the same place several rounds in a row, and others are more likely to jump around). | |
| Dec 14, 2020 at 22:04 | history | edited | Let101 | CC BY-SA 4.0 |
added 481 characters in body
|
| Dec 14, 2020 at 21:57 | comment | added | Let101 | @JamesMartin OK, I see: the strategy of each player may be dependent on the round number, but must be the same. | |
| Dec 14, 2020 at 21:50 | comment | added | Let101 | @JamesMartin how can I formalize the concept that no player knows the strategies of the others? | |
| Dec 14, 2020 at 21:47 | history | edited | Let101 |
edited tags
|
|
| Dec 14, 2020 at 21:43 | comment | added | Let101 | I see your point @JamesMartin. Your doubt is definitely legitimate. Could you please suggest a modification of the problem which makes it non-trivial? Should all the players play the same strategy? | |
| Dec 14, 2020 at 21:39 | comment | added | James Martin | So, the strategy may differ from player to player, but you don't allow the strategy to depend on the index of the player. I'm still not quite sure what the constraint on the strategies is. Does every player's strategy have to be symmetric over all the locations? For example: does every player's choice in the first round have to give probability $1/n$ to each location? | |
| Dec 14, 2020 at 21:34 | history | edited | Let101 | CC BY-SA 4.0 |
deleted 23 characters in body
|
| Dec 14, 2020 at 21:31 | comment | added | Let101 | Thank you, you are right about the misleading sentence on the (possible) determinism of the strategy, because the strategy must be randomized. Now I edit that part of the question. However, I do not understand your statement "[...] if you allow any strategies then of course player $i$ choosing location $i$ on the first round is good" because, for instance, player $p_1$ does not know her/him index ($1$ in this case). Hence, it is not possible to that each player $p_i$ chooses $\ell_i$ on the first round with probability $1$. Anyway, the strategy may differ from player to player. | |
| Dec 14, 2020 at 21:22 | history | edited | James Martin |
combinatorial game theory tag removed
|
|
| Dec 14, 2020 at 21:20 | comment | added | James Martin | By "each player does not know his/her own index $i$, and the players cannot communicate" do you mean that each player must follow the same strategy? Or is it that each player's strategy must be symmetric over the locations (but the strategy may differ from player to player)? If you allow any strategies then of course player $i$ choosing location $i$ on the first round is good. If everyone must use the same strategy, then any deterministic strategy fails for ever (all players always choose the same location) - but your last paragraph suggests that some determinstic strategies are plausible. | |
| Dec 14, 2020 at 20:08 | history | edited | Let101 | CC BY-SA 4.0 |
added 119 characters in body
|
| Dec 14, 2020 at 19:45 | review | Close votes | |||
| Dec 16, 2020 at 1:31 | |||||
| Dec 14, 2020 at 19:44 | history | edited | Let101 | CC BY-SA 4.0 |
added 17 characters in body
|
| Dec 14, 2020 at 19:31 | history | edited | Let101 | CC BY-SA 4.0 |
added 148 characters in body
|
| Dec 14, 2020 at 19:13 | history | edited | Let101 | CC BY-SA 4.0 |
added 10 characters in body
|
| Dec 14, 2020 at 19:08 | history | edited | Let101 | CC BY-SA 4.0 |
added 10 characters in body
|
| Dec 14, 2020 at 18:34 | review | First posts | |||
| Dec 14, 2020 at 20:08 | |||||
| Dec 14, 2020 at 18:29 | history | asked | Let101 | CC BY-SA 4.0 |