Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality

We thank the reviewer for the detailed feedback. All the comments will be taken into account in the new version of the paper. You can find below our answers to each of your concerns.

W1. One significant weakness of the paper is the lack of empirical validation or experimental results to back up the proposed theoretical framework.

We will add in the revised version experiments on a toy model. Please see the attached pdf for the corresponding, unpolished, figure. In a few words, we consider a simple environment with two firms having continuous (quadratic) profit functions, similarly to Example 1. We discretize these functions so each level corresponds to an arm. We consider the two cases where (i) no property rights are defined and both firms playing UCB; (ii) property rights are defined, with the downstream firm applying BELGIC (and upstream plays UCB). In both cases, we plot the empirical frequency of the action chosen by the upstream firm. As expected by our theory, we observe in this example that the learning agents will quickly converge to the social optimum when using transfers and implementing the algorithm BELGIC (for the downstream player). On the other hand, there is a social inefficiency in the absence of transfers, as the upstream player ends up choosing his best action, regardless of the downstream utility.

W2. Addressing implementation hurdles could provide valuable insights for policymakers and practitioners.

Addressing implementation of our approach on real world situations for policymakers and practitioners requires an extensive line of research that is generally run over multiple years in economics. We believe that studying these questions is out of our scope and left for future work. Before that, we also believe that building a more solid theoretical understanding of the problem is necessary, through extensions to more realistic cases (as in our answer below to W3).

As an example, Abildtrup et al (2012) observed that the predictions of Coase theorem are not verified for an interaction between farmers and waterworks in Denmark. They suggested that the uncertainty on the reward functions might be a reason for that. We can see our work as an illustration of the cost of learning in the presence of uncertainty: this cost might be an obstacle for practical implementation.

W3. Do the observations apply to potentially broader settings?

Please see our general answer on the use of our work for more general settings. To summarize, extending our work to broader settings is a very interesting direction for future work. We believe that our work can pave the way towards tackling more general settings.

W4. The mathematical notations provided in the paper sometimes become too difficult to follow and correlate with the text.

We realize that we build on a quite heavy set of notations and have faced several times the challenge of writing something clear but still rigorous. The latter forced us to rely on several different mathematical notations but we can either introduce clearer environment definitions or a table of notations.

If the reviewers agree, we would love to include a table of notations after the references to help the reader. We can also insist on the notations and their definitions each time we introduce a new one to ease the reading.

---

We hope that we answered all your different concerns. If you still have any, we would be happy to answer any further questions.

---

References

Abildtrup, J., Jensen, F., & Dubgaard, A. (2012). Does the Coase theorem hold in real markets? An application to the negotiations between waterworks and farmers in Denmark. Journal of environmental management, 93(1), 169-176.

We thank the reviewer for the detailed feedback. All the comments will be taken into account in the new version of the paper. You can find below our answers to each of your concerns.

It will be nice to see a discussion about possible notions of optimality of mechanisms that incentivize participation in this context.

As explained in the general answer, with the current assumption on the upstream player, we cannot hope for a better bound than $T^{\frac{\kappa+1}{2}}$. Indeed, in the almost “ideal” scenario where the downstream player proposes a payment $\tau_{a}^{\star}+\varepsilon$ on the (socially) optimal arm $a$ at each round, within our assumptions, the upstream player might not pull $a$ a number of times $\frac{T^{\kappa}}{\varepsilon}$, while still having an upstream regret smaller than $T^{\kappa}$. This would then imply a total downstream regret of order $\frac{T^{\kappa}}{\varepsilon}+T\varepsilon$, which is minimized for $\varepsilon=T^{\frac{\kappa-1}{2}}$ with value $T^{\frac{\kappa+1}{2}}$. Note that this is also the reason for which we add an extra $T^{\frac{\kappa-1}{2}}$ term in the proposed payment in the final phase of the algorithm.

Yet, it might be possible that stronger assumptions on the upstream player strategy (that remain realistic) could lead to better regret bounds in the end.

How broad do you expect the BELGIC routine to be applicable?

We invite the reviewer to look at our general answer on the use of our work for more general settings. To summarize, if externalities go both ways (i.e. downstream action also influences upstream utility), the problem becomes much more complex and BELGIC shouldn’t learn the optimal equilibrium. This would then become a general repeated game, for which learning is hard and a long line of research already exists. Our goal in this work is instead to consider a simpler game structure, where learning is easier. Extending this kind of problem to more than two agents is an interesting question as explained in our general answer, and we believe that BELGIC can pave the way towards designing satisfying learning strategies in those games and understanding how they behave when increasing the number of involved agents.

Thank you for your insightful feedback, that will be taken into account in the new version of the paper. We answer below your different questions.

It is not clear whether the regret incurred by the downstream player is optimal.

See our general answer on optimality of the regret bound for BELGIC for more details. To summarize, we believe that the $T^{\frac{1+\kappa}{2}}$ bound is optimal with our set of assumptions. Yet, it might be possible that stronger assumptions on the upstream player strategy (that remain realistic) could lead to better regret bounds in the end.

It is stated (on lines 111-112) that the assumption that the rewards are bounded is "without loss of generality"

Note that our boundedness assumption is about the expected rewards $v^{\mathrm{up}}(a)$. On the other hand, we assume nothing about the random realization rewards, except 1-sub-Gaussianity in Corollary 1. H1 is only needed to know the range for which we should run the binary search (to estimate the optimal transfers $\pi^{\star}$). When the range is unknown, we could first do a range search procedure before the binary search, but we eluded this point for the sake of simplicity and presentation.

In the current setup, it is assumed that transfers occur only on a single action, with the transfer function taking a value of 0 for all but one action

More generally, we could indeed define transfers as a vector of size $K$ depending on the choice of the upstream player. However such a possibility does not bring any improvement in the considered solution for the downstream player, as we cannot infer more information from the choice of action by the upstream player in that case.