Understanding games with multiple access channels

Prelude

This is quite a step up in complexity from my usual posts, but it was part of my coursework as a recent paper presentation, and I was like, "huh, that's kind of insane!". The content here is based on the paper by Leditzky et al.¹, which explores some fascinating intersections between quantum theory, communication networks, and nonlocal games. The overarching theme is this:

Quantum entanglement can boost classical communication rates in multi-user networks.

But to understand this, we need to set up a LOT of building blocks first, starting with multiple access channels.

What is a Multiple Access Channel?

Think about your phone sending a text to a cell tower. This is a simple point-to-point communication scenario. One sender, one receiver. But now imagine you and a friend are both texting the same tower at the exact same time, on the same frequency. How does the tower make sense of both signals? This is the essence of a multiple access channel (MAC).

In information theory, a MAC is one of the simplest network scenarios: two senders, one receiver, and a shared communication medium. It's everywhere: WiFi networks, cellular uplinks, satellite communications. And unlike the single-sender case that Shannon solved (quite elegantly) in 1948², MACs have a richer structure that took decades to fully understand.

The Mathematical Model

Let's formalize this. A two-sender MAC is defined by:

• Input alphabets $\mathcal{A}$ and $\mathcal{B}$ for senders 1 and 2
• An output alphabet $\mathcal{Z}$ for the receiver
• A conditional probability distribution $N(z|a,b)$ describing how inputs get transformed into outputs

The channel takes an input pair $(a, b) \in \mathcal{A} \times \mathcal{B}$ and produces an output $z \in \mathcal{Z}$ according to the probability $N(z|a,b)$. The randomness here captures the noise and interference inherent in real communication systems.

Capacity Region

For a point-to-point channel (one sender, one receiver), we get a single number: the channel capacity. It tells us the maximum rate at which you can reliably transmit information.

But for a MAC, we have two senders, each with their own transmission rate. Sender 1 transmits at rate $R_1$, sender 2 at rate $R_2$. The question isn't "what's the capacity?" but rather "what combinations of $(R_1, R_2)$ are achievable?"

This set of achievable rate pairs forms the capacity region $\mathcal{C}(N)$, a two-dimensional region in rate space. And a natural tradeoff emerges: if sender 1 hogs more of the channel's capacity, sender 2 gets less, and vice versa.

Ahlswede-Liao Characterization

The capacity region was characterized independently by Ahlswede in 1971³ and Liao in 1972⁴. For a product distribution $\pi_A \cdot \pi_B$ on the inputs, we define the region $\mathcal{R}(A,B)$ as all rate pairs satisfying three constraints:

Then the capacity region is:

The convex hull of the union over all product distributions. We'll unpack what these constraints mean.

The Three Constraints

Constraint 1: $R_1 \leq I(A; Z|B)$

This is the conditional mutual information between sender 1's input and the output, given sender 2's input. If the receiver somehow knew exactly what sender 2 was transmitting, how much information could sender 1 get through? This can be thought of as sender 1's "private lane", i.e., the capacity available when sender 2's signal is treated as known side information.

Constraint 2: $R_2 \leq I(B; Z|A)$

The symmetric constraint for sender 2. Same intuition, with just the roles reversed.

Constraint 3: $R_1 + R_2 \leq I(AB; Z)$

The sum rate constraint. This bounds the total information both senders can jointly convey, captured by the mutual information between the joint input $(A,B)$ and output $Z$. Even if each sender individually could transmit more, the channel has a finite total throughput.

The Pentagonal Region

For a fixed product distribution, these three constraints carve out a pentagonal region in $(R_1, R_2)$ space. The capacity region is then the convex hull of all such pentagons as we vary over input distributions.

Why pentagonal? The first two constraints give us upper bounds on $R_1$ and $R_2$ individually (two edges). The third constraint gives a diagonal bound on their sum (one edge). Combined with the trivial constraints $R_1 \geq 0$ and $R_2 \geq 0$, we get five edges. Et voilà! A pentagon.

Why Does This Matter?

So far, this is classical information theory: very beautiful, but well-understood since the 1970s. The capacity region formula tells us exactly what rates are achievable. Case closed?

Well, not really. Never is, right? There are some twists that make MACs far more interesting than they first appear:

