How to play the Majority game with a liar

The Majority game is played by a questioner ( Q ) and an answerer ( A ). A holds n elements, each of which can be labeled as 0 or 1 . Q is trying to identify some element A holds as having the Majority label or, in the case of a tie, claim there is none. To do this Q asks questions comparing whether two elements have the same or different label. Q ’s goal is to ask as few questions as possible while A ’s goal is to delay Q as much as possible. Let q ∗ denote the minimal number of questions needed for Q to identify a Majority element regardless of A ’s answers. s paper we investigate upper and lower bounds for q ∗ in a variation of the Majority game, where A is allowed to lie up to t times. We consider two versions of the game, the adaptive (where questions are asked sequentially) and the oblivious (where questions are asked in one batch).