Sender receiver games with payment promises shape outcomes and complexity
Sender-Receiver Games with Payment Commitments
Computer Science and Game Theory
Summary
This paper studies a game where one person (the sender) sends a message to another (the receiver), but both can commit to making payments based on what actually happens later. These payments can act as promises or penalties to influence decisions. The authors explore how these commitments affect the possible outcomes and how hard it is to find the best strategies. They show interesting differences depending on who commits first and whether payments can be random, and they provide efficient ways to compute optimal promises in some cases.
What this means in practice
- •For economic mechanism designers: Design contracts with conditional payments to reliably influence decisions before uncertainty resolves.
- •For automated negotiation systems: Compute efficient payment schemes to guide agent interactions where commitments influence later actions.
Authors
Ivan Geffner
Abstract
We study sender-receiver games in which players commit, before the state is drawn, to payments contingent on the subsequently verified state and the receiver's action. Payments may be transferred or burned, serving as contractual guarantees or promised tips. We analyze equilibrium guarantees, welfare, and computational complexity. For arbitrary finite action sets, we characterize pessimistic utility guarantees under unilateral commitments. Sender-only and sender-first commitments have worst-equilibrium welfare equal to the best constant-action welfare. Simultaneous commitments can instead reduce welfare below every equilibrium of the original game. Neither simultaneous nor sender-first commitments always admit an efficient equilibrium. Receiver-first commitments always admit an efficiently computable welfare-maximizing equilibrium, but can also reduce worst-equilibrium welfare. For binary actions, we characterize their entire equilibrium payoff region. With binary actions, optimal receiver commitments are computable in linear time, whereas optimizing deterministic sender commitments is NP-hard. Privately randomized sender commitments admit an exact $O(n\log n)$ algorithm, with an optimal lottery over at most two schemes differing at only one state. This yields an additive approximation by deterministic commitments. For arbitrary finite action sets, optimal privately randomized sender payoffs equal Bayesian persuasion values: ordinary persuasion with burning alone, and persuasion with nonnegative compliance payments when transfers are allowed. These equivalences yield polynomial-time algorithms with polynomial-size commitment lotteries.