Communication and Third Parties: Costs

This thesis tells the story of Alice and Bob, who wish to share information. However, Alice and Bob, motivated either by self-interest or simply good manners, also wish to respect constraints imposed by Candice, Damon, or Eve, who may be lurking in the background. This thesis takes an information-theoretic approach to determine the rates at which Alice and Bob can communicate while satisfying the constraints imposed by these third parties. The constraints in this thesis are inspired by wireless communication, in which multiple users share a common medium. Signals over a common medium can interfere with one another, so a case study is introduced that models one aspect of this problem: Alice must send a message to Bob such that she does not interfere with communication from Candice to Damon. Furthermore, Candice and Damon are unaware of Alice and Bob, so there is no direct way for Alice to learn how much interference she causes. However, by relying on cues gained from eavesdropping on feedback signals from Damon to Candice, strategies are introduced that enable Alice to communicate with Bob and adaptively control the average interference. While the case study only accounts for the average interference, Damon may be more annoyed by interference arriving in bursts than interference spread out over time. To address this issue, a new model is introduced that forces Alice's transmissions to satisfy a cost constraint, where the cost at a given time can include memory about the past. A strategy is introduced that enables Alice to adjust her transmissions to communicate with Bob and satisfy the cost constraint. A converse is also proved that characterizes when this strategy is optimal. Wireless environments allow characters like Eve, an eavesdropper, to intercept signals that are not intended for them. A model is considered in which Alice and Bob wish to keep the information they share secret from Eve. Specifically, Alice, Bob, and Eve share correlated observations, and there is a one-way noisy broadcast channel from Alice to Bob and Eve. Do Alice and Bob want to keep specific information secret, or is any information kept secret from Eve sufficient? It turns out that the rates Alice and Bob can achieve depend on the answer to this question, and a strategy is introduced that establishes a functional relationship between these two notions of secrecy. Furthermore, this strategy is shown to be optimal over a class of models that includes one applicable to wireless: namely, the case in which the channel noises are additive Gaussian and the correlated observations are jointly Gaussian.