Revisions to Finding an optimal strategy for a combinatorial sequential game

deleted 7 characters in body

Source Link

edited Dec 15, 2020 at 21:35

83
6

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 randomization of the strategy randomization)? What is the corresponding strategy?

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 randomization of the strategy)? What is the corresponding strategy?

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?

Clarification

Source Link

edited Dec 15, 2020 at 10:08

Let101

83
6

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 freefree 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 randomization of the strategy)? What is the corresponding strategy?

Edit: The sentence "Finally, each player $p_i$ knows the total number $n$ of players/locations, but does not know her/his own index $i$" implies that the strategy of each player must be the same. 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.

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$.

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 randomization of the strategy)? What is the corresponding strategy?

Edit: The sentence "Finally, each player $p_i$ knows the total number $n$ of players/locations, but does not know her/his own index $i$" implies that the strategy of each player must be the same. 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.

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 randomization of the strategy)? What is the corresponding strategy?

added 481 characters in body

Source Link

edited Dec 14, 2020 at 22:04

Let101

83
6

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$.

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 randomization of the strategy)? What is the corresponding strategy?

Edit: The sentence "Finally, each player $p_i$ knows the total number $n$ of players/locations, but does not know her/his own index $i$" implies that the strategy of each player must be the same. 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.

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$.

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 randomization of the strategy)? What is the corresponding strategy?

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$.

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 randomization of the strategy)? What is the corresponding strategy?

Edit: The sentence "Finally, each player $p_i$ knows the total number $n$ of players/locations, but does not know her/his own index $i$" implies that the strategy of each player must be the same. 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.