How to Play the Majority Game with Liars

摘要

The Majority game is a two player game with a questioner Q and an answerer A. The answerer holds n elements, each of which can be labeled as 0 or 1. The questioner can ask questions comparing whether two elements have the same or different label. The goal for the questioner is to ask as few questions as possible to be able to identify a single element which has a majority label, or in the case of a tie claim there is none. We denote the minimum number of questions Q needs to make, regardless of A's answers, as q~*. In this paper we consider a variation of the Majority game where A is allowed to lie up to t times, i.e., Q needs to find an error-tolerant strategy. In this paper we will give upper and lower bounds for q~* for an adaptive game (where questions are processed one at a time), and will find q~* for an oblivious game (where questions are asked in one batch).