1
$\begingroup$

Suppose I have $k$ players $P_1,\dots,P_k$ that can communicate with each other directly by sending messages.

For defining the inputs, we consider a fixed set of names $N$ which are integers in $[1,k^2]$. The input of each player $P_i$ consists of a unique name chosen from $N$ and a set $X_i$ of (up to $k-1$) other integers from $N$. Note that some elements of $X_i$ might refer to names that have been assigned to other players while others are just arbitrary names that weren't assigned to anyone. Each player $P_i$ only knows its own name and its own input and has no idea regarding the inputs and names of the other players, but it can communicate with every player $P_j$ by sending a message to $P_j$ (even without knowing $P_j$'s name).

The goal of the players is to discover at least one of the name (if it exists) that is part of the input set $X_j$ of some player $P_j$ but does not refer to a name assigned to one of the players.

A trivial algorithm for this would simply be each of the $k$ players sending their names and name-sets to $P_1$ and $P_1$ can compute the answer, requiring $O(k^2\log k)$ bits in total.

Intuitively, we could think of the $k$ players as a group of people each of whom knows a list of other people and they would like to discover the name of at least $1$ person who is not part of this group.

Is there a name for this problem of finding the "odd guy out"?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.