Playing by searching: Two strategies against a linearly bounded liar
type: Item
instance of: scholarly article
title: Playing by searching: Two strategies against a linearly bounded liar
zbMATH Open document ID: 1019.91011
DOI: 10.1016/S0304-3975(01)00071-8
author: Alberto Pedrotti
published in: Theoretical Computer Science
publication date: 2002-07-15T00:00:00Z
review text: The searching problem is formulated and analyzed as a two-players game of questioner and responder. The strategy of the responder consists in choosing an integer from a given finite set, the strategy of the questioner is represented by a sequence of questions aiming to determine the chosen value. The number of such questions is predetermined and the responder can lie in an exactly limited number of his responses. The rate of lies under which the questioner may win the game is known from the literature. The main result of the referred paper regards the lower bound of the number of queries needed for the questioner to win the game even if the arbitrary membership queries are allowed. Two questioning strategies for the case where only comparison queries are allowed are suggested, as well. The first one improves the upper bound of the number of needed queries, the second strategy, moreover, makes sure that each query can be formulated in constant time.
reviewed by: Milan Mareš
Mathematics Subject Classification ID: 91A40
Mathematics Subject Classification ID: 91A46
Mathematics Subject Classification ID: 91A35
zbMATH DE Number: 1767917
zbMATH Keywords: game
zbMATH Keywords: searching game
zbMATH Keywords: comparison query
zbMATH Keywords: error rate
MaRDI profile type: Publication
cites work: Q5568914
cites work: Comparison-based search in the presence of errors
cites work: Q4763384
cites work: Computing with Noisy Information
cites work: Ulam's searching game with two lies
cites work: Optimal comparison strategies in Ulam's searching game with two errors
cites work: Q3128931
cites work: Solution of Ulam's problem on binary search with three lies
cites work: Solution of Ulam's problem on searching with a lie
cites work: Prefix search with a lie
cites work: Searching with known error probability
cites work: Coping with errors in binary search procedures
cites work: Ulam's searching game with a fixed number of lies
cites work: Three Thresholds for a Liar
cites work: Q4121861
description: scientific article; zbMATH DE number 1767917