Ferkans — Interactive Telecom Tutor

Beyond Two Users

Real systems serve many users simultaneously — a 5G cell may have $K = 10$ to $100$ active users. The two-user MAC theory generalizes naturally to $K$ users, but the structure of the capacity region becomes richer and more complex. Instead of three inequalities, we need $2^K - 1$ — one for every non-empty subset of users. The resulting capacity region is a polymatroid, a beautiful combinatorial-geometric object that connects information theory to discrete optimization.

Definition:
The $K$ -User Discrete Memoryless MAC

The $K$ -user DM-MAC consists of $K$ encoders with input alphabets $\mathcal{X}_1, \ldots, \mathcal{X}_K$ , an output alphabet $\mathcal{Y}$ , and a conditional PMF $p(y | x_1, \ldots, x_K)$ . Each encoder $k$ maps its message $W_k \in \{1, \ldots, 2^{nR_{k}}\}$ to a codeword $x_k^n(W_k)$ . The messages are independent. The decoder produces estimates $(\hat{W}_1, \ldots, \hat{W}_K)$ from $Y^n$ .

A rate tuple $(R_{1}, \ldots, R_{K})$ is achievable if $P_e^{(n)} \to 0$ as $n \to \infty$ .

Theorem: Capacity Region of the $K$ -User DM-MAC

The capacity region of the $K$ -user DM-MAC is the closure of the convex hull of all rate tuples $(R_{1}, \ldots, R_{K}) \in \mathbb{R}_+^K$ satisfying

$\sum_{k \in \mathcal{S}} R_{k} \leq I(X(\mathcal{S}); Y | X(\mathcal{S}^c)), \quad \forall \; \mathcal{S} \subseteq \{1, \ldots, K\}, \; \mathcal{S} \neq \emptyset,$

for some product distribution $\prod_{k=1}^K p(x_k)$ , where $X(\mathcal{S}) = \{X_k : k \in \mathcal{S}\}$ and $\mathcal{S}^c = \{1, \ldots, K\} \setminus \mathcal{S}$ .

Each inequality constrains the total rate of a subset of users. The bound $\sum_{k \in \mathcal{S}} R_{k} \leq I(X(\mathcal{S}); Y | X(\mathcal{S}^c))$ says: even if all users outside $\mathcal{S}$ are perfectly decoded and removed, the users in $\mathcal{S}$ cannot collectively exceed the mutual information of their combined input with the output.

For $K = 2$ , this gives three inequalities ( $\mathcal{S} = \{1\}$ , $\mathcal{S} = \{2\}$ , $\mathcal{S} = \{1,2\}$ ), recovering the pentagon of Section 14.1.

For $K = 3$ , we get $2^3 - 1 = 7$ inequalities: three individual, three pairwise, and one triple sum-rate.

Proof

Achievability

The achievability proof extends the joint typicality argument of Section 14.2. Generate $K$ independent random codebooks, one per user. The decoder searches for a unique $K$ -tuple $(w_1, \ldots, w_K)$ such that all codewords and the received sequence are jointly typical.

The error analysis now has $2^K - 1$ error events, one per non-empty subset $\mathcal{S}$ : the event that codewords in $\mathcal{S}$ are wrong while those in $\mathcal{S}^c$ are correct. Each such event contributes a probability bounded by

$2^{n \sum_{k \in \mathcal{S}} R_{k}} \cdot 2^{-n I(X(\mathcal{S}); X(\mathcal{S}^c), Y)} = 2^{-n(I(X(\mathcal{S}); Y | X(\mathcal{S}^c)) - \sum_{k \in \mathcal{S}} R_{k})},$

where we used the independence of the codebooks. Each term vanishes when the corresponding subset inequality is strict.

Converse

For each subset $\mathcal{S}$ , apply Fano's inequality to the messages $\{W_k : k \in \mathcal{S}\}$ conditioned on the messages $\{W_j : j \notin \mathcal{S}\}$ :

$\sum_{k \in \mathcal{S}} nR_{k} \leq I(W(\mathcal{S}); Y^n | W(\mathcal{S}^c)) + n\epsilon_n.$

By the chain rule and memoryless property, the mutual information term is bounded by $n I(X(\mathcal{S}); Y | X(\mathcal{S}^c))$ for some product distribution, completing the converse. $\blacksquare$

,

Definition:
Polymatroid

A polymatroid is a polytope $\mathcal{P} \subset \mathbb{R}_+^K$ defined by a submodular set function $f: 2^{\{1,\ldots,K\}} \to \mathbb{R}_+$ with $f(\emptyset) = 0$ :

$\mathcal{P} = \left\{(R_{1}, \ldots, R_{K}) \in \mathbb{R}_+^K : \sum_{k \in \mathcal{S}} R_{k} \leq f(\mathcal{S}), \; \forall \; \mathcal{S} \subseteq \{1, \ldots, K\}\right\}.$

A set function $f$ is submodular if for all $\mathcal{A}, \mathcal{B} \subseteq \{1, \ldots, K\}$ :

