This content will become publicly available on July 15, 2025
Title: Algorithmic Cheap Talk
The literature on strategic communication originated with the influential cheap talk model, which precedes the Bayesian persuasion model by three decades. This model describes an interaction between two agents: sender and receiver. The sender knows some state of the world which the receiver does not know, and tries to influence the receiver’s action by communicating a cheap talk message to the receiver. This paper initiates the algorithmic study of cheap talk in a finite environment (i.e., a finite number of states and receiver’s possible actions). We first prove that approximating the sender-optimal or the welfare-maximizing cheap talk equilibrium up to a certain additive constant or multiplicative factor is NP-hard. Fortunately, we identify three naturally-restricted cases that admit efficient algorithms for finding a sender-optimal equilibrium. These include a state-independent sender’s utility structure, a constant number of states or a receiver having only two actions. more »« less
We study a model of cheap talk with one substantive assumption: The sender's preferences are state independent. Our main observation is that such a sender gains credibility by degrading self‐serving information. Using this observation, we examine the sender's benefits from communication, assess the value of commitment, and explicitly solve for sender‐optimal equilibria in three examples. A key result is a geometric characterization of the value of cheap talk, described by the quasi concave envelope of the sender's value function.
Haghtalab, Nika; Immorlica, Nicole; Lucier, Brendan; Mobius, Markus; Mohan, Divyarthi(
, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
Guruswami, Venkatesan
(Ed.)
We study a communication game between a sender and receiver. The sender chooses one of her signals about the state of the world (i.e., an anecdote) and communicates it to the receiver who takes an action affecting both players. The sender and receiver both care about the state of the world but are also influenced by personal preferences, so their ideal actions can differ. We characterize perfect Bayesian equilibria. The sender faces a temptation to persuade: she wants to select a biased anecdote to influence the receiver’s action. Anecdotes are still informative to the receiver (who will debias at equilibrium) but the attempt to persuade comes at the cost of precision. This gives rise to informational homophily where the receiver prefers to listen to like-minded senders because they provide higher-precision signals. Communication becomes polarized when the sender is an expert with access to many signals, with the sender choosing extreme outlier anecdotes at equilibrium (unless preferences are perfectly aligned). This polarization dissipates all the gains from communication with an increasingly well-informed sender when the anecdote distribution is heavy-tailed. Experts therefore face a curse of informedness: receivers will prefer to listen to less-informed senders who cannot pick biased signals as easily.
Su, ST.; Kempe, D.; Subramanian, V.G.(
, Web and Internet Economics. WINE 2021. Lecture Notes in Computer Science())
Feldman, M.
(Ed.)
We study a Bayesian persuasion setting in which the receiver is trying to match the (binary) state of the world. The sender’s utility is partially aligned with the receiver’s, in that conditioned on the receiver’s action, the sender derives higher utility when the state of the world matches the action.
Our focus is on whether in such a setting, being constrained helps a receiver. Intuitively, if the receiver can only take the sender’s preferred action with smaller probability, the sender might have to reveal more information, so that the receiver can take the action more specifically when the sender prefers it. We show that with a binary state of the world, this intuition indeed carries through: under very mild non-degeneracy conditions, a more constrained receiver will always obtain (weakly) higher utility than a less constrained one. Unfortunately, without additional assumptions, the result does not hold when there are more than two states in the world, which we show with an explicit example.
Motivated by practical concerns in applying information design to markets and service systems, we consider a persuasion problem between a sender and a receiver where the receiver may not be an expected utility maximizer. In particular, the receiver’s utility may be non-linear in her belief; we deem such receivers as risk-conscious. Such utility models arise, for example, when the receiver exhibits sensitivity to the variability and the risk in the payoff on choosing an action (e.g., waiting time for a service). In the presence of such non-linearity, the standard approach of using revelation-principle style arguments fails to characterize the set of signals needed in the optimal signaling scheme. Our main contribution is to provide a theoretical framework, using results from convex analysis, to overcome this technical challenge. In particular, in general persuasion settings with risk-conscious agents, we prove that the sender’s problem can be reduced to a convex optimization program. Furthermore, using this characterization, we obtain a bound on the number of signals needed in the optimal signaling scheme.
We apply our methods to study a specific setting, namely binary per-suasion, where the receiver has two possible actions (0 and 1), and the sender always prefers the receiver taking action 1. Under a mild convexity assumption on the receiver’s utility and using a geometric approach,we show that the convex program can be further reduced to a linear program. Furthermore, this linear program yields a canonical construction of the set of signals needed in an optimal signaling mechanism. In particular, this canonical set of signals only involves signals that fully reveal the state and signals that induce uncertainty between two states.We illustrate our results in the setting of signaling wait time information in an unobservable queue with customers whose utilities depend on the variance of their waiting times.
Miller, Sara E.; Sheehan, Michael J.; Reeve, H. Kern(
, Philosophical Transactions of the Royal Society B: Biological Sciences)
Social interactions are mediated by recognition systems, meaning that the cognitive abilities or phenotypic diversity that facilitate recognition may be common targets of social selection. Recognition occurs when a receiver compares the phenotypes produced by a sender with a template. Coevolution between sender and receiver traits has been empirically reported in multiple species and sensory modalities, though the dynamics and relative exaggeration of traits from senders versus receivers have received little attention. Here, we present a coevolutionary dynamic model that examines the conditions under which senders and receivers should invest effort in facilitating individual recognition. The model predicts coevolution of sender and receiver traits, with the equilibrium investment dependent on the relative costs of signal production versus cognition. In order for recognition to evolve, initial sender and receiver trait values must be above a threshold, suggesting that recognition requires some degree of pre-existing diversity and cognitive abilities. The analysis of selection gradients demonstrates that the strength of selection on sender signals and receiver cognition is strongest when the trait values are furthest from the optima. The model provides new insights into the expected strength and dynamics of selection during the origin and elaboration of individual recognition, an important feature of social cognition in many taxa. This article is part of the theme issue ‘Signal detection theory in recognition systems: from evolving models to experimental tests’.
Babichenko, Yakov, Talgam-Cohen, Inbal, Xu, Haifeng, and Zabarnyi, Konstantin.
"Algorithmic Cheap Talk". Country unknown/Code not available: Proceedings of 25th ACM Conference on Economics and Computation, EC 2024. https://par.nsf.gov/biblio/10532234.
@article{osti_10532234,
place = {Country unknown/Code not available},
title = {Algorithmic Cheap Talk},
url = {https://par.nsf.gov/biblio/10532234},
abstractNote = {The literature on strategic communication originated with the influential cheap talk model, which precedes the Bayesian persuasion model by three decades. This model describes an interaction between two agents: sender and receiver. The sender knows some state of the world which the receiver does not know, and tries to influence the receiver’s action by communicating a cheap talk message to the receiver. This paper initiates the algorithmic study of cheap talk in a finite environment (i.e., a finite number of states and receiver’s possible actions). We first prove that approximating the sender-optimal or the welfare-maximizing cheap talk equilibrium up to a certain additive constant or multiplicative factor is NP-hard. Fortunately, we identify three naturally-restricted cases that admit efficient algorithms for finding a sender-optimal equilibrium. These include a state-independent sender’s utility structure, a constant number of states or a receiver having only two actions.},
journal = {},
publisher = {Proceedings of 25th ACM Conference on Economics and Computation, EC 2024},
author = {Babichenko, Yakov and Talgam-Cohen, Inbal and Xu, Haifeng and Zabarnyi, Konstantin},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
