IEEE Transactions on Information Theory

Signaling Games for Log-Concave Distributions: Number of Bins and Properties of Equilibria

Ertan Kazıklı, Serkan Sarıtaş, Sinan Gezici, Tamás Linder, Serdar Yüksel

Published Nov 25, 2021• 6 citations

Abstract

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions.

DOI: 10.1109/tit.2021.3130672

Related papers

Quadratic Multi-Dimensional Signaling Games and Affine Equilibria

Serkan Sarıtaş, Serdar Yüksel, Sinan Gezici

This paper studies the decentralized quadratic cheap talk and signaling game problems when an encoder and a decoder, viewed as two decision makers, have misaligned objective functions. The main contributions of this study are the extension of Crawford and Sobel's cheap talk formulation to multi-dimensional sources and to noisy channel setups. We consider both (simultaneous) Nash equilibria and (sequential) Stackelberg equilibria. We show that for arbitrary scalar sources, in the presence of misalignment, the quantized nature of all equilibrium policies holds for Nash equilibria in the sense that all Nash equilibria are equivalent to those achieved by quantized encoder policies. On the other hand, all Stackelberg equilibria policies are fully informative. For multi-dimensional setups, unlike the scalar case, Nash equilibrium policies may be of non-quantized nature, and even linear. In the noisy setup, a Gaussian source is to be transmitted over an additive Gaussian channel. The goals of the encoder and the decoder are misaligned by a bias term and encoder's cost also includes a penalty term on signal power. Conditions for the existence of affine Nash equilibria as well as general informative equilibria are presented. For the noisy setup, the only Stackelberg equilibrium is the linear equilibrium when the variables are scalar. Our findings provide further conditions on when affine policies may be optimal in decentralized multi-criteria control problems and lead to conditions for the presence of active information transmission in strategic environments.

arXiv:1503.04360IEEE Transactions on Automatic ControlJun 8, 201657 citations

On multi-dimensional and noisy quadratic signaling games and affine equilibria

Serkan Sarıtaş, Serdar Yüksel, Sinan Gezici

This study investigates extensions of the quadratic cheap talk and signaling game problem, which has been introduced in the economics literature. Two main contributions of this study are the extension of Crawford and Sobel's cheap talk formulation to multi-dimensional sources, and the extension to noisy channel setups as a signaling game problem. We show that, in the presence of misalignment, the quantized nature of all equilibrium policies holds for any scalar random source. It is shown that for multi-dimensional setups, unlike the scalar case, equilibrium policies may be of non-quantized nature, and even linear. In the noisy setup, a Gaussian source is to be transmitted over an additive Gaussian channel. The goals of the encoder and the decoder are misaligned by a bias term and encoder's cost also includes a power term scaled by a multiplier. Conditions for the existence of affine equilibrium policies as well as general informative equilibria are presented for both the scalar and multi-dimensional setups.

Proceedings of the ... American Control Conference/Proceedings of the American Control ConferenceJul 1, 20159 citations

Dynamic signaling games under Nash and Stackelberg equilibria

Serkan Sarıtaş, Serdar Yüksel, Sinan Gezici

In this study, dynamic and repeated quadratic cheap talk and signaling game problems are investigated. These involve encoder and decoders with mismatched performance objectives, where the encoder has a bias term in the quadratic cost functional. We consider both Nash equilibria and Stackelberg equilibria as our solution concepts, under a perfect Bayesian formulation. These two lead to drastically different characteristics for the equilibria. For the cheap talk problem under Nash equilibria, we show that fully revealing equilibria cannot exist and the final state equilibria have to be quantized for a large class of source models; whereas, for the Stackelberg case, the equilibria must be fully revealing regardless of the source model. In the dynamic signaling game where the transmission of a Gaussian source over a Gaussian channel is considered, the equilibrium policies are always linear for scalar sources under Stackelberg equilibria, and affine policies constitute an invariant subspace under best response maps for Nash equilibria.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20168 citations

Nash and Stackelberg equilibria for dynamic cheap talk and signaling games

Serkan Sarıtaş, Serdar Yüksel, Sinan Gezici

Simultaneous (Nash) and sequential (Stackelberg) equilibria of two-player dynamic quadratic cheap talk and signaling game problems are investigated under a perfect Bayesian formulation. For the dynamic scalar and multi-dimensional cheap talk, the Nash equilibrium cannot be fully revealing whereas the Stackelberg equilibrium is always fully revealing. Further, the final state Nash equilibria have to be essentially quantized when the source is scalar and has a density, and non-revealing for the multi-dimensional case. In the dynamic signaling game where the transmission of a Gauss-Markov source over a memoryless Gaussian channel is considered, affine policies constitute an invariant subspace under best response maps for both scalar and multi-dimensional sources under Nash equilibria; however, the Stackelberg equilibrium policies are always linear for scalar sources but may be non-linear for multi-dimensional sources. Further, under the Stackelberg setup, the conditions under which the equilibrium is non-informative are derived for scalar sources.

Proceedings of the ... American Control Conference/Proceedings of the American Control ConferenceMay 1, 20175 citations

Truth Revelation, Information Hiding, or Misinformation: Characterization of Equilibrium Outcomes in Signaling Games

Ertan Kazıklı, Sinan Gezici, Serdar Yüksel

In signaling games where a sender and a receiver have misaligned criteria, equilibrium behavior may lead to fully revealing, quantized, or randomized policies. Notably, the first arises in statistical decision theory and classical communication theoretic problems involving a fully aligned sensor and receiver, the second arises in Nash theoretic simultaneous signaling games, and the last may appear in Stackelberg type (leader-follower) Bayesian signaling games. In this paper, we investigate the Bayesian persuasion problem involving a receiver that tries to estimate the source. We show that for certain payoff structures, the equilibrium solution is such that a source observation is mapped to distinct messages with nonzero probabilities. More specifically, we completely characterize conditions under which the sender requires randomization for the Bayesian persuasion problem involving general sources with finite cardinality. In particular, regardless of whether the equilibrium solution under a deterministic policy restriction is fully revealing, quantized or noninformative, there exists a randomized sender policy that improves the sender's payoff under certain conditions characterized in the paper. Moreover, we provide an algorithmic procedure to obtain the Bayesian persuasion solution, where the algorithm compares the payoffs with finitely many posterior probability combinations. We also consider fully aligned and completely misaligned payoff structures, where the solutions respectively involve a fully revealing sender and a noninformative sender. Then, we unify these results by proving that if the sender's expected payoff with respect to posterior distributions is continuous, then the equilibrium solution involves either a fully revealing sender or a noninformative sender.

arXiv:2609.05489Aug 25, 20260 citations

Quadratic Privacy-Signaling Games, Payoff Dominant Equilibria and the Information Bottleneck Problem.

Ertan Kazıklı, Sinan Gezici, Serdar Yüksel

We introduce a privacy-signaling game problem in which a transmitter with privacy concerns observes a pair of correlated random variables which are modeled as jointly Gaussian. The transmitter aims to hide one of these random variables and convey the other one whereas the objective of the receiver is to accurately estimate both of the random variables. 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 for scalar sources a payoff dominant Nash equilibrium among all admissible policies is attained by affine policies. We prove that these Nash equilibria coincide with the Stackelberg equilibria. We also show that there always exists an informative Stackelberg equilibrium for the multidimensional parameter setting. We revisit the information bottleneck problem within our Stackelberg framework where under the information bottleneck setup the sender observes only one of the parameters. We characterize the Stackelberg equilibria under certain conditions and when these conditions are not met we establish the existence of informative equilibria.

arXiv:2005.05743May 12, 20202 citations