Bayesian Persuasion with Sequential Games
This work addresses information design in multi-agent sequential interactions, providing computational insights for persuasion in game theory, though it is incremental by extending existing models to sequential settings.
The authors tackled the problem of designing optimal signaling schemes for a sender in a Bayesian persuasion model with multiple receivers playing a sequential game, showing that computing an optimal ex ante persuasive scheme is NP-hard for three or more receivers but can be done in polynomial time for two receivers using a novel ellipsoid-based algorithm.
We study an information-structure design problem (a.k.a. persuasion) with a single sender and multiple receivers with actions of a priori unknown types, independently drawn from action-specific marginal distributions. As in the standard Bayesian persuasion model, the sender has access to additional information regarding the action types, which she can exploit when committing to a (noisy) signaling scheme through which she sends a private signal to each receiver. The novelty of our model is in considering the case where the receivers interact in a sequential game with imperfect information, with utilities depending on the game outcome and the realized action types. After formalizing the notions of ex ante and ex interim persuasiveness (which differ in the time at which the receivers commit to following the sender's signaling scheme), we investigate the continuous optimization problem of computing a signaling scheme which maximizes the sender's expected revenue. We show that computing an optimal ex ante persuasive signaling scheme is NP-hard when there are three or more receivers. In contrast with previous hardness results for ex interim persuasion, we show that, for games with two receivers, an optimal ex ante persuasive signaling scheme can be computed in polynomial time thanks to a novel algorithm based on the ellipsoid method which we propose.