Majority Algorithm

The Prediction Problem

We want to predict a binary sequence $X_t \in {0, 1}$ generated by an all-knowing adversary. At each time step $t$:

The agent observes $Y_{i,t}$, the prediction of expert $i$, for all $i$.
The agent takes action $A_t$ based on expert outputs.
The true value $X_t$ is revealed.

The agent’s goal is to minimize cumulative loss over a horizon $n$:

\[L_n = \sum_{t=1}^n \mathbf{1}\{X_t \neq A_t\}\]

Since the sequence is adversarially generated, we ask: can we guarantee a bound on the worst-case loss?

Assumption: The Perfect Expert

Assumption 1. There exists a perfect expert, i.e., one that always predicts the ground truth.

This is a strong assumption, but it leads to a clean and elegant algorithm.

The idea: maintain a set $S$ of experts who have never made a mistake. At each step, take the majority vote among experts in $S$.

Algorithm 1: Majority Algorithm

Require: Number of experts $K$, horizon $n$

Initialize: $S_0 = {1, 2, \ldots, K}$
For $t = 1$ to $n$ do:
- $A_t = \text{Majority}(Y_{i,t})$ for $i \in S_{t-1}$
- Observe $X_t$
- $S_t = S_{t-1} \setminus {i : Y_{i,t} \neq X_t}$
End for

At each step we take the majority vote of the still-surviving experts and then eliminate those who got it wrong.

Regret Bound

Claim 1.1. The loss under the Majority Algorithm is at most $\log_2 K$.

Proof. Every time the agent makes a mistake, it means the majority voted incorrectly, which implies at least half of the experts in $S$ voted wrong. Those experts are eliminated, so $\lvert S\rvert $ drops by at least a factor of $2$ on each mistake.

Starting from $\lvert S_0\rvert = K$, after $L_n$ mistakes we have:

\[|S_{L_n}| \leq \frac{K}{2^{L_n}}\]

Since $\lvert S\rvert \geq 1$ as long as the perfect expert survives (by Assumption 1), we need:

\[\frac{K}{2^{L_n}} \geq 1 \implies L_n \leq \log_2 K\]

If only one expert makes a mistake at each step, the majority is still correct and the agent never errs. The bound $\log_2 K$ is the worst case when each mistake eliminates exactly half the remaining experts. $\square$

Key Observation

The bound $\log_2 K$ is independent of the horizon $n$. No matter how long the game runs, the agent makes at most $O(\log K)$ mistakes. This is a remarkable guarantee: it is constant in the number of rounds.

This works entirely because of Assumption 1. The perfect expert is never eliminated, so the set $S$ always contains at least one reliable guide.

Limitations

The Majority Algorithm is brittle:

It relies entirely on a perfect expert existing. If no such expert exists, the set $S$ could become empty and the algorithm breaks.
It uses a hard vote: once you make a mistake, you are gone forever. This leaves no room to recover if experts are noisy.

These issues motivate the Weighted Majority Algorithm, which handles the case where no perfect expert exists.