Ulam's pathological liar game with one half-lie

Robert B. Ellis and Catherine H. Yan

International Journal of Mathematics and Mathematical Sciences, 2004, vol. 2004, 1-10

Abstract:

We introduce a dual game to Ulam's liar game and consider the case of one half-lie. In the original Ulam's game, Paul attempts to isolate a distinguished element by disqualifying all but one of n possibilities with q yes-no questions, while the responder Carole is allowed to lie a fixed number k of times. In the dual game, Paul attempts to prevent disqualification of a distinguished element by “pathological” liar Carole for as long as possible, given that a possibility associated with k + 1 lies is disqualified. We consider the half-lie variant in which Carole may only lie when the true answer is “no.” We prove the equivalence of the dual game to the problem of covering the discrete hypercube with certain asymmetric sets. We define A 1 * ( q ) for the case k = 1 to be the minimum number n such that Paul can prevent Carole from disqualifying all n elements in q rounds of questions, and prove that A 1 * ( q ) ~ 2 q + 1 / q .

Date: 2004
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/2004/826163.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/2004/826163.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:826163

DOI: 10.1155/S0161171204306204

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().