$f(\mathcal{A} \cup \mathcal{B}) + f(\mathcal{A} \cap \mathcal{B}) \leq f(\mathcal{A}) + f(\mathcal{B}).$

Submodularity captures the "diminishing returns" property.

For a fixed input distribution, the MAC capacity region is a polymatroid with $f(\mathcal{S}) = I(X(\mathcal{S}); Y | X(\mathcal{S}^c))$ . The submodularity of this function follows from the submodularity of entropy: for independent inputs, $I(X(\mathcal{S}); Y | X(\mathcal{S}^c))$ is a submodular function of $\mathcal{S}$ .

Polymatroid

A polytope in $\mathbb{R}_+^K$ defined by $2^K - 1$ inequalities indexed by subsets, where the bounding function is submodular. The MAC capacity region for a fixed input distribution has this structure.

Related: Capacity Region

Theorem: Submodularity of the MAC Rate Function

For a fixed product input distribution $\prod_{k=1}^K p(x_k)$ , the function

$f(\mathcal{S}) = I(X(\mathcal{S}); Y | X(\mathcal{S}^c))$

is a monotone submodular set function. That is, for all $\mathcal{A} \subseteq \mathcal{B} \subseteq \{1, \ldots, K\}$ :

Monotonicity: $f(\mathcal{A}) \leq f(\mathcal{B})$ .
Submodularity: For any user $k \notin \mathcal{B}$ , $f(\mathcal{A} \cup \{k\}) - f(\mathcal{A}) \geq f(\mathcal{B} \cup \{k\}) - f(\mathcal{B})$ .

Monotonicity says that adding more users to the subset increases the mutual information (more users carry more information). Submodularity says that the marginal contribution of a new user decreases as the existing subset grows — adding user $k$ to a large group helps less than adding it to a small group. This is a "diminishing returns" property that arises because the existing users already carry some of the information that user $k$ provides.

Proof

Express in terms of entropy

Since the inputs are independent:

$f(\mathcal{S}) = I(X(\mathcal{S}); Y | X(\mathcal{S}^c)) = H(Y | X(\mathcal{S}^c)) - H(Y | X_1, \ldots, X_K).$

Let $g(\mathcal{S}) = H(Y | X(\mathcal{S}^c))$ . Then $f(\mathcal{S}) = g(\mathcal{S}) - H(Y | X(\{1,\ldots,K\}))$ , and it suffices to show $g$ is monotone submodular.

Submodularity from conditioning

For $\mathcal{A} \subseteq \mathcal{B}$ , conditioning reduces entropy gives $H(Y | X(\mathcal{A}^c)) \leq H(Y | X(\mathcal{B}^c))$ since $\mathcal{B}^c \subseteq \mathcal{A}^c$ , i.e., $g(\mathcal{A}) \leq g(\mathcal{B})$ (monotonicity).

For submodularity, consider user $k \notin \mathcal{B}$ . The marginal gain $g(\mathcal{S} \cup \{k\}) - g(\mathcal{S}) = H(Y|X(\mathcal{S}^c \setminus \{k\})) - H(Y|X(\mathcal{S}^c)) = I(X_k; Y | X(\mathcal{S}^c \setminus \{k\}))$ . Since $\mathcal{A} \subseteq \mathcal{B}$ implies $\mathcal{B}^c \setminus \{k\} \subseteq \mathcal{A}^c \setminus \{k\}$ , conditioning reduces mutual information:

$I(X_k; Y | X(\mathcal{B}^c \setminus \{k\})) \leq I(X_k; Y | X(\mathcal{A}^c \setminus \{k\})).$

Wait, conditioning on more variables can increase or decrease mutual information. But here $X_k$ is independent of the conditioning variables, so conditioning on more X's reduces the "noise" and increases the mutual information... Actually, we need to use:

$f(\mathcal{A} \cup \{k\}) - f(\mathcal{A}) = H(Y|X(\mathcal{A}^c \setminus \{k\})) - H(Y|X(\mathcal{A}^c))$

and similarly for $\mathcal{B}$ . Since $\mathcal{A}^c \supseteq \mathcal{B}^c$ , more conditioning in the $\mathcal{B}$ case makes the marginal smaller. Formally, this follows from the chain rule of mutual information and the non-negativity of conditional mutual information. $\blacksquare$

SIC Orderings and Corner Points for $K$ Users

For the $K$ -user MAC, the polymatroidal capacity region has $K!$ corner points on the dominant face, one for each permutation $\pi = (\pi(1), \pi(2), \ldots, \pi(K))$ of the user indices.

The corner point corresponding to permutation $\pi$ is achieved by SIC with decoding order $\pi(1) \to \pi(2) \to \cdots \to \pi(K)$ :

User $\pi(1)$ is decoded first (treating all others as noise) at rate $I(X_{\pi(1)}; Y)$ .
User $\pi(2)$ is decoded second (after removing $\pi(1)$ ) at rate $I(X_{\pi(2)}; Y | X_{\pi(1)})$ .
User $\pi(k)$ is decoded $k$ -th at rate $I(X_{\pi(k)}; Y | X_{\pi(1)}, \ldots, X_{\pi(k-1)})$ .

