What One Bit of Communication Enables in a Two-Agent Coordination Game

Two agents want the same thing. Both know the rules. Both are fully cooperative. And they still fail half the time — until someone is allowed to say a single bit.

That gap between aligned incentives and coordinated action is where most multi-agent intuition quietly breaks. We tend to assume that if everyone shares the same reward, the hard part is over. This game shows the hard part is not the reward at all. It is the information partition each agent can condition on, and how much of the state that partition can distinguish.

I like this example because it is small enough to enumerate by hand and sharp enough to predict the exact cost of silence. Let's fix the notation, derive the no-communication ceiling, then add one bit and watch the ceiling move.

The Game, Stated Precisely

Nature draws a state $s$ uniformly from $\{0,1\}$. Both values are equally likely, and there is no other randomness in the environment.

Agent 1 observes $s$. Agent 2 does not. That asymmetry is the entire problem — not incentives, not learning, not scale.

The action sets are guesses: $a_1, a_2 \in \{0,1\}$. The message set is $m \in \{0,1\}$, or the option to send nothing. The payoff is shared and perfectly aligned:

Both agents receive the same payoff. There is no conflict to resolve. The game is one-shot: Nature moves, agent 1 optionally signals, both agents guess simultaneously, and the episode ends. No repeated play, no reputation, no learning dynamics.

A policy here is a mapping from each agent's information to its choice. Agent 1's policy maps $s$ to a message and a guess. Agent 2's policy maps the received message to a guess. Because the state space, action space, and message space are all binary, deterministic policies are sufficient for this analysis — I'll justify that claim in the assumptions section rather than assert it.

Why the No-Communication Baseline Caps at 1/2

Strip out the message. Now agent 2's information set is identical for $s=0$ and $s=1$: it knows the rules and nothing else. Any deterministic policy for agent 2 must therefore output the same guess in both states. Call that fixed guess $g \in \{0,1\}$.

Agent 1, by contrast, still observes $s$. So agent 1's policy can be state-contingent: it may guess $a_1(0)$ in state 0 and $a_1(1)$ in state 1, and those two guesses need not match. This is the detail that makes the baseline derivation worth doing carefully, because it is easy to accidentally restrict agent 1 to a constant guess and then "prove" a ceiling that was never actually forced.

Fix agent 2's constant guess $g$. Agent 1's best response is to guess $s$ exactly, since success requires $a_1 = a_2 = s$, and agent 1 knows $s$. Under that best response, success occurs precisely when $s = g$. Since $s$ is uniform over two values, this happens with probability $1/2$.

Now check whether agent 1 could do better by choosing something other than $a_1 = s$. If agent 1 guesses $1-s$ instead, success requires $1-s = g = s$, which is impossible. If agent 1 guesses a constant $c$, success requires $c = g = s$, which holds only when $s$ equals that shared constant — again probability $1/2$ at best. So for any fixed $g$, agent 1's maximum success probability is $1/2$, achieved by guessing $s$.

Agent 2 has only two choices for $g$, and both yield the same ceiling. The best achievable joint success probability is therefore $1/2$. Randomization cannot rescue it: any mixture of policies whose individual success probabilities are at most $1/2$ has success probability at most $1/2$.

The ceiling is an information constraint, not a strategic one. Both agents are already doing everything a cooperative pair can do — agent 2 simply cannot tell the two worlds apart, and no choice of guess can compensate for that.

Note: This is the same structural failure that shows up in decentralized execution. If two agents share a reward but not an observation, the reward alignment buys you nothing until the observation gap is closed.

Adding One Bit: The Signaling Policy That Reaches Certainty

Now give agent 1 a one-bit channel. Define the policy:

• Agent 1 sends $m = s$.
• Agent 2 guesses $a_2 = m$.
• Agent 1 guesses $a_1 = s$.

Trace both states.

If $s = 0$: agent 1 sends $m = 0$, agent 2 guesses $0$, agent 1 guesses $0$. Both guesses equal $s$. Payoff 1.

If $s = 1$: agent 1 sends $m = 1$, agent 2 guesses $1$, agent 1 guesses $1$. Both guesses equal $s$. Payoff 1.

Success probability is 1 for every realization, so expected payoff is 1. The message is a faithful encoding: the one-bit channel has exactly enough capacity to distinguish the two states, and agent 2's policy can condition on the message.

Same two agents. Same action sets. One extra channel. The ceiling moves from $1/2$ to $1$.

What the One Bit Actually Buys

The numeric jump from $1/2$ to $1$ is not a coincidence of small numbers. It is a change in the set of feasible policies.

Before communication, agent 2's information partition is $\{\{0,1\}\}$ — one cell containing both states. After communication, it is $\{\{0\},\{1\}\}$ — two cells, one per message. A policy is feasible only if it is measurable with respect to the agent's information: it must assign the same action to every state inside a single information cell. Communication splits one cell into two, and that split is what makes the correct action reachable.

The gain is not "more information" in the abstract. It is the ability to condition the guess on the state through a proxy the receiver can actually observe.

Common mistake: Treating the result as a general law — "one bit solves binary coordination." It does not. The result is a capacity match: one bit distinguishes two states, and there are exactly two states. With three or more states, one bit cannot separate them all, and the achievable success probability drops below 1. The clean answer is a property of this game's size, not a universal rule.

Assumptions That Hold the Result Together

The derivation is valid under specific conditions. Each one, when broken, changes the answer.

Perfectly aligned payoffs. Any misalignment turns this into a signaling game with incentive-compatibility constraints. Agent 1 might prefer to misreport, and the achieving policy may no longer be an equilibrium. Truthful signaling is optimal here precisely because both agents want the same outcome.

Noiseless channel. If the bit flips with probability $\epsilon$, agent 2 guesses wrong whenever the flip occurs, and success drops to $1 - \epsilon$. The channel's reliability is part of the capacity story.

Truthful observation. Agent 1 must actually observe $s$. If its observation is corrupted, the message encodes noise, and the receiver inherits the error.

One-shot, simultaneous play. Repeated interaction introduces reputation, punishment, and learning dynamics that this static analysis excludes. The clean $1/2 \to 1$ comparison assumes a single round.

Deterministic policies suffice. In this specific game, stochastic policies add nothing. Agent 2's best response to any message is a single guess; mixing over guesses can only lower expected payoff when one guess is strictly correct. The same argument applies to agent 1's signaling.

No communication cost. If sending a message carries a penalty, the comparison becomes a cost-benefit calculation rather than a pure feasibility question. The bit is free here; in real systems it rarely is.

From This Toy Game to Real Communication Constraints

This game isolates one variable: channel capacity versus state-space size. That is its whole value. Real systems add noise, cost, partial observability, and agents who are themselves learning — which is why learned communication protocols exist rather than hand-designed ones. When the state space is large and the channel is narrow, the design problem becomes which distinctions to preserve and which to drop.

The feasibility logic recurs everywhere: a message is useful only if it refines the receiver's information partition in a way that changes the optimal action. A message that arrives but cannot alter a decision is bandwidth spent for nothing.

Before adding communication to a coordination problem, ask two questions. Can the channel distinguish the states that actually change the optimal action? And can the receiver's policy condition on the message once it arrives? If either answer is no, the channel will not buy you coordination — no matter how aligned the rewards are.

Then perturb the game and re-derive. Add a third state and watch one bit fall short. Flip the bit with probability $\epsilon$ and compute the new success probability. Make the payoffs misaligned and check whether truthful signaling survives as an equilibrium. Each perturbation tells you which assumption was load-bearing, and that is the skill worth carrying into larger multi-agent systems.