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 systematic 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. We further prove that deciding whether there exists an equilibrium in which the receiver gets utility higher than the trivial utility he can guarantee is NP-hard. Fortunately, we identify two naturally-restricted cases that admit efficient algorithms for finding a sender-optimal equilibrium - a constant number of states or a receiver having only two actions.