The Ulam-Renyi game is a classical model for the problem of determining the min- imum number of queries to find an unknown number in a finite set when up to a finite number e of the answers may be lies. In the variant, we introduce in this paper, questions with q many possible answers are allowed and lies are constrained by a prescribed graph. We essentially solve the problem exact asymptotically un- der some symmetry-hypothesis. All our strategies are implementable by procedures which use adaptiveness only once.
Ulam-Renyi game with constrained lies
CICALESE, Ferdinando;
2005
Abstract
The Ulam-Renyi game is a classical model for the problem of determining the min- imum number of queries to find an unknown number in a finite set when up to a finite number e of the answers may be lies. In the variant, we introduce in this paper, questions with q many possible answers are allowed and lies are constrained by a prescribed graph. We essentially solve the problem exact asymptotically un- der some symmetry-hypothesis. All our strategies are implementable by procedures which use adaptiveness only once.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
