Research map / Multi-agent systems and games / Games and equilibria
Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that externalities break down social welfare in a two-player bandit game without property rights, and proposes BELGIC, a downstream-player policy that learns Coasean transfers online so that social welfare regret becomes sub-linear (an online Coase theorem).
Problem
Externalities cause social welfare loss when agents must learn their own and others' rewards; the Coase theorem assumes perfect knowledge, so it is unclear whether efficient bargaining is achievable under learning.
Approach
Models the externality as a two-player bandit game in which the upstream player's arm affects the downstream reward; with property rights the downstream player offers learned transfers via batched binary search to estimate per-arm minimal incentives, then runs a bandit subroutine on shifted rewards so that individual no-regret learning yields sub-linear social welfare regret.
Key results
- Without property rights, the social welfare regret is Omega(T) for any no-regret upstream policy under the stated gap condition.
- With BELGIC the social welfare regret is O(K log(T) T^{(kappa+1)/2}) when the upstream runs UCB, with the downstream regret bound (10+4K+32sqrt(K log_2(KT^3))+v̄-v̲) log_2(T)(3+2T^{3/4})+3K^2(v̄-v̲) for alpha=3/4, beta=1/4.
- In simulation with T=5e6 and 10 arms, empirical frequencies show the upstream player converges to the social optimum (q1=8) with BELGIC rather than its individual optimum (q1=5) without property rights.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Introduce property rights and use BELGIC for bargaining and transfers | Two-player bandit game with externalities · Two-player bandit game | social welfare regret: \mathcal{O}(K\log(T)T^{(\kappa+1)/2}) | Helped |
| Allow players to act independently without property rights | Two-player bandit game with misaligned interests · Two-player bandit game without property rights | social welfare regret: \Omega(T) | Hurt |
Surprising findings
- Individually rational no-regret learners with transfers jointly achieve social welfare optimality, even though both players are learning.
Limitations
- Restricted to finite action sets and two players; extensions to multiple agents are left open.
- Regret guarantees depend on the upstream regret bound assumption (C, kappa) and sub-Gaussian rewards; the upstream learning rate limits downstream rate.
- Assumes transfers are costless and the upstream follows a no-regret algorithm satisfying a batched regret property.
Experimental setup
Benchmarks: simulated two-firm bandit instance (T=5e6, 10 arms)
Metrics: empirical frequency of upstream player's actions social welfare regret (theoretical bound)
Baselines: UCB without property rights (competitive outcome)
Builds on: Upper Confidence Bounds (UCB) Coase theorem principal-agent bandit models incentivized exploration
Closest papers by meaning
- Equilibrium of Data Markets with Externality (ICML 2024 · similarity 0.85)
- LOPT: Learning Optimal Pigovian Tax in Sequential Social Dilemmas (NeurIPS 2025 · similarity 0.84)
- Domination-Avoiding Learning Agents Cannot Collude (NeurIPS 2026 · similarity 0.84)
- Maximizing utility in multi-agent environments by anticipating the behavior of other learners (NeurIPS 2024 · similarity 0.84)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.84)
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.