Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2000-12

July 2000

The Telephone Coordination Game

Steve Alpern and Michael Pikounis


In this paper we extend the work of several authors on the `Telephone Coordination Game' originally proposed as follows by the first author: In each of two rooms, there are  n  telephones randomly strewn about. The phones are connected pairwise in some unknown fashion. There is a player in each room. In each period  0,1,2, . . . ,  each player picks up a phone and says `hello', until the first period when they hear each other (called a meeting). The common aim of the two players is to minimize the (expected) number of periods  T  required to meet. The players do not have any common labeling of the telephones on which they can coordinate. Of course a good simple solution to this problem would be for one player to pick up the same phone each period, and for the other to pick different ones each period (a random permutation). However this solution requires the players to determine in advance which role each will take, and we rule out such solutions by requiring a symmetric solution in which both players employ the same mixed strategy.

A compressed (gzip) PostScript file (59 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-2000-12, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2000

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html.