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

Download

index.pdf

Date

2022-03-01

Author

Kazikli, Ertan
Sarıtaş, Serkan
GEZİCİ, Sinan
Linder, Tamas
Yuksel, Serdar

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

214
views

72
downloads

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.

Subject Keywords

Decoding, Quantization (signal), Costs, Games, Upper bound, Nash equilibrium, Linear programming, Cheap talk, signaling games, Nash equilibrium, optimal quantization, Lloyd-Max algorithm, payoff dominant equilibria, LOCALLY OPTIMAL QUANTIZER, CHEAP-TALK, COMMUNICATION, UNIQUENESS

URI

https://hdl.handle.net/11511/96662

Journal

IEEE TRANSACTIONS ON INFORMATION THEORY

DOI

https://doi.org/10.1109/tit.2021.3130672

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

On the Number of Bins in Equilibria for Signaling Games Sarıtaş, Serkan; Gezici, Sinan; Linder, Tamas; Yuksel, Serdar (2019-01-01) We investigate the equilibrium behavior for the decentralized quadratic cheap talk problem in which an encoder and a decoder, viewed as two decision makers, have misaligned objective functions. In prior work, we have shown that the number of bins under any equilibrium has to be at most countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we refine this result in the context of exponential and Gaussian sources. For expone...
Efficient Three-Layer Iterative Solutions of Electromagnetic Problems Using the Multilevel Fast Multipole Algorithm Onol, Can; Ucuncu, Arif; Ergül, Özgür Salih (2017-05-19) We present a three-layer iterative algorithm for fast and efficient solutions of electromagnetic problems formulated with surface integral equations. The strategy is based on nested iterative solutions employing the multilevel fast multipole algorithm and its approximate forms. We show that the three-layer mechanism significantly reduces solution times, while it requires no additional memory as opposed to algebraic preconditioners. Numerical examples involving three-dimensional scattering problems are prese...
Dynamic programming for a Markov-switching jump-diffusion Azevedo, N.; Pinheiro, D.; Weber, Gerhard Wilhelm (Elsevier BV, 2014-09-01) We consider an optimal control problem with a deterministic finite horizon and state variable dynamics given by a Markov-switching jump-diffusion stochastic differential equation. Our main results extend the dynamic programming technique to this larger family of stochastic optimal control problems. More specifically, we provide a detailed proof of Bellman's optimality principle (or dynamic programming principle) and obtain the corresponding Hamilton-Jacobi-Belman equation, which turns out to be a partial in...
Frequency estimation of a single real-valued sinusoid: An invariant function approach Candan, Çağatay; Çelebi, Utku (2021-08-01) An invariant function approach for the computationally efficient (non-iterative and gridless) maximum likelihood (ML) estimation of unknown parameters is applied on the real-valued sinusoid frequency estimation problem. The main attraction point of the approach is its potential to yield a ML-like performance at a significantly reduced computational load with respect to conventional ML estimator that requires repeated evaluation of an objective function or numerical search routines. The numerical results ind...
Stability analysis of constraints in flexible multibody systems dynamics İder, Sıtkı Kemal (Elsevier BV, 1990-1) Automated algorithms for the dynamic analysis and simulation of constrained multibody systems assume that the constraint equations are linearly independent. During the motion, when the system is at a singular configuration, the constraint Jacobian matrix possesses less than full rank and hence it results in singularities. This occurs when the direction of a constraint coincides with the direction of the lost degree of freedom. In this paper the constraint equations for deformable bodies are modified for use...

Citation Formats

E. Kazikli, S. Sarıtaş, S. GEZİCİ, T. Linder, and S. Yuksel, “Signaling Games for Log-Concave Distributions: Number of Bins and Properties of Equilibria,” IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 68, no. 3, pp. 1731–1757, 2022, Accessed: 00, 2022. [Online]. Available: https://hdl.handle.net/11511/96662.