Playing the majority game with boolean formulae

Wildon's Weblog 2021-09-26

In the majority game, there are $n$ numbered balls, each either black or white. One knows that black balls are in the majority. At each step, one may ask

‘are balls $i$ and $j$ the same colour’

and get a truthful answer. How many questions does it take to find a black ball? This problem was first solved by Saks and Werman, who proved the elegant result that $n-B(n)$ questions are necessary and sufficient, where $B(n)$ is the number of $1$ s in the binary form of $n$ .

It is a nice exercise to find a questioning strategy that meets this target: if you discover something fundamentally different to the ‘Binary Knight Hunt’ from Section 2 of this paper, I would like to know about it! (Incidentally, the name of this strategy comes from a different setting for the problem in which black balls become Knights, who always tell the truth, white balls become Knaves, who always lie, and a comparison between balls $i$ and $j$ becomes the question `Person $i$ , is Person $j$ a knight?’.) The harder part of the Saks—Werman result is that $n-B(n)$ questions are necessary. This part was later generalised by John Britnell and me to the case where black balls outnumber white balls by a specified excess.

A related problem asks for the minimum number of questions to identify the colour of every ball. After the first question in the Binary Knight Hunt when a black ball is known, the question graph is a forest: turning it into a tree by connecting the component of the known black ball to all other components identifies all the balls in $n-1$ questions (recall that a tree on $n$ vertices has $n-1$ edges). When $n$ is odd, there are $2^{n-1}$ possible sets of black balls (for each partition $\{1,\ldots, n\} = A \cup B$ one may colour the larger set black), and so we must learn $n-1$ bits of information. Therefore this strategy is optimal. For even $n$ the same result holds, but requires a bit more work to prove: see Theorem 4 in this later paper of mine.

The majority game for a boolean function

To state the intended generalisation we need some more notation. Let $a_i$ be the colour of ball $i$ , identifying black with $0$ and white with $1$ . A comparison of ball $i$ with ball $j$ reveals $a_i + a_j$ . This is $F(a_i,a_j)$ where $F$ is the two-variable boolean formula

$F(x,y) = x + y.$

In this post we present some preliminary results on generalizations of the majority game in which $f$ is replaced with an arbitrary boolean formula.

Note that, in the original game, we cannot know for sure a ball is of the minority colour unless it has been compared with a ball known to be of majority colour. This observation has no analogue when comparison is replaced with evaluation of an arbitrary boolean formula. For each boolean formula we therefore have three variants of the majority game.

Find a ball of known colour.
Find a ball of the majority colour.
Find the colour of every ball.

For simplicity we shall assume from now on that $n=2m+1$ is odd.

Linear formulae

The relevant formulae are $F_\ell(x_1,\ldots,x_{\ell}) = x_1 + \cdots + x_\ell$ . We immediately note that if $\ell$ is odd then $F_\ell(a_i,\ldots, a_i) = a_i$ , and so we can determine a ball’s colour in just one evaluation, making (1) trivial. For (2), the first $m$ questions may find white balls, so $m+1$ evaluations are necessary and sufficient. For (3) the obvious strategy uses $n$ questions.

Problem 1 Is it possible, using $F_\ell$ when $\ell$ is odd, to find the colour of every ball using $n-1$ evaluations?

At attempt to block this strategy by requiring the argument of $f$ to be distinct is easily subverted, provided that $n \ge 2\ell - 1$ . (Equivalently, $m \ge \ell-1$ .) Begin by evaluating $F(a_1,\ldots,a_{\ell-1},a_k)$ for $\ell$ distinct choices of $k \in \{a_\ell, \ldots, a_n)$ . Order the results so that

$a_1 + \cdots + a_{\ell-1} + a_{i_1} = \cdots = a_1 + \cdots + a_{\ell-1} + a_{i_s} = 0$

and

$a_1 + \cdots + a_{\ell-1} + a_{j_1} = \cdots = a_1 + \cdots + a_{\ell-1} + a_{j_t} = 1.$

Since $s+t = \ell$ , exactly one of $s$ and $t$ is odd. If it is $s$ then $a_{i_1} + \cdots + a_{i_{s-1}} + a_{j_1} + \cdots + a_{j_t} = 0$ ; if it is $t$ then $a_{i_1} + \cdots + a_{i_s} + a_{j_1} + \cdots + c_{j_{t-1}} = 0$ . Therefore we obtain $\ell-1$ variables $a_{k_1}, \ldots, a_{k_{\ell-1}}$ such that $a_{k_1} + \cdots + a_{k_{\ell-1}} = 0$ . Since

$F(a_{k_1}, \ldots, a_{k_{\ell-1}}, a_r) = a_r$

we are again in the happy position of being able to learn a ball’s colour with a single evaluation. This gives a strategy for game (1) using $\ell+1$ evaluations. For game (2) we use $\ell + m$ evaluations $F(a_{k_1}, \ldots, a_{k_{\ell-1}}, c)$ for $m+1$ distinct $c$ , each not equal to any of $a_{k_1}, \ldots, a_{k_{\ell-1}}$ ; this is possible since $m+1 + (\ell-1) \le m+1 + m \le n$.

Problem 2 Find optimal strategies for games (1), (2) and (3) using $F_\ell$ when repeated arguments are disallowed.

Problem 3 Show that game (1) cannot be won if $n \le 2\ell - 2$ .

When $\ell$ is even one can use a similar trick to reduce to the case $\ell=2$ by using $\ell-1$ questions to find balls $k_1, \ldots, k_{\ell-2}$ such that $a_{k_1} + \cdots + a_{k_{\ell-2}} = 0$ ; then

$F(a_{k_1}, \ldots, a_{k_{\ell-2}}, a_i, a_j) = a_i + a_j.$

Problem 4 This reduction shows that games (1) and (2) can be solved in $\ell-1 + 2m - B(m)$ questions and game (3) in $\ell - 1 + 2m$ questions. Are these bounds optimal?

One could also ask the analogue of Problem 4 with repeated arguments disallowed, but (3) in particular seems to have a somewhat technical flavour. The results so far suggest that games (1) and (2), with repeated arguments permitted, are the most appealing.

Majority vote

An important example of a non-linear boolean function is the $3$ -way majority vote function $M(x,y,z) = xy + yz + zx$ . Since $M(x,x,x) = x$ , we must require distinct arguments to get an interesting problem. With this condition, observe that if $m(x,y,z) \not= m(x,y,z')$ then $x \not= y$ , and now $M(x,y,w) = w$ for any $w$ . This suggests the following strategy: evaluate $M$ at disjoint triples $a_i, a_j, a_k$ until one sees both possible results. Let $M(u,v,w) \not= M(u',v',w')$ . Now, interpolating between the sets by evaluating $M(u,v,w')$ and $M(u,v',w')$ , one can find $x$ and $y$ with $x \not= y$ . As above, one further question will win game (1) and one can use very similar ideas to win games (2) and (3).

Unfortunately, if there are few white balls, it may take many evaluations to find a triple in which white balls are in the majority. For instance, suppose that $n=2^4-1 = 15$ and there are just two white balls. We identify $\{1,\ldots, 15\}$ with $\mathbb{P}\mathbb{F}_2^4$ and cover the $2$ -subsets of points of $\latex \mathbb{P}\mathbb{F}_2^4$ using the $\binom{4}{2}_2 = (2^4-1)(2^4-2)/(2^2-1)(2-1) = 35$ lines in $\mathbb{P} \mathbb{F}_2^4$ . Since any two points lie on a unique line, this strategy is optimal. Still it requires $35$ evaluations. Generally if $n=2^r-1$ then there are $O(n^2)$ lines, and so $O(n^2)$ evaluations may be necessary. Thus the attractive feature of the majority game (and related Knights and Spies problems) that only $O(n)$ questions are needed is lost.

It therefore seems natural to require that there are exactly $m$ white balls and $m+1$ black balls. Suppose, again for simplicity, that $m = 2p+1$ is odd. If we evaluate $M$ at $p$ distinct triples (using $3p$ of the $4p+3$ balls) and get $0$ every time, then we have used up at least $2p$ black balls and at most $p$ white balls. Hence any remaining triple must have white balls in the majority. This gives a strategy for games (1) and (2) using $n/4 + O(1)$ questions, and for game (3) using $5n/4 + O(1)$ questions.

Problem 5 Are these strategies optimal?

Problem 6 Generalize to the majority-vote function with any odd number of variables.

The majority game with $q$ -ary functions

Another generalization that might be of interest is to allow $q$ different colours, labelled by elements of $\mathbb{Z}/q\mathbb{Z}$ , with strictly more than $n/q$ balls of colour $0$. We now interpret $+$ as addition in $\mathbb{Z}/q\mathbb{Z}$ . Note this is not the same as the ‘plurality problem’ considered for three colours in this paper of Martin Aigner, Gianluca De Marco, Manuela Montangero, in which the result of a comparison is the familiar ‘same’ / ‘different’ from the majority game, rather than ‘0 so same’, ‘1 so different’, ‘2 so different’ as here. The authors’ main result is that $3 \floor n/2 \rfloor - 1$ and $\lfloor 5n/3 \rfloor -2$ comparisons are necessary and sufficient to find a black ball.

Problem 7. Since $\log_2 q$ bits of information are learned in each evaluation, we can expect that fewer evaluations are necessary. What are optimal strategies for each game?

Finally one could consider a combined generalization in which an arbitrary function $G : \mathbb{Z}/p\mathb{Z}^t \rightarrow \mathbb{Z}/p\mathbb{Z}$ is evaluated.