School of Mathematical Sciences

A ''numbers on foreheads'' game menu

A ''numbers on foreheads'' game

Sune Jakobsen
Wed, 05/11/2014 - 12:00

We consider a game where n people have a randomly (but not independently) chosen natural numbers on their foreheads, and no two player have the same number. The players are not allowed to communicate, but they all know the distribution of the numbers. After seeing the numbers on all the other peoples foreheads, each player can choose two numbers, i and j between 1 and n. The player now wins £1 if the number on his forehead is the i'th smallest, but looses £1 if it is the j'th smallest. We want to choose a distribution such that the players do not win too much in expectation. How well can we do?

We will see that no matter the distribution, the players will always be able to ensure a positive expectation, but for any epsilon, we can choose the distribution such that they have expectation at most epsilon. However, to do this we would need to use numbers as large as 2^{2^{\dots 2^{k_n/\epsilon}}}, where the height of the tower is n-2.

The presentation is based on joint work with Troels B. Sørensen and Vincent Conitzer.