The sum of all rates equals $I(X_1, \ldots, X_K; Y)$ regardless of the permutation (by the chain rule).

The entire dominant face is the convex hull of these $K!$ corner points. For $K = 3$ , this gives 6 corner points; for $K = 10$ , it gives $10! = 3,628,800$ corner points.

Example: Three-User Symmetric Gaussian MAC

Consider a three-user Gaussian MAC: $Y = X_1 + X_2 + X_3 + Z$ , with $X_k \sim \mathcal{N}(0, P)$ independently and $Z \sim \mathcal{N}(0, 1)$ . Write down all $2^3 - 1 = 7$ capacity region constraints and identify the symmetric rate point on the dominant face.

Solution

Individual rate constraints ($|\mathcal{S}| = 1$)

For any single user, the other two contribute noise:

$R_{k} \leq \frac{1}{2}\log\!\left(1 + \frac{P}{2P + 1}\right), \quad k = 1, 2, 3.$

Pairwise constraints ($|\mathcal{S}| = 2$)

For any pair $\\{j, k\\}$ , the third user contributes noise:

$R_{j} + R_{k} \leq \frac{1}{2}\log\!\left(1 + \frac{2P}{P + 1}\right), \quad \\{j,k\\} \subset \\{1,2,3\\}.$

Sum-rate constraint ($|\mathcal{S}| = 3$)

$R_{1} + R_{2} + R_{3} \leq \frac{1}{2}\log(1 + 3P).$ $

Symmetric rate point

By symmetry, the fair operating point is $R_{1} = R_{2} = R_{3} = R^*$ . The binding constraint is the tightest. Setting $R^* = C_{\text{sum}}/3$ :

$R^* = \frac{1}{6}\log(1 + 3P).$

We must verify this satisfies the individual and pairwise constraints. For $P = 10$ : $R^* = \frac{1}{6}\log 31 \approx 0.825$ bits. Individual bound: $\frac{1}{2}\log(1 + 10/21) \approx 0.347$ bits.

Since $0.825 > 0.347$ , the individual constraint is violated! So the symmetric sum-rate point $C_{\text{sum}}/3$ is not in the capacity region. The correct symmetric rate is:

$R^* = \min\!\left(\frac{1}{6}\log(1+3P),\; \frac{1}{4}\log\!\left(1+\frac{2P}{P+1}\right),\; \frac{1}{2}\log\!\left(1+\frac{P}{2P+1}\right)\right).$

For $P = 10$ : the individual constraint $\approx 0.347$ is the tightest. The total symmetric throughput is $3 \times 0.347 \approx 1.04$ bits, much less than $C_{\text{sum}} \approx 2.474$ bits. This shows the severe "fairness cost" in the symmetric MAC at high SNR.

Massive Random Access and the Many-User MAC

The $K$ -user MAC framework is particularly relevant for massive random access in IoT scenarios, where $K$ can be very large (thousands to millions of devices). In this regime:

The $2^K - 1$ constraints make the capacity region description exponentially complex.
Practical interest shifts to the symmetric sum rate and the per-user rate $R/K$ as $K \to \infty$ .
New paradigms like unsourced random access (Polyanskiy, 2017) sidestep the exponential complexity by treating all users as identical and only requiring the decoder to recover the set of transmitted messages (without user identification).

The connection between the classical $K$ -user MAC and modern massive access is an active area of research, with links to compressed sensing, approximate message passing, and coded random access.

⚠️Engineering Note

Exponential Growth of MAC Constraints

The $K$ -user MAC capacity region requires $2^K - 1$ inequalities. For practical system design with $K > 10$ users, this exponential description is intractable. Practical approaches include:

Greedy SIC: Choose a specific decoding order (typically by decreasing received power) and operate at the corresponding corner point. This requires only $K$ rate constraints.
Equal-rate operation: Operate at the symmetric rate point, which is determined by a single constraint (the tightest among all subsets).
Clustering: Group users into small clusters ( $K_c \leq 4$ ) and apply SIC within each cluster while treating inter-cluster interference as noise.

Practical Constraints

•
Full capacity region requires exponential number of constraints
•
SIC decoding order affects fairness among users
•
Scheduling algorithms must balance throughput and fairness

Quick Check

For a 4-user MAC, how many subset inequalities define the capacity region?

4

7

15

24

Correction:

15

$2^4 - 1 = 15$ : 4 singleton, 6 pairs, 4 triples, 1 quadruple.

Key Takeaway

The $K$ -user MAC capacity region is described by $2^K - 1$ mutual information inequalities, one per non-empty user subset. The region has a polymatroidal structure characterized by the submodularity of the mutual information set function. SIC with a specific decoding order achieves one of $K!$ corner points on the dominant face. The exponential growth of constraints motivates practical approaches like greedy SIC and user clustering.

The MAC with More Than Two Users