Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. 2016. “Signaling in Bayesian Stackelberg Games .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
Algorithms for solving Stackelberg games are used in an evergrowing variety of real-world domains. Previous work has extended this framework to allow the leader to commit not only to
a distribution over actions, but also to a scheme for stochastically
signaling information about these actions to the follower. This can
result in higher utility for the leader. In this paper, we extend this
methodology to Bayesian games, in which either the leader or the
follower has payoff-relevant private information or both. This leads
to novel variants of the model, for example by imposing an incentive compatibility constraint for each type to listen to the signal
intended for it. We show that, in contrast to previous hardness
results for the case without signaling [5, 16], we can solve unrestricted games in time polynomial in their natural representation.
For security games, we obtain hardness results as well as efficient
algorithms, depending on the settings. We show the benefits of our
approach in experimental evaluations of our algorithms.