A non-zero-sum no-information best-choice game

A given number of n applicants are to be interviewed for a position of secretary. They present themselves one-by-one in random order, all n! permutations being equally likely. Two players I and II jointly interview the i-th applicant and observe that his (or her) relative rank is y for I and z for II, relative to i−1 applicants that have already seen (rank 1 is for the best). Each player chooses one of the two choices Accept or Reject. If choice-pair is R-R, then the i-th is rejected, and the players face the next i+1-th applicant. If A-A is chosen, then the game ends with payoff to I (II), the expected absolute rank under the condition that the i-th has the relative rank y (z). If players choose different choices, then arbitration comes in, and forces players to take the same choices as I’s (II’s) with probability Arbitration is fair if p=1/2. If all applicants except the last have been rejected, then A-A should be chosen for the last. Each player aims to minimize the expected payoff he can get. Explicit solution is derived to this n stage game, and numerical results are given for some n and p. The possibility of an interactive approach in this selection problem is analyzed.

The research was supported by the Russian Fund for Basic Research (project 01-01-00126) and Japan Society for the Promotion of Science (grant L 01530).

Authors and Affiliations

1. Prof. Emeritus, Osaka University, 3-26-4 Midorigaoka, Toyonaka, Osaka, 560-0002, Japan

   Minoru Sakaguchi

2. Institute of Applied Mathematical Research, Karelian Research Center of Russian Academy of Sciences, Pushkinakaya st. 11, Petrozavodsk, 185610, Russia

   Vladimir V. Mazalov

Corresponding author

Correspondence to Minoru Sakaguchi.

Manuscript received: July 2003/Final revision received: January 2004

Reprints and permissions