How to play the Majority game with a liar

The Majority   game is played by a questioner (Q) and an answerer (A). A holds nn elements, each of which can be labeled as 00 or 11. 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∗q∗ denote the minimal number of questions needed for Q to identify a Majority element regardless of A’s answers.In this paper we investigate upper and lower bounds for q∗q∗ in a variation of the Majority game, where A is allowed to lie   up to tt 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).