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"?


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.