Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2012.08265 · 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• 8 citations
arXivHTMLPDF

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

Signaling and information games with subjective costs or priors and privacy constraints

Ertan Kazıklı

We investigate signaling game problems where an encoder and a decoder with misaligned objectives communicate. We consider a variety of setups involving cost criterion mismatch, prior mismatch and a particular application to privacy problems. We also consider both Nash and Stackelberg solution concepts. First, we extend the classical results on the scalar cheap talk problem which is intro-duced by Crawford and Sobel. In prior work, it is shown that the encoder must employ a quantization policy under any Nash equilibrium for arbitrary source distributions. We specifically consider sources with a log-concave density and in-vestigate properties of equilibria. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. If the source has semi-unbounded support, then there may exist a finite upper bound on the number of bins in equilibrium depending on certain explicit condi-tions. Moreover, we show that an equilibrium with more bins is more informative by showing that 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 that if the encoder and decoder iteratively compute their best responses starting from a given number of bins, then the resulting policies converge to the unique equilibrium with the corresponding number of bins. Second, we model a privacy problem as a signaling game between an encoder and a decoder. Given a pair of correlated observations modeled as jointly Gaus-sian random vectors, the encoder aims to hide one of them and convey the other one to the decoder. In contrast, the aim of the decoder is to accurately estimate both of the random vectors. For the resulting signaling game problem, we show that a payoff dominant Nash equilibrium among all admissible policies is attained by a set of explicitly characterized linear policies. We also show that a payoff dominant Nash equilibrium coincides with a Stackelberg equilibrium. Moreover, we formulate the information bottleneck problem within our Stackelberg frame-work under the mean squared error criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the encoder. We show that the Gaussian information bottleneck problem admits a linear solution which is explicitly characterized. Third, we investigate communications through a Gaussian noise channel be-tween an encoder and a decoder with prior mismatch. Although they consider the same cost function, the induced expected costs as a map of their policies are misaligned due to their prior mismatch. We analyze the resulting signaling game problem under Stackelberg equilibria. We first investigate robustness of equilibria and show that the Stackelberg equilibrium cost of the encoder is upper semi continuous, under the Wasserstein metric, as the encoder’s prior approaches the decoder’s prior, and it is also lower semi continuous with Gaussian priors. In addition, we show that the optimality of affine policies for Gaussian signaling no longer holds under prior mismatch. Furthermore, we provide conditions under which there exist informative equilibria under an affine policy restriction. Fourth, we extend Crawford and Sobel’s formulation to a multidimensional source setting. We first provide a set of geometry conditions that decoder actions at a Nash equilibrium has to satisfy considering any multidimensional source. Then, we consider independent and identically distributed sources and charac-terize necessary and sufficient conditions under which an informative linear equi-librium exists. We observe that these conditions involve the bias vector that leads to misaligned costs. Depending on certain conditions on the bias vector, the existence of linear equilibria may require sources with a Gaussian or a sym-metric density. Moreover, we provide a rate-distortion theoretic formulation of the cheap talk problem and obtain achievable rate and distortion pairs for the Gaussian case. Finally, in a communication theoretic setup, we consider modulation classi-fication and symbol decoding problems jointly and propose optimal strategies under various settings. The aim is to decode a sequence of received signals with an unknown modulation scheme. First, the prior probabilities of the candidate modulation schemes are assumed to be known and a formulation is proposed under the Bayesian framework. Second, we address the case when the prior prob-abilities of the candidate modulation schemes are unknown, and provide a method under the minimax framework. Numerical simulations show that the proposed techniques improve the performance under the employed criteria compared to the conventional techniques in a variety of system configurations.

•Aug 1, 2021•0 citations

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.04360•IEEE Transactions on Automatic Control•Jun 8, 2016•54 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 Conference•Jul 1, 2015•9 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, 2016•8 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 Conference•May 1, 2017•5 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.05489•Aug 25, 2026•0 citations
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.
We investigate signaling game problems where an encoder and a decoder with misaligned objectives communicate. We consider a variety of setups involving cost criterion mismatch, prior mismatch and a particular application to privacy problems. We also consider both Nash and Stackelberg solution concepts. First, we extend the classical results on the scalar cheap talk problem which is intro-duced by Crawford and Sobel. In prior work, it is shown that the encoder must employ a quantization policy under any Nash equilibrium for arbitrary source distributions. We specifically consider sources with a log-concave density and in-vestigate properties of equilibria. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. If the source has semi-unbounded support, then there may exist a finite upper bound on the number of bins in equilibrium depending on certain explicit condi-tions. Moreover, we show that an equilibrium with more bins is more informative by showing that 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 that if the encoder and decoder iteratively compute their best responses starting from a given number of bins, then the resulting policies converge to the unique equilibrium with the corresponding number of bins. Second, we model a privacy problem as a signaling game between an encoder and a decoder. Given a pair of correlated observations modeled as jointly Gaus-sian random vectors, the encoder aims to hide one of them and convey the other one to the decoder. In contrast, the aim of the decoder is to accurately estimate both of the random vectors. For the resulting signaling game problem, we show that a payoff dominant Nash equilibrium among all admissible policies is attained by a set of explicitly characterized linear policies. We also show that a payoff dominant Nash equilibrium coincides with a Stackelberg equilibrium. Moreover, we formulate the information bottleneck problem within our Stackelberg frame-work under the mean squared error criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the encoder. We show that the Gaussian information bottleneck problem admits a linear solution which is explicitly characterized. Third, we investigate communications through a Gaussian noise channel be-tween an encoder and a decoder with prior mismatch. Although they consider the same cost function, the induced expected costs as a map of their policies are misaligned due to their prior mismatch. We analyze the resulting signaling game problem under Stackelberg equilibria. We first investigate robustness of equilibria and show that the Stackelberg equilibrium cost of the encoder is upper semi continuous, under the Wasserstein metric, as the encoder’s prior approaches the decoder’s prior, and it is also lower semi continuous with Gaussian priors. In addition, we show that the optimality of affine policies for Gaussian signaling no longer holds under prior mismatch. Furthermore, we provide conditions under which there exist informative equilibria under an affine policy restriction. Fourth, we extend Crawford and Sobel’s formulation to a multidimensional source setting. We first provide a set of geometry conditions that decoder actions at a Nash equilibrium has to satisfy considering any multidimensional source. Then, we consider independent and identically distributed sources and charac-terize necessary and sufficient conditions under which an informative linear equi-librium exists. We observe that these conditions involve the bias vector that leads to misaligned costs. Depending on certain conditions on the bias vector, the existence of linear equilibria may require sources with a Gaussian or a sym-metric density. Moreover, we provide a rate-distortion theoretic formulation of the cheap talk problem and obtain achievable rate and distortion pairs for the Gaussian case. Finally, in a communication theoretic setup, we consider modulation classi-fication and symbol decoding problems jointly and propose optimal strategies under various settings. The aim is to decode a sequence of received signals with an unknown modulation scheme. First, the prior probabilities of the candidate modulation schemes are assumed to be known and a formulation is proposed under the Bayesian framework. Second, we address the case when the prior prob-abilities of the candidate modulation schemes are unknown, and provide a method under the minimax framework. Numerical simulations show that the proposed techniques improve the performance under the employed criteria compared to the conventional techniques in a variety of system configurations.
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.
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.
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.
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.
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.