The Capacity Region of the Multiple Access Channel with Non-Signaling Assistance

The capacity region of the K-sender discrete memoryless multiple access channel (MAC) is fully characterized when non-signaling (NS) assistance is available to all K transmitters and the receiver. It is shown to have the same form as the classical capacity region of the MAC, except that the input distribution is allowed to be arbitrarily dependent across the senders. In particular, the NS-assisted capacity region matches the natural generalization to K senders of an outer bound that was previously established by Fawzi and Fermé for K=2 senders. Additionally, we provide examples of K-sender MACs where the multiplicative gain in capacity from NS-assistance is arbitrarily close to K. Combined with an upper bound from prior work, this establishes K as the extremal value of the multiplicative gain from NS-assistance across all K-sender MAC settings.