My IIT Login
IIT.EDU HOME
    Inquire

    An Improved Liar Game Strategy From a Deterministic Random Walk

    Robert Ellis

    Department of Applied Mathematics
    Illinois Institute of Technology

    A liar game is a 2-person perfect information played by Paul and Carole in which Paul uses Yes-No questions to find a distinguished element known by Carole, and Carole is allowed to lie a prescribed number of times.  Liar games were introduced by Renyi and Ulam, and in an equivalent form, by Berlekamp.  In the pathological variant, Paul plays to preserve possibilities for the distinguished element, while Carole plays to disqualify all possibilities.  The original and pathological variants are equivalent to adaptive error-correcting and adaptive covering codes, respectively.  We introduce a deterministic random walk called the "linear machine," compare its behavior to the simple random walk on the integers, and use the result to improve the best-known strategy for Paul in the pathological variant when the number of lies is a constant fraction of the total number of questions.  Included in this talk is an overview of liar games and deterministic random walks.

    26 October, 2009  E1  106 4:40 pm

    © Illinois Institute of Technology
    Applied Mathematics Office, Engineering 1 Building 10 West 32nd Street, Chicago, IL 60616, Tel 312.567.8980, Fax 312.567.3135
    Undergraduate Admission: 800.448.2329 || Graduate Admission: 312.567.3020   Emergency Information