Bayesian Persuasion with Externalities: Exploiting Agent Types
This work addresses a specific problem in algorithmic game theory for designing efficient persuasion mechanisms, but it is incremental as it extends existing models with externalities and type-based categorization.
The paper tackles the problem of computing optimal signaling strategies for a principal in a Bayesian persuasion model with externalities and agent types, showing that LP-based formulations yield polynomial-time solutions when the number of deviating agents is bounded, but the problems become NP-hard otherwise.
We study a Bayesian persuasion problem with externalities. In this model, a principal sends signals to inform multiple agents about the state of the world. Simultaneously, due to the existence of externalities in the agents' utilities, the principal also acts as a correlation device to correlate the agents' actions. We consider the setting where the agents are categorized into a small number of types. Agents of the same type share identical utility functions and are treated equitably in the utility functions of both other agents and the principal. We study the problem of computing optimal signaling strategies for the principal, under three different types of signaling channels: public, private, and semi-private. Our results include revelation-principle-style characterizations of optimal signaling strategies, linear programming formulations, and analysis of in/tractability of the optimization problems. It is demonstrated that when the maximum number of deviating agents is bounded by a constant, our LP-based formulations compute optimal signaling strategies in polynomial time. Otherwise, the problems are NP-hard.