Printable PDF
Department of Mathematics, University of California San Diego

****************************

Two-batch liar games on a general bounded channel

Abstract:

We consider a 2-person perfect information liar'' game, often called a R\'enyi-Ulam game. The basic game is that of twenty questions'' played between questioner Paul and responder Carole; Paul searches for a distinguished element $x$ in a search space $[n]$ by asking Yes-No questions of the form is $x\in A$'', where $A\subseteq [n]$. Carole responds Yes' or No', lying in up to $k$ responses. The fully off-line game is equivalent to $k$-error-correcting codes. We extend this game to a general channel $\mathcal{C}$ which governs the manner in which Carole may lie. Specifically, given the alphabet $[t]:=\{1,\ldots,t\}$, Paul searches for $x\in[n]$ by partitioning $[n]=A_1\cup \cdots \cup A_t$ and asking for $a$ such that $x\in A_a$. A lie is a tuple $(a,b)\in[t]\times [t]$ with $a\neq b$. The channel $C$ specifies an arbitrary set of lie strings of bounded length $\leq k$ from which Carole may choose a string and intersperse its lies, in order, among her responses. For example, when $t=2$, Carole lies with $(1,2)$ when she responds with 2 (No'') when the correct response is 1 (Yes''). We further restrict Paul to ask his questions in two off-line batches. We show that the maximum size of the search space $[n]$ for which Paul can guarantee finding the distinguished element is $t^{q+k}/(E_k(C){q \choose k})$ as $q\rightarrow\infty$, where $E_k(C)$ is the number of lie strings in $\mathcal{C}$ of maximum length $k$, generalizing previous work of Dumitriu and Spencer, and of Cicalese, Deppe, and Mundici. We similarly solve the pathological liar variant. This is joint work with Kathryn Nyman (Loyola University-Chicago).

Host: Jeff Remmel

AP&M 7321

****************************