2023/11/15 by Babichenko, Yakov, Talgam-Cohen, Inbal, Xu, Haifeng +1
#91A68 (Primary) 91A27 (Secondary) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.09011
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.