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 her/his own index $i$ and the total number $n$ of players/locations.
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.
What is the (expected) minimum number of rounds necessary to occupy all locations (where the expectation is taken over the randomization of the strategy, if is not deterministic)? What is the corresponding strategy?