Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Editor's puzzle: identifying the champion

Editor's puzzle: identifying the champion Editor ™s Puzzle: Identifying the Champion VINCENT CONITZER Duke University Solutions should be sent to the editor at conitzer@cs.duke.edu with subject header SIGecom Exchanges Puzzle. The author(s) of the most elegant solution (as judged by the editor) will be allowed to publish his or her or their proof in the next issue of the Exchanges (ties broken towards earlier submissions). To make the solution accessible to a wide audience, try to minimize technical jargon in the proof. The editor will not give any feedback on submitted solutions and ignore any requests for hints, etc. A Japanese prophecy foretells that a champion warrior will emerge, a warrior that is strictly more skillful than any other warrior. A large (but nite) group of warriors has assembled to determine who the champion warrior is. It is common knowledge among these warriors that the prophecy is true, and, moreover, that the champion is among them. To determine the champion, an in nite sequence 1, 2, . . . of rooms with challenges has been set up for them, each one more di ƒcult than the previous. For every warrior i, there is a number ni ∈ {0, 1, . . .} such that the warrior ™s performance will be satisfactory in the rst ni rooms, and unsatisfactory in the remaining rooms. The champion, of course, has the strictly highest ni . Each warrior spends every day in one of the rooms, trying to pass the challenge. All warriors start in the rst room. Every day exactly at midnight each warrior can choose to move on to the next room, or stay in the current room. A warrior is said to qualify for a room if his performance in the previous room was satisfactory. If a warrior ends up in a room for which he is not quali ed then his performance will be not only unsatisfactory, but humiliating. This will cast shame on the warrior ™s family name, which each warrior wishes to avoid at any cost. Therefore, a warrior will move on to the next room if and only if he is completely sure that his performance in the current room is satisfactory. To make matters more di ƒcult, each warrior is unable to (directly) assess whether his own performance in a room is satisfactory. But, each warrior can easily assess whether the performance of any other warrior in the same room is satisfactory (which also implies that they can see who is in the same room). The warriors are quite stern and do not communicate with each other, but it is common knowledge that the warriors are highly intelligent. Will the champion be identi ed? How long does the process take? Where does each warrior end up? Why is the prophecy Japanese? Authors ™ addresses: conitzer@cs.duke.edu http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

Editor's puzzle: identifying the champion

Conitzer, Vincent
ACM SIGecom Exchanges , Volume 8 (1) – Jul 1, 2009
Download PDF
1 page

Loading next page...
 
/lp/association-for-computing-machinery/editor-s-puzzle-identifying-the-champion-haSTgIZfKS
Publisher
Association for Computing Machinery
Copyright
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Subject
Economics
ISSN
1551-9031
DOI
10.1145/1598780.1598792
Publisher site
See Article on Publisher Site

Abstract

Editor ™s Puzzle: Identifying the Champion VINCENT CONITZER Duke University Solutions should be sent to the editor at conitzer@cs.duke.edu with subject header SIGecom Exchanges Puzzle. The author(s) of the most elegant solution (as judged by the editor) will be allowed to publish his or her or their proof in the next issue of the Exchanges (ties broken towards earlier submissions). To make the solution accessible to a wide audience, try to minimize technical jargon in the proof. The editor will not give any feedback on submitted solutions and ignore any requests for hints, etc. A Japanese prophecy foretells that a champion warrior will emerge, a warrior that is strictly more skillful than any other warrior. A large (but nite) group of warriors has assembled to determine who the champion warrior is. It is common knowledge among these warriors that the prophecy is true, and, moreover, that the champion is among them. To determine the champion, an in nite sequence 1, 2, . . . of rooms with challenges has been set up for them, each one more di ƒcult than the previous. For every warrior i, there is a number ni ∈ {0, 1, . . .} such that the warrior ™s performance will be satisfactory in the rst ni rooms, and unsatisfactory in the remaining rooms. The champion, of course, has the strictly highest ni . Each warrior spends every day in one of the rooms, trying to pass the challenge. All warriors start in the rst room. Every day exactly at midnight each warrior can choose to move on to the next room, or stay in the current room. A warrior is said to qualify for a room if his performance in the previous room was satisfactory. If a warrior ends up in a room for which he is not quali ed then his performance will be not only unsatisfactory, but humiliating. This will cast shame on the warrior ™s family name, which each warrior wishes to avoid at any cost. Therefore, a warrior will move on to the next room if and only if he is completely sure that his performance in the current room is satisfactory. To make matters more di ƒcult, each warrior is unable to (directly) assess whether his own performance in a room is satisfactory. But, each warrior can easily assess whether the performance of any other warrior in the same room is satisfactory (which also implies that they can see who is in the same room). The warriors are quite stern and do not communicate with each other, but it is common knowledge that the warriors are highly intelligent. Will the champion be identi ed? How long does the process take? Where does each warrior end up? Why is the prophecy Japanese? Authors ™ addresses: conitzer@cs.duke.edu

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Jul 1, 2009

There are no references for this article.