We study a problem of communication between an influencer and a receiver where the influencer has access to a sequence of facts that the receiver is interested in knowing with zero error. The influencer sends a signal to the receiver for every such sequence and it obtains a utility that is a function of the true sequence and the sequence deduced by the receiver, and incurs a cost that is a function of the true sequence and the signal sent. The influencer may choose to induce ambiguity by sending a common signal for multiple sequences, and by performing coding. The resulting problem is studied as a Stackelberg game and operational strategies are obtained as the equilibrium of this game. Our main contribution is the study of informativeness – the minimum amount of correct information that the receiver can obtain in any such equilibrium. We characterize informativeness as the limiting value of the list chromatic number of a sequence of graphs and obtain single-letter bounds on it. Our results show that the presence of cost increases informativeness and when a certain single-letter condition holds, there is no benefit to coding in the costless case.
We study a problem of communication between an influencer and a receiver where the influencer has access to a sequence of facts that the receiver is interested in knowing with zero error. The influencer sends a signal to the receiver for every such sequence and it obtains a utility that is a function of the true sequence and the sequence deduced by the receiver, and incurs a cost that is a function of the true sequence and the signal sent. The influencer may choose to induce ambiguity by sending a common signal for multiple sequences, and by performing coding. The resulting problem is studied as a Stackelberg game and operational strategies are obtained as the equilibrium of this game. Our main contribution is the study of informativeness – the minimum amount of correct information that the receiver can obtain in any such equilibrium. We characterize informativeness as the limiting value of the list chromatic number of a sequence of graphs and obtain single-letter bounds on it. Our results show that the presence of cost increases informativeness and when a certain single-letter condition holds, there is no benefit to coding in the costless case.
We introduce a setting where a receiver aims to perfectly recover a source known privately to a \textit{strategic} sender over a possibly noisy channel. The sender is endowed with a utility function and sends signals to the receiver with the aim of maximizing this utility. Due to the strategic nature of the sender not all the transmitted information is truthful, which leads to question: how much true information can be recovered by the receiver from such a sender? We study this question in this paper. We pose the problem as a game between the sender and receiver, where the receiver tries to maximize the number of sequences that can be recovered perfectly and the sender maximizes its utility. We show that, in spite of the sender being strategic and the presence of noise in the channel, there is a strategy for the receiver by which it can perfectly recover an \textit{exponentially} large number of sequences. Our analysis leads to the notion of the \textit{information extraction capacity} of the sender which quantifies the growth rate of the number of recovered sequences with blocklength, in the presence of a noiseless channel. We identify cases where this capacity is equal to its theoretical maximum, and also when it is strictly less than maximum. In the latter case, we show that the capacity is sandwiched between the independence number and the Shannon capacity of a suitably defined graph. These results lead to an exact characterization of the information extraction capacity in large number of cases. We show that in the presence of a noisy channel, the rate of information extraction achieved by the receiver is the minimum of the zero-error capacity of the channel and the information extraction capacity of the sender. Our analysis leads to insights into a novel regime of communication involving strategic agents.
We consider a privacy-signaling game problem in which a transmitter with privacy concerns and a receiver, which does not pay attention to these privacy concerns, communicate. In this communication scenario, the transmitter observes a pair of correlated random variables which are modeled as jointly Gaussian. The transmitter constructs its message based on these random variables with the aim to hide one of them and convey the other one. In contrast, the objective of the receiver is to accurately estimate both of the random variables so as to gather as much information as possible. These conflicting objectives are analyzed in a game theoretic framework where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg equilibria. We show that a payoff dominant (i.e., most desirable for both players) Nash equilibrium is attained by affine policies and we explicitly characterize these policies. In addition, the strategies at the characterized Nash equilibrium is shown to form also a Stackelberg equilibrium. Furthermore, we show that there always exists an informative Stackelberg equilibrium for the multidimensional parameter setup. We also revisit the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the sender. We fully characterize the Stackelberg equilibria under certain conditions and when these conditions are not met we establish the existence of informative equilibria.
This paper analyzes a finite horizon dynamic signaling game motivated by the well-known strategic information transmission problems in economics. The mathematical model involves information transmission between two agents, a sender who observes two Gaussian processes, state and bias, and a receiver who takes an action based on the received message from the sender. The players incur quadratic instantaneous costs as functions of the state, bias and action variables. Our particular focus is on the Stackelberg equilibrium, which corresponds to information disclosure and Bayesian persuasion problems in economics. Prior work solved the static game, and showed that the Stackelberg equilibrium is achieved by pure strategies that are linear functions of the state and the bias variables. The main focus of this work is on the dynamic (multi-stage) setting, where we show that the existence of a pure strategy Stackelberg equilibrium, within the set of linear strategies, depends on the problem parameters. Surprisingly, for most problem parameters, a pure linear strategy does not achieve the Stackelberg equilibrium which implies the existence of a trade-off between exploiting and revealing information, which was also encountered in several other asymmetric information games.
It is a well known phenomenon that communication between a group of
players affects the set of equilibria of a repeated game. This communication
can be costly. Its cost may be measured in terms of complexity, or payoffs.
In particular, a payoff cost of communication occurs when players communicate
through their actions, and one is interested in characterizing the optimal
communication.
We study a class of games that models the communication cost of online
coordination. For example: A sequence X = (X(t)) of zeroes and ones is chosen
at random, and announced to a player, the seer, but not to his teammate, the
follower. A repeated game then proceeds in which the follower and the seer
choose actions Y (t) and Z(t) in {0, 1} at stage t, and their (common) stage
payoff is 1 whenever X(t) = Y (t) = Z(t).
We address the question of the optimal communication level from the seer
to the follower in order to maximize payoffs. We characterize this level using
the notion of entropy, and provide construction of optimal strategies for the
team: the seer and the follower. In particular, we prove that against a family
of i.i.d. random variables (1/2, 1/2), the maximum expected payoff v to the
team is the solution of the equation
H(x) + log(3) (1 - x) = 1;
where H is the entropy function and log is taken in basis 2. Moreover, we prove
the existence of pure strategies of the prophet and the seer that guarantee v
against all sequences X = X(t). Hence, the zero-sum game in which player I
is the Team (no correlation is allowed between its members), player II is the
opponent, and the payoff to I is as above, has a value, and this equals v. Our
result has direct implications for repeated games played by finite automata, or
by players with bounded recall.
We consider the problem of zero-error function computation with side information. Alice and Bob have correlated sources X,Y with joint p.m.f. pXY(⋅,⋅). Bob wants to calculate f(X,Y) with zero error. Alice encodes m-length blocks (m≥1) of her observations to Bob over error-free channels, which can be classical or quantum. We consider two classical settings. (i) Alice communicates via a fixed length code (FLC), and (ii) Alice communicates via a variable length code (VLC). In the FLC scenario, the minimum communication rate depends on the asymptotic growth of the chromatic number of an appropriately defined m-instance ``confusion graph'' G(m). In the VLC scenario, the corresponding rate is characterized by the asymptotics of the chromatic entropy of G(m). %and has single-letter characterization in terms of Körner's graph entropy if G(m) is m-times graph OR product. In the quantum setting, we only consider fixed length codes; the corresponding rate depends on the asymptotic growth of the orthogonal rank of the complement of G(m). The behavior of the communication rates depends critically on G(m), which is shown to be sandwiched between G⊠m (m-times strong product) and G∨m (m-times OR product) respectively. Our work presents necessary and sufficient conditions on the function f(⋅,⋅) and joint p.m.f. pXY(⋅,⋅) such that G(m) equals either G⊠m or G∨m. Our work explores the multitude of possible behaviors of the quantum and classical (FLC/VLC) rates in the single-instance case and the asymptotic (in m) case for several classes of confusion graphs.
In this paper, we address the problem of optimal hierarchical signaling between a sender and a receiver for a general class of square integrable multivariate distributions. The receiver seeks to learn a certain information of interest that is known to the sender while the sender seeks to induce the receiver to perceive that information as a certain private information. For the setting where the players have quadratic cost measures, we analyze the Stackelberg equilibrium, where the sender leads the game by committing his/her strategies beforehand. We show that when the underlying state space is finite, the optimal signaling strategies can be computed through an equivalent linear optimization problem over the cone of completely positive matrices. The equivalence established enables us to use the existing computational tools to solve this class of cone programs approximately with any error rate. For continuous distributions, we also analyze the error of approximation, if the optimal signaling strategy is computed for a discretized version obtained through a quantization scheme, and we provide an upper bound in terms of the quantization error.