2
$\begingroup$

We are given a set $\{p_1, p_2, \ldots, p_n\}$ of players and a set of $\{\ell_1, \ell_2, \ldots, \ell_n\}$ of locations, where $n\in\mathbb{N}$. Each location can be either free or occupied, and each user can be either looking for a free location or s/he has already occupied a location. The goal of each player is to occupy a free location, and they cannot to communicate with each other. Finally, each player $p_i$ knows the total number $n$ of players/locations, but does not know her/his own index $i$. Each player must use the same (randomized) strategy.

The game consists of a series of rounds. Initially all locations are free. At each round $r_1, r_2, \ldots$, each player $p_i$ who has not occupied a location yet, selects an integer $j\in\{1, 2, \ldots, n\}$ and attempts to occupy $\ell_j$. For each of such players, only two mutually exclusive events are possible:

  • If $\ell_j$ is free and during the current round no other player choses $j$, then $p_i$ occupies $\ell_j$ starting from the current round;
  • $p_i$ does not occupy $\ell_j$.

In both cases, each player receives only one bit of information corresponding to the realization of either the former or the latter event. Hence, if two or more players select the same location $\ell_j$ during the same round, no player can occupy $\ell_j$ until the next round (without knowing if it was already occupied in a previous round or there is a conflict in the attempt of occupying it).

What is the expected minimum number of rounds necessary to occupy all locations (where the expectation is taken over the strategy randomization)? What is the corresponding strategy?

Improve this question
$\endgroup$
13
  • $\begingroup$ 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. $\endgroup$
    – James Martin
    Commented Dec 14, 2020 at 21:20
  • $\begingroup$ 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. $\endgroup$
    – Let101
    Commented Dec 14, 2020 at 21:31
  • 2
    $\begingroup$ @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? $\endgroup$
    – Timothy Chow
    Commented Dec 16, 2020 at 4:16
  • 1
    $\begingroup$ @Let101 : If you have no application in mind, then I would say that the problem is interesting if the solution is interesting. $\endgroup$
    – Timothy Chow
    Commented Dec 16, 2020 at 14:06
  • 1
    $\begingroup$ @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. $\endgroup$
    – domotorp
    Commented Dec 18, 2020 at 7:01

0

Reset to default

You must log in to answer this question.