1. Computational complexity: Despite having a "computable" formula, actually evaluating the capacity region turns out to be surprisingly hard. The optimization over product distributions is non-convex, and determining whether a rate pair is achievable is NP-hard (this post doesn't cover this).

2. Quantum resources: What if the two senders share quantum entanglement? For point-to-point channels, entanglement doesn't help transmit classical information any faster. But for MACs, something remarkable happens, as entanglement can boost the capacity region beyond what's classically possible (we will cover this!)

To see how entanglement-assisted communication works, we need to take a detour into the world of nonlocal games. And that's where things get interesting.

Nonlocal Games

A nonlocal game is a cooperative game between two players (Alice and Bob) and a referee. The setup is simple:

1. The referee sends a question to Alice and a question to Bob (simultaneously)
2. Alice and Bob each send back an answer
3. The referee checks if their answers satisfy some winning condition

Alice and Bob cannot communicate during the game! They can agree on a strategy beforehand, they can flip shared coins, they can do whatever preparation they want, but once the questions arrive, they're on their own.

Formally, a nonlocal game $G = (X_1, X_2, Y_1, Y_2, W)$ consists of:

• Question sets $X_1$ (for Alice) and $X_2$ (for Bob)
• Answer sets $Y_1$ (for Alice) and $Y_2$ (for Bob)
• A winning condition $W \subseteq X_1 \times X_2 \times Y_1 \times Y_2$

The game proceeds as: referee draws $(x_1, x_2)$, sends $x_1$ to Alice and $x_2$ to Bob, they respond with $y_1$ and $y_2$, and they win if $(x_1, x_2, y_1, y_2) \in W$.

What resources can Alice and Bob share to coordinate their answers? We have two main types:

Classical case: They share randomness, essentially like shared coin flips decided beforehand. Their strategy boils down to functions $f_1: X_1 \to Y_1$ and $f_2: X_2 \to Y_2$, possibly randomized. Given a question, each player deterministically (or probabilistically) produces an answer based only on their own question and the shared randomness.

Quantum case: They share an entangled quantum state $|\psi\rangle$ (or states). When questions arrive, each player performs a measurement on their half of the entangled state to generate their answer. This creates correlations between their answers that are impossible to achieve classically!

The CHSH Game: A Taste of Quantum Advantage

The CHSH game (Clauser, Horne, Shimony, Holt) is the simplest demonstration of quantum advantage that we can analyze.

Setup: Alice and Bob each get a random bit ($x, y$) and must respond with a bit.

Win condition: Their answers should be the same unless both received 1, in which case they should differ.

Try building a classical strategy on the left. You'll find that any assignment that wins three cases must lose the fourth and there's no way around it. The best you can do classically is 75%.

On the right, the quantum strategy does better. Alice and Bob share an entangled state and measure it at carefully chosen angles. When measuring entangled qubits, the probability of getting the same result is $\cos^2(\theta)$ where $\theta$ is the angle between their measurement bases. By choosing angles that are always π/8 apart for the "same" cases and 3π/8 apart for the "different" case, they achieve an 85.4% win rate, which is the Tsirelson bound⁵.

Pseudo-Telepathy Games

So we just saw that CHSH shows quantum outperforms classical strategies. But some games go further, being designed such that the quantum strategy wins every time while the classical one must sometimes fail. These are pseudo-telepathy games⁶ where Alice and Bob appear to read each other's minds perfectly!

The magic square game is the example that the paper uses, so let's dive into that (and with a bit more rigor)!

Magic Square Game

Here's the setup: Alice and Bob are staring at a 3×3 grid. Alice gets told a row, Bob gets told a column, and they each have to fill in their entire row/column with $+1$s and $-1$s. But there is a constraint: Alice's entries must multiply to $+1$, Bob's must multiply to $-1$, and they have to agree on the cell where their row and column intersect.

More precisely, the magic square game $G_{MS}$ (also known as Mermin-Peres⁷) is defined over a 3×3 grid with entries $a_{ij} \in \{+1, -1\}$. Alice receives a row index $r \in \{0,1,2\}$, Bob receives a column index $c \in \{0,1,2\}$. They must output assignments for their row/column respectively, satisfying:

This is technically a binary constraint system (BCS) game over $\mathbb{Z}_2$, but all that really means is: six parity constraints, and we're using $\{+1,-1\}$ multiplication instead of $\{0,1\}$ addition. The six constraints:

Let's multiply all row constraints together: $\prod_{i,j} a_{ij} = (+1)^3 = +1$. Now we multiply all column constraints: $\prod_{i,j} a_{ij} = (-1)^3 = -1$. Both expressions are the product of all nine cells, yet $+1 \neq -1$. Since the constraints are contradictory, there exists no classical assignment of $\pm 1$ values to the cells that satisfies all six constraints simultaneously.

So what's the best Alice and Bob can do here? They can win on 8 of the 9 possible question pairs and accept failure on the ninth, giving $\omega_C = 8/9$.

Quantum Strategy for Magic Square

Yes, classical strategies cannot win this game. However, the Mermin-Peres construction⁸ provides a winning quantum strategy by replacing scalar $\pm 1$ entries with Pauli observables acting on $(\mathbb{C}^2)^{\otimes 4}$.

Alice and Bob share two Bell pairs $|\Phi^+\rangle^{\otimes 2}$, with Alice holding qubits 1,3 and Bob holding qubits 2,4. The observable grid is:

where $X_1 I_3$ denotes $X$ on qubit 1 tensored with $I$ on qubit 3 (suppressing Bob's qubits). Why does this grid work? Four properties:

1. Commutativity within rows/columns: All three observables in any row (or column) pairwise commute, enabling simultaneous measurement.

2. Row products: $\prod_j O_{rj} = +I$ for each row $r$. Since eigenvalues of $\pm I$ are $\pm 1$, the product of measurement outcomes is $+1$.

3. Column products: $\prod_i O_{ic} = -I$ for each column $c$. The product of measurement outcomes is $-1$.

4. Intersection consistency: Alice measuring $O_{rc}$ on qubits 1,3 and Bob measuring the same observable $O_{rc}$ on qubits 2,4 yield identical outcomes, guaranteed by the entanglement correlations of $|\Phi^+\rangle$.

So the quantum winning probability is $\omega_Q = 1$, perfect every time! This works because non-commuting observables can satisfy product constraints that commuting scalars cannot!

Building a Channel from a Game

A MAC and a nonlocal game share the same structural constraint: two parties must coordinate their behavior without communicating. Alice and Bob in a nonlocal game cannot exchange information once questions arrive. The two senders in a MAC cannot coordinate during transmission. We can make use of this parallel and we can construct a MAC directly from any nonlocal game.

The Construction

Given a nonlocal game $G = (\mathcal{X}_1, \mathcal{X}_2, \mathcal{Y}_1, \mathcal{Y}_2, W)$, let's define the MAC $N_G : (\mathcal{X}_1 \times \mathcal{Y}_1) \times (\mathcal{X}_2 \times \mathcal{Y}_2) \to \mathcal{X}_1 \times \mathcal{X}_2$ as follows:

• Alice's input alphabet: question-answer pairs $(x_1, y_1) \in \mathcal{X}_1 \times \mathcal{Y}_1$
• Bob's input alphabet: question-answer pairs $(x_2, y_2) \in \mathcal{X}_2 \times \mathcal{Y}_2$
• Output alphabet: question pairs $(\hat{x}_1, \hat{x}_2) \in \mathcal{X}_1 \times \mathcal{X}_2$

The channel transition probabilities are:

$N_G(\hat{x}_1, \hat{x}_2 | x_1, y_1; x_2, y_2) = \begin{cases} \delta_{x_1}^{\hat{x}_1}\delta_{x_2}^{\hat{x}_2} & \text{if } (x_1, x_2, y_1, y_2) \in W \\ |\mathcal{X}_1|^{-1}|\mathcal{X}_2|^{-1} & \text{otherwise} \end{cases}$

where $\delta_a^b$ is the Kronecker delta and $|\mathcal{X}_i|^{-1}$ is the uniform distribution over $\mathcal{X}_i$. When Alice and Bob's answers constitute a winning response (i.e., $(x_1, x_2, y_1, y_2) \in W$), the channel faithfully transmits the question pair. When they lose, the output is uniform random noise over $\mathcal{X}_1 \times \mathcal{X}_2$.

In our setup, the questions encode the message and the answers serve as a "proof of coordination." The channel quality depends directly on game performance. If we set $A = X_1 Y_1$ and $B = X_2 Y_2$, the mutual information constraining the sum rate satisfies:

$I(X_1Y_1X_2Y_2; Z) = H(Z) - p_L \cdot (\log|\mathcal{X}_1| + \log|\mathcal{X}_2|)$

where $p_L$ denotes the probability of losing the game under the induced strategy. We can see that each loss injects maximum entropy into the output.

Theorem (Leditzky et al.):

If a nonlocal game $G$ admits no perfect strategy using available resources, the sum rate $R_1 + R_2$ of $N_G$ is strictly bounded below $\log|\mathcal{X}_1| + \log|\mathcal{X}_2|$.

This holds regardless of resource type: classical shared randomness, finite-dimensional entanglement, or otherwise. Imperfect game strategies yield imperfect communication.

Capacity of the Magic Square MAC

Now we can be precise about the payoff. The MAC $N_{G_{MS}}$ has:

Thus the maximum possible sum rate is $\log 3 + \log 3 = 2\log 3 \approx 3.17$ bits which is achieved when both senders transmit at $\log 3$ bits each. The best classical magic square strategy wins $8/9$ of the time, so $p_L = 1/9$.

Working through the optimization over input distributions, we have: $R_1 + R_2 \leq 3.13694 \text{ bits (proven upper bound)}$

The authors note that their numerical optimization yields a lower bound on the maximum classical sum rate of about $2.84$ bits, suggesting the true value is much lower than the proven upper bound. With the quantum strategy, $p_L = 0$. The channel becomes noiseless: $R_1 + R_2 = 2\log 3 \approx 3.17 \text{ bits}$

For point-to-point channels, entanglement provides no advantage for classical communication⁹. But we see that MACs are different, as the two-sender structure creates room for entanglement to help by letting the senders coordinate their inputs.

The Magic Square as a Linear System

The magic square game is an instance of a broader class called linear system games¹⁰. A linear system game starts with a system of linear equations $Ax = b$ over $\mathbb{F}_2$ (binary arithmetic). The game works as follows:

• The referee picks an equation $i$ and a variable $j$ that appears in it
• Alice receives the equation index $i$ and must output an assignment to all variables in that equation, satisfying it
• Bob receives the variable index $j$ and must output a value for that variable
• They win if Alice's assignment for variable $j$ matches Bob's value

For a concrete example, consider the system:

If Alice gets equation 1 and Bob gets variable $x_2$: Alice outputs an assignment $(x_1, x_2)$ satisfying $x_1 \oplus x_2 = 0$, say $(0, 0)$. Bob outputs a value for $x_2$, say $0$. They win because both agree that $x_2 = 0$. But can they always win? Adding all three equations gives $0 = 1$, and the system is inconsistent, similar to the magic square example we saw earlier.

The magic square fits this framework exactly. The nine cells $a_{ij}$ are the variables (over $\mathbb{F}_2$, writing $0$ for $+1$ and $1$ for $-1$). The six parity constraints are the equations. Alice receives a constraint (row or column) and fills it in; Bob receives a cell and assigns it a value.

Some classically unsolvable linear systems admit perfect quantum strategies. The observables in the Mermin-Peres construction encode a "solution" in the algebra of quantum measurements, where operators can satisfy product constraints that commuting scalars cannot. This isn't unique to the magic square: any linear system game whose system is inconsistent but whose constraint structure is compatible with quantum observables can exhibit the same phenomenon. We will see what this generalization leads to!

Unbounded Entanglement and Undecidability

The magic square needs just two entangled qubit pairs. But other linear systems can require much more.

Slofstra and Vidick constructed a specific linear system game $G_{SV}$¹¹ where:

• No finite-dimensional quantum strategy wins perfectly
• But the winning probability approaches 1 as entanglement dimension $d \to \infty$

For a $d$-dimensional strategy with losing probability $p_L^{(d)}$:

$C \cdot p_L^{-1/6} \leq d \leq C' \cdot p_L^{-1/2}$

To halve our error rate, we need polynomially more entanglement. To get arbitrarily close to perfect, we need arbitrarily large entanglement.

For the corresponding MAC $N_{G_{SV}}$: the optimal rate pair $(\log m, \log n)$ lives in the closure of the achievable region, but not in the region itself. We can get arbitrarily close with enough entanglement, but never quite reach it with finite resources.

A channel with finite alphabets requiring infinite entanglement for optimal performance. That's... not what we'd expect.

Slofstra proved something even stranger¹²: for general linear system games, determining whether a perfect finite-dimensional quantum strategy exists is undecidable. No algorithm can answer this question for all inputs.

For our MACs built from linear system games, this means that whether the optimal rate pair is achievable with finite entanglement is undecidable. Whether the optimal rate pair of a classical MAC is achievable with finite entanglement can have no algorithmic answer!

Conclusion

What makes this paper clever is the bridge it builds. The construction $G \mapsto N_G$, turning a nonlocal game into a multiple access channel, lets us import results from quantum foundations directly into classical information theory. And we can see how even in classical communication scenarios, quantum resources can provide an advantage. The structure of multi-user channels creates opportunities for entanglement to boost performance, pushing the boundaries of what's possible with just a classical channel. I believe this field is ripe for further exploration, and who knows what other surprising connections between quantum mechanics and communication theory are waiting to be discovered!

References