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


Creative Commons License

Kazikli E., SARITAŞ S. , GEZİCİ S., Linder T., Yuksel S.

IEEE TRANSACTIONS ON INFORMATION THEORY, vol.68, no.3, pp.1731-1757, 2022 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 68 Issue: 3
  • Publication Date: 2022
  • Doi Number: 10.1109/tit.2021.3130672
  • Title of Journal : IEEE TRANSACTIONS ON INFORMATION THEORY
  • Page Numbers: pp.1731-1757
  • 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

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.