Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality
Authors: Antoine Scheid
Aymeric Capitaine
Etienne Boursier
Eric Moulines
Michael Jordan
Alain Oliviero Durmus
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Online Learning
Bandits
Algorithmic Game Theory
Externality
Policy Design
Two-Players Game
Primary area: algorithmic_game_theory

Abstract: In Economics, the concept of externality refers to any indirect effect resulting from an interaction between players and affecting a third party without compensation. Most of the models within which externality has been studied assume that agents have perfect knowledge of their environment and preferences. This is a major hindrance to the practical implementation of many proposed solutions. To adress this issue, we consider a two-players bandit game setting where the actions of one of the player affect the other one. Building upon this setup, we extend the Coase theorem [Coase, 2013], which suggests that the optimal approach for maximizing the social welfare in the presence of externality is to establish property rights, i.e., enabling transfers and bargaining between the players. Nonetheless, this fundamental result relies on the assumption that bargainers possess perfect knowledge of the underlying game. We first demonstrate that in the absence of property rights in the considered online scenario, the social welfare breaks down. We then provide a policy for the players, which allows them to learn a bargaining strategy which maximizes the total welfare, recovering the Coase theorem under uncertainty.

Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality
Antoine Scheid!
Aymeric Capitaine'
Etienne Boursier
Eric Moulines'
Michael Jordan
Alain Durmus
Centre de Mathématiques Appliquées - CNRS École polytechnique Palaiseau, 91120, France INRIA Saclay, Université Paris Saclay. LMO Orsay. 91400, France
University of California, Berkeley Inria, Ecole Normale Supérieure, PSL. Research University Paris, 75, France
Abstract
In economic theory, the concept externality refers to any indirect effect resulting from an interaction between players that affects the social welfare. Most of the models within which externality has been studied assume that agents have perfect knowledge of their environment and preferences. This is major hindrance the practical implementation of many proposed solutions. To address this issue, consider two-player bandit setting where the actions of of the players affect the other player and we extend the Coase theorem [Coase, 2013]. This result shows that the optimal approach for maximizing the social welfare in the presence of externality to establish property rights, i.e., enable transfers and bargaining between the players. Our work removes the classical assumption that bargainers possess perfect knowledge of the underlying game, We first demonstrate that in the absence of property rights, the social welfare breaks down. We then design policy for the players which allows them to learn bargaining strategy which maximizes the total welfare, recovering the Coase theorem under uncertainty.
Introduction
The concept of externality used in economics to capture phenomena that impact the global welfare stemming from economic interactions without any compensation [Buchanan and Stubblehine, 2006, Shah et al., 2018]. Externality is generally considered as market failure since they result in loss of collective welfare. Given its practical importance [Dahlman, 1979, Greenfield et al., 2009], mechanisms that characterize and mitigate externalities central to modern economic thinking.
first approach to tackle the adverse effects of externalities modern economics was based on quotas and taxation [see, e.g., Pigou, 2017, and the references therein]. However, Coase's 's theorem [Coase, 2013] shows that the presence of well-defined property rights and low transaction costs, parties affected by externalities can privately negotiate efficient solutions, and recover welfare efficient allocation through transfers and bargaining.
Throughout the paper, we use the following simple example to illustrate our results.
Example 1. Consider two firms (upstream) and 2 (downstream) respectively producing quantities Q 2 and q2 2 of good sold at a fixed price p > 0. They incur strictly increasing and convex costs, captured by the differentiable cost functions C₁ q1 + C, (qi) and Cg 42 + Cz(42), satisfying
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(1) = 0 and (0) = O. We assume that,fim 1 exerts on firm 2 constant externality a > 0 per unit produced. In other words, their functions (or utilities) are given by
T (1 p4 - ci and (2 92) = p42 c2(92) aqq
One simple concrete illustration consists in upstream firm emitting pollutants that reduce the downstream firm's production. If the upstream firm owns the property rights, it may receive a payment from the downstream one to reduce its output and thereby pollution. On the other hand, if the downstream firm owns the property right, it may require compensation from the upstream firm to allow its operation.
The Coase theorem demonstrates that in both cases with appropriate property rights, the resulting levels of production would be welfare efficient. The theorem is typically explained in texthooks under the assumption that the players have perfect knowledge of their own utility or profit function, as well as that of others. However, this assumption is unlikely to hold in real-world scenarios, where players have to learn about their own preferences and those of their competitors.
This example is, of course, a simplification of real world scenarios. For example, Abildtrup et al. [2012] consider a more complex setting to model the interaction between farmers and waterworks in Denmark where the farmers have the property rights whereas the waterworks can pay to reduce pollution. In particular, they demonstrate the failure of the theorem, attributing to the breakdown of the main assumptions: no transaction costs, maximizing behaviors and perfect information, with an important focus on strategic behaviors and the asymmetry of information. We restore the latter in our work and provide foundations for the theorem to hold in more realistic scenarios.
A key question is whether the Coase theorem holds when players learn their preferences over time.
We investigate this question within the framework of a multi-armed bandit learning. We build upon recent works that extend the classical bandit setting to economics in which there are two players interacting via principal-
protocols [Dogan al., 2023b,a, Scheid et al., 2024]. This allows us to capture, for example, version of the two-firm problem where firms are uncertain regarding both their profit functions and the degree of externality on other firms. We represent production decisions in this problem as arms which can be played by the firms at any round over time, with the goal of finding decisions that maximize their rewards. More precisely, we assume that the reward of the upstream firm only depends on its own action, while the reward of the downstream firm depends on both its action and the upstream firm's 's action. This dependency on both actions allows us to capture externalities.
The property rights in Example 1, or more generally over bandit instance, amount to giving a firm the possibility of engaging in monetary transfers that influence the arms that are played over time. The owner of the bandit instance will face a problem of bandit learning with transfers with an upstream player who is also learning his preferences.
To account for the efficiency of a policy in this setup, we extend the classical static notion of welfare efficiency to the online setting. We say that a policy is Welfare efficient if the social welfare regret is sub-linear. Proving the Coase theorem within our setup therefore boils down show that if the bandit owner (who is without loss of generality the upstream player in this study") runs a no-regret bandit algorithm to learn and exploit his preferences, the downstream player can then choose an optimal transfer scheme leading to a aineirn total regret.
Our contributions are as follows:
We show that when an upstream agent exerts externality on a downstream agent, in the absence of property right, the social welfare breaks down. Put differently, no joint policy of the agents can be welfare efficient.
We then introduce property rights and show how it affects the game. this case, bargaining and transfers are available to the players. We propose policy for the downstream player that leads to welfare efficiency when the upstream player follows any black-box no-regret policy under mild assumption. This solution addresses the breakdown issue at equilibrium. Put together, we show an online version of the Coase theorem.
'The fact that efficiency is restored whoever is given the property rights is known as the invariance property of the Coase theorem.

---

2 Setup and Inefficiency of Externality
2.1 Bandit game
We consider a sequential bandit game in which two players (downstream and upstream) simulta- neously play actions in bandit instance for horizon T E N*. The action set for both players is A = (1,.... K), K N'.
The reward distributions of the agents differ. Given a family of distributions {7e E AA} indexed by A, the upstream player's rewards are provided by an i.i.d. family of random variables
(ta(t)) AA
where (t) ~ V for any t E [T] and a E A.
To model the externality exerted by the upstream on the downstream player, we assume that the latter has reward that depends both her action and that of the upstream player. Formally, this is modeled through a family of distributions (Mab : a, b E A} double-indexed by A and an i.i.d. family of random variables
(t)e)T(t))EETT) a, A}
where Xa,b(t) ~ Vo,b
the reward received by the downstream player time if she pulls the arm and the upstream player pulls the arm a.
Players. We assume that players risk-neutral expected-utility maximizers, and we define their expected utilities for any (a, b) E Ax A as
e (aP(()= - (dzz) E ER and v down (a, b) (a.b))/ I (ax) E R.
The distributions (7a)aEd and (Va.))a. are unknown to both the downstream and the upstream players and they aim to learn the distributions with best mean rewards by sequentially observing samples from (t)
E A} and {(Xa,(tt))e(()) a, b, A}.
Moreover, suppose that players rational in hindsight; that is, they minimize their regret. Formally, the upstream player aims to minimize his regret defined as
R.P (T, I1 Tu*
E
Σ "P (A.)
where -u max v (a)
(I)
aEA
while the downstream player seeks minimize her external regret defined
Ordown (T, Th IIdown) =
max e down (A,, down (A,, B.) PEA
(2)
where the players' actions (At)er (Be) well as their policies L1uP, Ildown are defined below. Note that the utility of the downstream player also depends on the actions taken by the upstream player, which represents the externality exerted by the upstream player on the downstream player, hence the strategic dimension of our setting. We first consider game where no property right is defined, so each player free to pick his preferred arm irrespectively of the other player's choice. This will result in breakdown of the total utility.
Policies without property rights. Consider first the upstream player. Based policy THe (for example a no-regret bandit algorithm such as the Upper Confidence Bounds algorithm (UCB) [Auer, 2002] the e-greedy algorithm [Robbins, 1952, Langford and Zhang, 2007]), we define his history (H. "eet)r)) by induction. We set Hap = Ø and supposing that H.ppa is defined for I E [T], then
H. = H..... U {A++1, Vi+1, ZAr.s (t+ 1)},
where (Va).eN- is family of independent uniform random variables in [0, 1]. allowing for random- ization in the policy, and A is provided by II following IIMP; (V++1. H.p..)) + Ac+1.
Second, consider the downstream player and an algorithm IIdown (specifically no-regret bandit algorithm). We define her history (H (H.dwwn.n) )ee(ry) by induction. We set H Hdoon. Ø and supposing that H downn is defined for E [T], then
H.dowm H. down. U (A1t1, B1t1, X Bun 1))
3

---

where (U.) is family of independent uniform random variables in [0, 1] allowing for random- ization in the policy and Be+1 is provided by Ioow following IIdow; (U++1; H4 (lwon..) H B1+1-
Welfare efficiency. We now introduce the notion of Welfare efficiency for our setup. The global utility, or social welfare, of the players at round is defined as (")(A,) + udown (A,, B,). We define socially optimal action (a* ((w) E AA x A of the game as
E argmax (a) (a) + w down (a,
(3)
as well as the global regret (or social welfare regrer) associated with policies h and Ioow as
deth (T, 1P 11 (ldown) = ' (o"P((a*) + ddown (M ())) E tD (Ar) + udown (A,, B.)
(4)
Then, the joint policies ho and IIdown for the players are said to be Welfare efficient if
lim A (T, IT IIdow) ) =
T T
Intuitively, this condition implies that the frequency of the socially optimal action (a" tends to I as 7" goes to infinity. In this sense, it mimics the usual, static Welfare efficiency criterion. As we will see, (II IIdlwnn is typically not Welfare efficient when there is disalignment in the game between the players' individual interests based on their rationality and the social welfare.
2.2 Inefficiency without property rights
We first present result that captures the adverse consequence of externality on social welfare. The upstream player does not take into account the indirect cost incurred by the downstream player when he chooses his action. This drives the social welfare away from its optimal level. We illustrate this fact within our simple bilateral externality example.
Example 1 (continuing from 1). We show that the competitive outcome, where each firm maximizes its profit independently, is not welfare efficient in the presence of externality. Define the social welfare as the function
W (21.92) m + 12(21, 92) = p(ai + 92) - (q) + c2((2)) aqq
(5)
By definition, the welfare efficient outcome (gi,93) E 12 satisfies W W(i (0i,4))== > W W(q for any (gi,92) E RR, Since W is differentiable and strictly concave, (9i o ) is uniquely defined by the condition VW(gi.93 0. that is ((g1)) a and d((2))= =
(6)
Note that at the welfare efficient optimum, firm does not equalize marginal cost with marginal profit, but produces less account for the negative effect of externality firm 2. We now characterize the competitive outcome (g' 4/) E TR? Since wi and ny are differentiable and strictly concave, (gh (() satisfies
G(d))= = and d54))= =
(7)
For the competitive outcome to be welfare efficient, we require, by Equation (6) and Equation (7), (( = d(g)) that is a 0.
This proves that whenever there are externalities, no competitive outcome is efficient.
We show that in model, when there is property right and under mild assumptions, no achievable policy is welfare efficient whenever there misalignment between the players' interests and the social welfare. The upstream player's policy 11FP is said to be no-regret if
limy-++00 (T, ITT) / 0, where Run defined in (1).
Theorem 2. Suppose that argmax (a)( is the singleton {a") and that
(a + dowwn ((a,bbw) ) (a()) + down (a 0. b) > 0,
(8)
for any E A. In the absence of property rights and when the upstream player runs any no-regret policy IIDP, we have RwS (T, II.. Iddow)) Q(T). Therefore, Rww (T. 1l I[dww)) Q(T)) and (IIup, [1dowa] is not welfare efficient.

---

Condition (8) in Theorem 2 represents the unaligmment between the upstream player's preference and the optimal choice from social welfare point of view. Note that the upstream and downstream players can both have an o(T) external regret, while the social welfare regret still grows linearly with 7 because the unfavorable interactions between their policies.
3
Online Property Game with Bargaining Players
3.1 Online Property Game
We now consider the same repeated game in the form of a property game where one of the players possesses the bandit instance (upstream player). As in the original setup of Coase [2013], the other player (downstream player) will provide the bandit owner with transfers to incentivize him choose some specific action and influence the outcome of the game in her favor.
We show in Appendix B that our method applies similarly when property rights given to the upstream player rather than the downstream player. Hence, there is no loss generality in considering the aforementioned framework. In this sense, recover the invariance property of the Coasean bargaining [Mas-Colell et al., 1995].
Example 1 (continuing from p. 1). We now illustrate how Coasean bargaining re-instaures efficiency. Suppose without loss of generality that property rights such that firm 2 can pay R. to firm I for it to operate at a level @1. Profits become
T2 (11, 42, T, T1 + T2(11 92) - 1 (9:4:17 and Ti T, T((1) + (91=117
Consider the competitive outcome (41, T, (1) E TR which satisfies
Q1 = (T, E arg max कं (0/, T, (1) and ne(2n 42, T1)) 7.)
4:30
7o (2 ( (T)) 7',
The condition on q1 accounts for the rationality of the firm and the fact that its choice depends on the payment )1). Obviously, the optimal solution is reached for q1 91 and T = max IT T1(4') T (41). Plugging this back in the expression of ß22 then yields
(g), 42) = argmax, mI (41) + x2(()) argmax %f W(d.g)) h
so the competitive outcome (41,q) Q2) is welfare efficient.
The transfers at each step can be interpreted as contract between two players [see, e.g., Bolton and Dewatripont, 2004, Salanié, 2005, for general contract theory] and providing the right amount of incentives relates to adjusting contract in online setting [see Dütting al., 2019, Guruganesh et al., 2021, Zhu et al., 2022, Fallah and Jordan, 2023, Guruganesh et al., 2024, Ananthakrishnan et al., 2024, for learning-basee perspectives about contracts].
Similarly to Example 1, we modify the players' policies to now account for the transfer 7(t) that the downstream player offers at round f to the upstream player if he picks action âr The downstream player's policy at round does not only output an arm B, but now a triple (āg, -t), Bc), where B, is the arm that she should play and o, is the arm on which transfer T T()) is offered to the upstream player. On the upstream player's 's side, the policy still outputs an arm A, to play but also takes as an input the incentive (āe, r()). In addition, the instantaneous utility of the upstream player becomes A. (f) 1a, (f)) whereas the downstream player receives X AA (f) 11a (A.)r(t).
Policies with property rights. Based on policies NuP for the upstream player and Idown for the ) by induction. We set
downstream player, we define their histories ((EPP)) and Jydown.P are defined for t E [T). then H Ø, Hg dowwn. 2 and supposing that H.PPP H
HUP.P = H.PP. U (0t+1,7(1++ 1), A4ti, V41 Zeisa (t 1)}
and
H downnp H41
H.
U (āc+1, S
A1t1 Bi+1, U44 X XA Biy (t + 1)]
5

---

where (Vo).ENt, (Us)eEN- are two families of independent uniform random variables in [0, 1] allowing for randomization in the policies, and the remaining quantities are given by Ioo (U++1, (U441,H4omny H(dom..)) + (ā++1, r(++1), B++1) and Ipp: (ã++1, (t++1), V4+1, H,, A4+1-
Players' goal. Given transfer 7 from the downstream to the upstream player on arm â, actions and respectively are chosen by the upstream and the downstream player, the upstream player's expected utility reads 6.P (a) + (a(r) while the downstream player's expected utility is udown (a, b) 1a(a)T.
This defines the upstream player's expected regret for a horizon T
(T, mT P How
Σ max {u (P((a)) + 12, (a))(()) (c )+) + 1a (A))
(9)
aEA
Based the upstream player's utility, the downstream player aims single round at proposing an optimal transfer 7opt on an arm aopt E A as well as picking an arm jopt E A which solves
maximize (a, b) + (dowa (), -T
(10)
such that E R4, A.a E argmax EA (d))))) +1))'
Her regret for any horizon 7' is defined
Indown(T (T.1.) HI. Mp Mdowa) Ty
E
Σ e down (At, B:) - 1la 11, (A.)T(1)
(II)
where we define 2 ,down mownn (a Bopt) 7Pt as the optimal utility she aim for. We can see that the downstream player's influence is exerted through her action choice B, as well as through transfers which enable her influence the upstream player's actions. Hence, the notion of external regret is obsolete here. The game has now the form of a repeated Stackelberg game [Von Stackelberg, 2010].
Lemma 1. Recall that μ pd.www is the downstream player's optimal reward defined solution of (10). We have ut" .lown = maxa,DEAA ( (udoon((a + (aP(a)} - mmx,a (V [')}, as well as (aopt, (opt)= = (a²", 1P") and u² p ddown vuP((aW 4o (a=",1" ,1"") = maxa,ee ( (a)+ down (a, b)], where 4ruu is defined in Equation (1). Moreover, for any integer E NN' and policies IIDP, Inlow, we have that
RSS (T, ITP. Iddwn) < RDD (T, HI III.IIII...
IIdown) + +DRdown (T, HII IIdown).
This lemma has interesting economic interpretation: if both players individually seek for their own interest within this online property game, they will together converge towards the optimal global utility. Individual rationality moves the outcome of the game towards the optimal social welfare. The transfers allow the players to align their goals and share the global reward, in line with the Coase theorem. Consequently, if both players run no-regret policies 11b and I1dowa, the social welfare regret will also be in (T). The of the paper shows that such no-regret policies exist. To this end, we introduce the following assumptions.
Without loss of generality, corresponds to the following assumption on the reward distribution (Ya)ae in R.
assume that the upstream player's utility is rescaled and shifted, which
H1. For any E A. we have (a) [0, 1].
We now make a high probability bound assumption on the upstream player's 's regret.?.
H2. There exist C, Ç > O, K E [0, 1) such that for any s, E [T] with s s+t < T, any [Talag|K] E R and any policy Ildown that offers almost surely transfer (ā,, r()) = (ā), Far) for any I E {s 1,... 8 + 1}, the batched regret of the upstream following 11ur satisfies, with probability at least 1 1-
s+1
Σ
max (P) + 1a, - + 1a, (Ai)Ta)) < Ct*. aeAA
1=++1
A similar assumption is made in the work of Donahue et al. [2024] but with a stronger instantancous regret bound which does not encompass the UCB's 's regret bound.

---

The constraint on the downstream player's 's algorithm IIg enforces constant incentives associated with any arm a E A withtin the batch, while the incentivized actions (a))e(++1,...d may change. Proposition 2 in Appendix shows that an adaptation of UCB taking account the incentives satisfis H2 with C 8/ K log (KT*), K = 1/2 and Ç = 2. Note that usual bandit algorithms such as AAE, ETC or EXP-IX also satisfy the assumption [see, e.g., Donahue et al., 2024, Lattimore and Szepesvári, 2020].
3.2 Downstream player's procedure
We fix the policy ITPP which can be any algorithm satisfying H2 for the upstream player and introduce the algorithm BELGIC (Bandits and Externalities for Learning Game with Incentivized Coase) which provides a policy achieving sub-linear regret for the downstream player. It can be seen as an online bargaining strategy mitigate externalities. Simply put, BELGIC unfolds in two steps. First note that for any action a E A, the optimal (lowest) transfer to offer to the upstream player to make him choose a
max v (a') - 1 (a)
(12)
a'E.A
as detailed in Appendix A. Therefore, a batched binary search procedure (Algorithm 2) first allows the downstream player to estimate the optimal transfers Tं ..... T with good precision level of 1/T0, where 3 > 0. More precisely, the downstream player offers constant incentive (ā, ra) for batch time steps of length π = [T The observation of T the number steps from the batch for which the upstream player does not pick à allows her to estimate whether тa is above below T
and adjust it, following Lemma in Appendix A under the condition that a, 3 satisfy
B/a < <1 (1-Mk k)
(13)
The procedure needs be run for K[T "Tro[ooo [og, T rounds since have to make [lgg, T batches of binary search of length [T'] on each of the K arms [see Scheid et al., 2024]. This corresponds to the first phase of BELGIC as described in Algorithm
At the end of this stage, the estimated transfers
(fa (aa) satisfy the bound in Proposition 1. These are then used to feed the subroutine Bandit-Alg,
Proposition 1. Under HI and H2, after the first phase of BELGIC which consists in K [[T [log T
steps of binary search grouped in [log2 T batches per arm E A, we have that
P( for any E A, fo 4/T CT(K-1)/2 1)/2
T < fm > 1 - K[log T 1/T0O
The additional term 1/T + C in fa ensures that if H2 holds, the upstream player necessarily plays the incentivized action â at round with high probability. Lemmas 2 and 6 from Appendix C show how the binary search batches in BELGIC allow us to estimate - depending on T - T the number times that arm a has been pulled by the upstream player during the batch.
Then, any bandit subroutine Bandit Alg, such as UCB or e-greedy, for instance, can be run in black-box fashion on the shifted bandit instance, where the rewards are shifted by the upper estimated transfers (fa)aeA- The downstream player computes a shifted history H doww.. such that for any t < K [Ta [log T 1 doown. Ø and for any 1 > K 1[og, 8
fōr, Bi, ((), Xa. B, fa. H.oon if At
(14)
H Hdown.P otherwise
which serves to feed Bandit- following
Bandit-Alg: (U,, F.dowa.P) B.) Ax
(15)
For any family of constant incentives {Ta JaeA E R. we define Rgandit Alg (T, v. f )aeA) as the regret for the downstream player's subroutine Bandit-AN Alg on the bandit instance with shifted means over T rounds, following
Reandit-Ang(T. (T, vs (Ta)oCA) =T T max E. dedwn (1) 1--a Ta]
E
down (āz, B.) Tä,
A2
Note that here, Bandit-Alg aims to maximize the shifted reward (ndown (a, b) - -Ta(LaM)EA
7

---

Algorithm BELGIC
1: Input: Set of actions A [K], time horizon T, subroutine II, upstream player's regret
constants C, K, parameters a and B.
2: Compute Hdown.D 2 for any & & koo, P7[[Ta]
3: for E AA do
4: See Algorithm
5: Ia. = Binary Search(u, [logg 1 [T
6: end for
7: For any action E A, fa = + 1/7 + CT(x-1//2
8: for t= K[T"] loga 7 + 1, ,,..., do
9:
Get recommended actions by Bandit-Alg on the x bandit instance, (ā,, B.) Bandit-Alg(Ui, 7/
10:
Offer a transfer fa. on action āe nothing for any other action d' E A and play action Br. Observe A, (@ 7(t 1), Vú, Hi B.,
11:
if A, = 0₂ then update history A.dow..p.
12:
13:
end if
14: Update upstream player's history H.P.P.
end for
Algorithm 2 Binary Search Subroutine
1: Input: action a, .r. T, Ta: Tu-
2: for d .,..., Ny 1 do
3: Compute mid = (Ta(d) + Ia (d)) 7 0.
4: for df + 1,..., dl + T' do
5: Propose transfer To. (midd on arm and nothing for any other action a' A.
6: A, II (t, miid (a), a, Vi, H:PP.)
7:
if A, + a then: T
8:
end if
9:
Update upstream player's history 7 UPD.P end for
10:
if C7x+B/a T < CT then Return I, (d), 3/a
12: else if 17 <T Cf B/a then (d) -- (d) 1/T and update history Hi Howwn...
else (d) rimid( (d) 1/T and update history H.own.p
13:
14: end
15:
end for
Theorem 3. Assume that H1 and H2 hold. Then BELGIC, ru with a, B satisfying (13) and any bandit subroutine Bandit-Al, has an overall regret Ddlown such that
Deloon (T, 11UP, BELGIC) 2(3 2C + t 2) log, (2T p(++1)/2 11= (1++)++ + 447 1 (T, (Fa FoEA)
+
where, for ease of notation
6
max a.b
min down (a, b)} and a.bEAAxA
down (a, b)}
Knowledge of C and K. An upper bound on C and k is sufficient to compute the hyperparameters in BELGIC. Theorem shows that the bigger C and x are, the worse is the downstream player's regret, hence the interest of knowing them more precisely.
Corollary 1. Assume that the upstream player's distribution (Ya)aEAA is such that holds. In addition, suppose that the distributions (Ya)aEA and (Va,)) (v..))..beAA.. are E-sub-Gaussion and that the upstream player plays Iou = Algorithm 3 (a slight modification of UCB to take into account the incentives). Then the downstream player's 's regret when she runs BELGIC with parameters a 3/4 and 3 1/4 (which satisfy (13)) and subroutine Bandit t -Alg lg UCB satisfies the following upper

---

bound Ri (T, UCB, BELGIC) < (10 + + 322 / (K22(K))) + 8 2) logg (3) 2778/4
+ 2)
The upper bound the social welfare regret in Lemma together with Corollary shows that when the upstream player runs IPp UCB and the downstream player runs BELGIC, the social welfare regret then satisfies Re (T, mp", BELGIC) O(K log(T))(w+1b/2))
In other words, if the downstream player runs BELGIC which produces policy Hown for any upstream policy 11.", jown 11pp) is welfare efficient.
Influence of the upstream performance. It is interesting note that in the downstream player's regret bound, the upstream player's s regret bound in O(T*) plays significant role: the downstream player never learns faster than the upstream player. The latter's performance determines the social welfare convergence rate towards the social optimum. We can observe that the players' bounded rationality [Selten, 1990, Jones, 1999] and personal interest make the game converge towards the optimal social welfare equilibrium even though they are both learning here.
even
Upatrram praft
Uparaam proft DOAMSEEENTT proft
1.2
Dicbal wetfare
Emriiicaal frequences
9.61144
3.0
Randi:
1.5
0.6
341
0.2
0 0000 22 200
#00 38800152
11 1.305
900 STAL 2000
200 05
Figure 1: Empirical frequencies of the upstream player's actions when property rights are not defined (left) and when they are defined (right).
Experiments.
We conclude this section with experiments showing empirical convergence of our algorithm to social optimum. In the simulation, we consider two firms, with firm 1 being upstream and firm 2 being downstream. Their profit functions are respectively given by
JT > max
q1
2
10
91
10
and
6
6
( q2) + max
-16
+
8
91
42
0
10
10
10
50
Thus, firm I's and firm 2's profit functions depends quadratically on yi with an firm 1 optimum at di and a social optimum at of Note that the expression of T2, Q2 has very little influence compared to 41 which allows to plot profits for only one value of q2-
We discretize the setup, consider bandit instance (horizon T' 5.10 10 arms, average over 10 rounds) and we assume that UCB is used as subroutine. In the first setting, there are no property rights and each firm runs UCB on their side. Second, property rights are defined and firm 2 runs BELGIC as its policy. The plots in Figure display the empirical frequencies and show empirically the effectiveness of BELGIC mitigate externalities.
4 Related work
Our work addresses the impact of externalities and therefore related to taxation theory [see, e.g., Mimrlees et al., 2011, Salanie, 2011, and the references therein], prominent solution for this issue, as
Note that it is K and not / V here, since the action space is of cardinality K² for the downstream player.

---

exemplified by the Pigouvian tax [see Pigou, 2017]. Taxation is a fundamental aspect of all developed economies, with 30% to 50% of national income derived from taxes. The topic has been fruitful for various scenarios, including the carbon tax [Carattini et al., 2018, Metcalf and Weisbach, 2009], alcohol markets [Griffith et al., 2019) 91, or business taxation [Boadway and Bruce, 1984]. Taxation can also be studied through an operations research lens, where it is used to enhance system efficiency or manage specific games IRoughgarden, 2010, Caragiannis et al., 2010, Bild and Vinci, 2019]. Recent work by Cui et al. [2024] explores online mechanisms to maximize efficiency in congestion games.
Mechanism designs [Myerson, 1989, Nisan and Ronen, 1999, Laffont and Martimort, 2009] allow to design games that have specific desired outcomes. Deploying these mechanisms in their classical ecnomical form assume that players' utility functions are known a priori. which is often unrealistic. There is major need to blend mechanism design with machine learning.
However, our approach differs, since, drawing inspiration from Coase's theory, we implement an online version of his theorem [Coase, 2013, Cooter, 1982], incorporating uncertainty to tackle the breakdown of social welfare in an online setting. We use the bandit setup [see Lattimore and Szepesvári, 2020, Slivkins et al., 2019] as a general and convenient way to model the game introduced by Coase. However, our work differs from considering single agent playing a bandit game. Instead, we focus on the more general problem of multi multi-players bandits, a field receiving a growing attention from the community [see e.g., Boursier and Perchet, 2019, 2022, Sankararaman et al., 2019].
Our approach is inspired by the principal-agent model introduced by Dogan et al. [2023b], which was further extended by Dogan al. [2023a], Scheid et al. [2024]. However, unlike the models proposed in the work of Dogan et al. [2023b.a], we do not specify a particular bandit al algorithm for the upstream player and instead, we allow him to use any no-regret algorithm satisfying H2 in black-box fashion. Conversely, the model of Scheid et al. [2024] assumes that the upstream player is always fully informed and best-responding, whereas we assume that he is also learning. Chen al. [2023b] leverages a similar model to study information acquisition by a principal through an agent's actions. However, in their model, the agent is also almighty and knows exactly the costs associated with each action. Designing incentives in an unknown environment is related to auction theory incorporating uncertainty, as is explored in the work of Feng et al. [see 2018], Li al. [see 2023]. Similar issues have been explored in the Reinforcement Learning framework within a lcader-follower game [see Chen et al., 2023a, with quantal responses by the follower] or in a principal-agent game with incentive design as done by Ben-Porat et al. [2023]. Donahue et al. [2024] also study a two-players repeated Stackelberg game on a bandit instance but instead of allowing for transfers, their main focus concerns the achievability of Slackelberg equilibrium through iterations of bandit policies: the same kind of goal also appears in Collina et al. [2023]. Such principal-agent setups are of some interest to model various real-world situations such as the design of fundings for hospitals [Wang et al., 2024] or have been studied with multiple agents through the lens of auction design in dynamic setups [Bergemann and Said, 2010, Chen et al., 2023c], or to account for faimess [Fallah et al., 2024].
In our game, the downstream player needs learn the optimal transfers/incentives to offer to the upstream player. This is related to the Incentivized Exploration literature [Mansour et al., 2016, Simchowitz and Slivkins, 2023, Esmaeili et al., 2023], which is often cast in terms of benevolent planner who aims to optimize the global welfare of agents via plausible recommendations. A related model is Bayesian Persuasion [Kamenica and Gentzkow, 201 I], where sender influences a receiver's action through sending a signal. This model has begun to be studied in learning settings [see, e.g.. Castiglioni et al., 2020, Bernasconi et al., 2022, Wu et al., 2022b,a].
5
Conclusion
This paper studies a model of externalities in a two-players sequential game where both players learn their optimal actions. We first show that when the players act independently, then a misalignment between the players' interests and the social welfare leads to a breakdown of the global utility. We then introduce interactions through transfers, which restores a social welfare optimum, representing the online version of the Coase theorem. To that purpose, we propose policy for the downstream player which allows her to estimate the optimal transfers as well as choosing the best actions. The mathematical difficulty comes from the learning aspect on both sides. Since our work is coined in learning framework for mechanism design, several directions for research are open, as for instance extensions to the multi-agent setting, which raises many questions.
10

---

Acknowledgements
Funded by the European Union (ERC, Ocean, 101071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
Jens Abildtrup, Frank Jensen, and Alex Dubgaard. Does the coase theorem hold in real markets? an application to the negotiations between waterworks and farmers in denmark. Journal of environmental management, (3(1):169-177) 2012.
Nivasini Ananthakrishnan, Stephen Bates, Michael Jordan, and Nika Haghtalab. Delegating data collection in decentralized machine learning. In International Conference Artificial Intelligence and Statistics, pages 478-486. PMLR, 2024.
Peter Auer. Using confidence bounds for exploitation-exploraiii trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Omer Ben-Porat, Yishay Mansour, Michal Moshkovitz, and Boaz Taitler. Principal-agent reward shaping in mdps. arXiv preprint arXiv:2401.0022 2023.
Dirk Bergemann and Maher Said. Dynamic auctions: A survey. Wiley Encyclopedia of Operations Research and Management Science, 2010.
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Sequential information design: Learning persuade in the dark. Advances Neural Information Processing Systems, 18:11917-11999 2022.
Vittorio Bild and Cosimo Vinci. Dynamic taxes for polynomial congestion games. ACM Transactions on Economics and Computation (TEAC), 7(3):1-36, 2019.
Robin Boadway and Neil Bruce. A general proposition on the design of a neutral business tax. Journal of Public Economics, 24(2):231-239, 1984.
Patrick Bolton and Mathias Dewatripont. Contract theory. MIT press, 2004.
Etienne Boursier and Vianney Perchet. Sic-mmab: Synchronisation involves communication in
multiplayer multi-armed bandits. Advances in Neural Information Processing Systems, 32, 2019.
Etienne Boursier and Vianney Perchet. A survey on multi-player bandits. arXiv preprint arXiv:2211.1625,, 2022.
Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
James M Buchanan and Wm Craig Stubblebine. Externality. In Inframarginal Contributions to Development Economics, pages 55-73, World Scientific, 2006.
Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. Taxes for linear atomic congestion games. ACM Transactions on Algorithms (TALG), 7(1):1331, 2010.
Stefano Carattini, Maria Carvalho, and Sam Fankhauser. Overcoming public resistance carbon taxes. Wiley Interdisciplinary Reviews: Climate Change, 95))e531, 2018.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi. and Nicola Gatti. Online bayesian persuasion. Advances in Neural Information Processing Systems, 13:16188-16198. 2020.
Siyu Chen, Mengdi Wang, and Zhuoran Yang. Actions speak what you want: Provably sample- efficient reinforcement learning of the quantal stackelberg equilibrium from strategic feedbacks. arXiv preprint 11x::23077..085, 2023a.

---

Siyu Chen, Jibang Wu, Yifan Wu, and Zhuoran Yang. Learning to incentivize information acquisition: Proper scoring rules meet sancipal-agen model. International Conference on Machine Learning. pages 5194-5218. PMLR, 2023b.
Yurong Chen, Qian Wang, Zhijian Duan, Haoran Sun, Zhaohua Chen, Xiang Yan, and Xiaotie Deng. Coordinated dynamic bidding in repeated second-price auctions with budgets. In International Conference on Machine Learning, pages 5052-5086. PMLR, 2023c.
Ronald Coase. The problem social cost. Journal of Law and Economics, 56(4):837 877, 2013. wwwpc..pp....................... org/ RePEc jlawec: :ttp:wew:doi:::o 0086/674772
URL Pettps:/EEooPaaene
Natalie Collina, Eshwar Ram Arunachaleswaran, and Michael Kearns. Efficient stackelberg strategies for finitely repeated games. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 643-651, 2023.
Robert Cooter. The cost of coase. The Journal of Legal Studies, 11(1):1-33, 1982.
Qiwen Cui, Maryam Fazel, and Simon S Du Learning optimal tax design in nonatomic congestion games. arXiv preprint arX1v:2402.07437, 2024.
Carl Dahlman. The problem of externality. The journal of law and economics, 22(1):141-162. 1979.
Ilgin Dogan, Zuo-Jun Max Shen, and Anil Aswani. Estimating and incentivizing inorr agents with hidden rewards. arXiv preprint arXiv:2308.66717, 2023a.
Iigin Dogan, Zuo-Jun Max Shen, and Anil Aswani. Repeated principal-agent games with unobserved agent rewards and perfect-knowledee agents. arXiv preprint arXlv:2304.07077, 2023b.
Kate Donahue, Nicole Immorlica, Meena Jagadeesan, Brendan Lucier, and Alcksandrs Slivkins. Impact of decentralized learning player utilities in stackelberg games. arXiv preprint arXiv:2403.00/88 2024.
Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen Simple versus optimal contracts. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 369-387, 2019.
Seyed A Esmaeili, Suho Shin, and Alcksandrs Slivkins. Robust and performance incentivizing algorithms for multi-armed bandits with strategic agents, arXiv preprint arXiv:2312.07929, 2023.
Alireza Fallah and Michael I Jordan. Contract design with safety inspections. arXiv preprint arXiv:2311.02537, 2023.
Alireza Fallah, Michael I Jordan, and Annie Ulichney. Fair allocation in dynamic mechanism design. arXiv preprint arXiv:24406.0114 2024.
Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. Learning to bid without knowing your value. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 505-522, 2018.
Thomas K Greenfield, Yu Ye, William Kerr, Jason Bond, Jürgen Rehm, and Norman Giesbrecht. Externalities from alcohol consumption in the 2005 us national alcohol survey: implications for policy. International journal of environmental research and public health, 6( 6(12):3205-3224, 2009.
Rachel Griffith, Martin O'Connell, and Kate Smith. Tax design in the alcohol market. Journal of public economics, 172:20-35, 2019.
Guru Guruganesh, Jon Schneider, and Joshua R Wang. Contracts under moral hazard and adverse selection. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 563-582, 2021.
Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inhal Talgam-Cohen, Caamanouil-Vasilenn Vlatakis- Vlatakis-Gkaragee Gkaragkounis, Joshua R Wang, and S Matthew Weinberg. Contracting with a learning agent, arXiv preprint arXiv:2401.16199 2024.
Bryan D Jones. Bounded rationality. Annual review of political science, 2(1):297-321, 1999.
12

---

Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6): 2590-2615, 2011.
Jean-Jacques Laffont and David Martimort. The theory of incentives: the principal-agent model. In The theory incentives. Princeton university press, 2009.
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. Advances in neural information processing systems, 20, 2007.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Ningyuan Li, Yunxuan Ma, Yang Zhao, Zhijian Duan, Yurong Chen, Zhilin Zhang, Jian Xu, Bo Zheng, and Xiaotic Deng. Learning-baat based ad auction design with externalities: the framework and maachhng-bbssd approach. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1291-1302, 2023.
Yishay Mansour, Aleksandrs Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian explo- ration: Incentivizing exploration in bayesian games. arXiv preprint arXiv:1602.07570. 2016.
Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Micrveconomic Theory. Oxford University Press, New York, 1995.
Gillbert Metcalf and David Weisbach. The design of carbon tax. Harv. Envtl. Rev., 33:499, 2009.
James Mirrlees et al. Tax by design: The Mirrlees review. OUP Oxford, 2011.
Roger B Myerson. Mechanism design. Springer, 1989.
Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of compuling, pages 129-140, 1999.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44:660-681, 2016.
Arthur Pigou. The economics of welfare. Routledge, 2017.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, page 527-535, 1952.
Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78-86, 2010.
Bernard Salanié. The economics of contracts: a primer. MIT press, 2005.
Bernard Salanie. The economics of taxation. MIT press, 2011.
Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, (3):1-35, 2019.
Antoine Scheid, Daniil Tiapkin, Etienne Boursier, Aymeric Capitaine, El Mahdi El Mhamdi, Éric Moulines, Michael Jordan, and Alain Durmus, Incentivized learning in principal-agent bandit games. JCML, 2024.
Reinhard Selten. Bounded rationality. Journal of Institutional and Theoretical Economics (JTTEYZeitschrrjf für die gesamte Staatswissenschuf.. 146(4):649-658, 1990.
Virag Shah, Jose Blanchet, and Ramesh Johari. Bandit learning with positive externalities. Advances in Neural Information Processing Systems, 31, 2018.
Max Simchowitz and Alcksandrs Slivkins. Exploration and incentives in reinforcement learning. Operations Research, 2023.
Aleksandrs Slivkins al. Introduction to multi-armed bandits. Foundations and Trends Machine Learning, 12(1-2):1-288 2019.
13

---

Heinrich Von Stackelberg, Market structure and equilibrium. Springer Science & Business Media, 2010.
Serena Wang, Stephen Bates, Aronow, and Michael Jordan. On counterfactual metrics for social welfare: Incentives, ranking, and information asymmetry. In International Conference on Artificial Intelligence and Statistics, pages 1522 1530. PMLR, 2024.
Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang. Zhuoran Yang, Michael Jordan, and Haifeng Xu. Markov persuasion processes and reinforcement learning. In ACM Conference on Economics and Computation, 2022a.
Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. arXiv preprint arXiv:2202. 10678, 2022b.
Banghua Zhu, Stephen Bates, Zhuoran Yang. Yixin Wang. Jiantao Jiao, and Michael Jordan. The sample complexity of online contract design, arXiv preprint arXiv:2211.0577 2022.
14

---

A Algorithmic Subroutine for the Binary Search
Optimal Transfer. For any given round I, action a E A and O, the downstream player can incentivize any best-responding upstream player to choose by offering transfer, zg IR+, defined as:
max v (a') (a) +E.
a'EAA
With this transfer, holds that for any d' A, a' * a, we have (a"(a') < (a) + T ensuring the upstream player's action A, since action yields superior reward. Consequently,
lim T c0
max u (a') - (a)(a)
a'EA
represents the infimal transfer necessary to make arm the best upstream player's choice.
First step of BELGIC: estimation of the optimal transfers. Suppose that consider arm a E AA and that the downstream player offers an incentive тa to the upstream player if he picks this arm. We consider this procedure with a constant incentive Ta for a batch of time steps of length / [70] due the fact that the upstream player is learning [see Perchet et al., 2016, for batched bandits in the usual multi-armed setting). Lemma 2 shows that for BELGIC to accurately estimate Tø with high probability, it must hold
CF <// which equivalent to CT < 1/2
(16)
This is why impose the condition (13) and B, namely 8/a < 1 K, which ensures that k(a- 1) 0 and therefore l T=(00-13+8 12+8 0. More precisely, we define for [K]
Aa = (a - 1) [og, T
which is the step after which starts the binary search procedure on arm a. For any d (1...., [log2 } on arm o, we define
ka,d = Ao + (d - 1)π
(17)
as the step after which starts the d-th batch iteration on arm a, and we consider
T T = Card {t E {kaa + I..... ka, + T) such that A, + a}.
(18)
where (At) (1, ...., K floga relry is given by Algorithm 2. Lemma 2 shows that for any A, d {1..... [log2 I1, with high probability
ifT T - and T7. CT then T -id 1/T
(19)
where fa.d the current estimate of = offered for iteration ka.d. In case (18) does not hold, means that the upstream player has misplayed and has chosen most of the steps suboptimal action, leading to an instantaneous regret for him larger than the bound given in H2. This is why (19) holds with high probability. To sum up, the first phase of BELGIC consists in [log, T batches of binary search on each arm a E A to obtain a precision level 1/T on the optimal transfer T.
During this phase in Algorithm 2, we define F. (d) E R4 the upper estimate and (d( R4 as the lower estimate of T after d E (1..... [log, T rounds of binary search on arm a. For any t E [T'] and a E AA, we define - (t) (F. + I (t)) 2. Fa (d)d), Ia (d), 7-uid (d) are updated at the end of the d-th binary search batch of length T on arm a. We define Ny [log, T as the number of binary search steps per arm.
After this first binary search phase, the downstream player computes estimates of the optimal transfers T
(Ga)aEA = (Fa(Ooog, TT1) + 1/T CT(x-1)/22 )
and offers these transfers a make the upstream player play any action à e AA she wants.
Second Step. After the first phase during which the optimal incentives are estimated by the down- stream player through (fa) she runs in the second phase the subroutine Bandi on the A A bandit instance driven by her action B, and the upstream player's one A,. More precisely, any bandit subroutine Bandit-Alg such UCB or e-greedy, for instance, can be run in black-box fashion
15

---

on the shifted bandit instance, where rewards are shifted by the upper estimated transfers (fa aEA The downstream player computes shifted history H.loon.P Ø for any t & [ [lg T and for any 1 > K [ [log2 T
{
fāe, Bi, (t,, fa H.-rm. if az A Hdorn. otherwise.
A.dowm.p
which serves to feed Bandit-Alg following Bandit-Alg: (U,, H + (āz, B.) E E A. Note that here, Bandit-Alg Alg aims to maximize the shifted reward (wdown (a (a).
Based on this decision by Bandit- Alg, IId offers the incentive fa. associated with action ās and plays action B,. Lemma 5 ensures that a, is the upstream player's hest choice. Therefore, H2 ensures that the upstream player will not deviate from the downstream player's recommendation with high probability.
B Invariance when the property rights are given to the downstream player
Our focus in the paper was the case where the upstream player possesses the bandit instance and receives monetary payments. We argue here that the symmetric situation, i.e. when the property rights are given to the downstream player, can be analysed in the exact same way.
Assume that the the downstream player owns the bandit instance. This implies that (i) they can prescribe what arm the upstream player has to play each round, and (ii) the upstream player may perform monetary transfer to influence the arm they are allowed to pull.
Consider the same bandit setup as before. Formally, the downstream player's ss action is (Ar, B,) e A x A where A, is the arm that the upstream player is prescribed to pull (he cannot deviate since the downstream player has the property rights), while B, is the arm played by the downstream player. On the other hand, the upstream player's 's policy outputs at each round the action (āz, (t)) E A x R,, where ā is the arm they choose to incentivize and r(t) is the amount of transfer. It means that the downstream player receives a transfer 7(t) if she prescribes action A, = āg. As a consequence, the instantaneous utility of the upstream player is AA, 1a, (()), while the downstream player receives X B, + 1a, (At)r(t). In that case, the upstream player may perform a binary search on each arm E A to identify the optimal incentive Th by considering Card {1 E [T] such that â = a} during batches designed for the binary search and then play on the shifted bandit instance as we explained. This situation and the upstream player's 's strategy are now equivalent to the one presented before.
C Proofs and Technical Results
Recall that we defined the shifted history Fedoon.. that will serve to feed IIdown at time as Addwn..p (ā., r(s), A,, V., ZA, (s))
Theorem 4. Suppose that argmax (a) is the singleton {a and that
n (a"( + yownn (a (a" ,b"h) (a.) + downn (a", > 0,
for any b A. In the absence of property rights and when the upstream player runs any no- regret policy 11m2, we have Row (T, 11up (1ddwa) > T'A - RRPP [1=P) A uP, where Aup min EAA ("P(a")) - u (a') and ^ = " (a + down (a bow) - maxses (a") gooon (a",b)). Therefore, Rew (T, HIu Ildown = (() and (IIHP) IIdown) is not welfare efficient.
Proof of Theorem 4. Since argmax (a) is the singleton {a-P), }. we define Au min (a) u (a?)) (a'( as the upstream player reward gap and Aaw enP (asw) + (a")
glown (as" baw) m (u (a") )+ + down ddown(a. b)) as the social welfare reward gap if the up- stream player plays his most preferred action.
Denote NoP (T) the number of pulls of the upstream player up to time 7 on the arm a. By definition of A up, we have that for any step t E [T' such that A, * an, max A (a)) ud (A.)
16

---

(a)() - (")(A,) > EE((A) (" - -o" A.. which leads
There are T - NTNNNP(T such steps,
(T, p Idwwa)
> E
max m (1)) (A2) acA
> (T - E[))
and we obtain
ETN >T T R (T, 11 A
Moreover, for any t E [7] such that A, = up and any Bt E A. u uuP (a + (aown(a." (aw)
(v.P(A:) + udown B.)) = ouP (ar") + ydown boww (v (a + ydoon (a BB)) A by definition, which leads to
N (T, I. IIdown) (TN"(
and we obtain
DR (T, 1P (ndown)
> TA sw R. (T, 1) AADP.
Since limy- too RM (T, //T we have limy-+ sw (T, Hop T //T s hence the result.
The proof of Theorem 2 is immediate consequence of Theorem 4.
Lemma 1. Recall that p. =..wwwn is the downstream player's optimal reward defined as solution of (10). We have p = maxx,bbEA (aoeee(yowwwo (aoow((abb + v"P(a)} max,' (a))) as well as
(aopt, boot)= = (a"H, (a"","" (tn)) and +== + T"P(a" ) (dowu (aa",,"" (%) = (e ydowa(a, b)}, where uru is defined in Equation (1), Moreover, for any integer E N*, and policies IIDp, Ildown, we have that
DwS (T, (T, (Idown) RR (T, (I, Iddown) +
+ sadlow (T, 11PP IIdown).
Proof of Lemma Recall that (nndown is defined as downown AR (udown (a, b) T} such that a E argmax,' E (a")(a') + [a()r) and a = argmax, w'P (a). Note that we can write
(PP(
1 doonn = max be...,. max(supp.be..rrR. 1l (a T) (n,dow (a, - T)) maxsE. down (a. (o"P,b) bb)
where À = {(a,r) r): (a) + 3 max v (a') + (a))r which is the set of pairs (a. T)
x E4 such that the constraint binds. However, we also have by definition that onH (a. + 0 >
max (a') + 1,,7 (a') and hence, (a"P, ,0) E Á. Therefore, since gdown (aw up b) > 0 for
any E A. we can write
I down
{u (ydwn (a, (c,b)-71
sup (a,T)EA,bEd
First note that if (a, A, then for any a' E A, E E R+, (a) + D (PP(a') + 1a(a")r, which gives
DPP > (1a(a') 1)T.
However, either = a' and hence (a) (a') = 0, either + a' and hence 1a(a') = 0. Therefore, we have that
(P) (a) n (a)) > -
which implies by definition of the optimal incentives that > u (a') (a) for any a' e A, and hence T. < T for any (a, E Å.
In addition, (a, T E À by definition. Consequently, # down
{u down (a, b) -.] max { down (a,b) max(v + (a)) a.EEA
0.
d'Ed
17

---

hence the first part of the result. Since u=' is defined as pt' = maX.Ed (a), we have that
1 pr.down
+ p=
max (odow (a, b) max (u (a))) + (a)((a) + max a.bEA
d'EA
aed
max (odown (a, + (a) a.bEA
(a*((""))))))) + udown(a aa baw)
Now summing Ripow and Rip as defined in (9) and (11), obtain
P (T, P [Idow)) + +RP Rndoon (T. (T.II . I!dow))
E
max (0 1a. (a)T(1)) (v"P(A)) La (A))T(1)
aEA
T max {u (udown 0.
max a'EA
max +
E
down (Ac, Bi) - 1s, (A)
r
T
> T max (1 (a)) -
v (At) + 13, (At)T(t)
- E
down (A,, B,) 1a. (A))T((t
aEA
1=1
TT max {u down (a, + (a)} T max abbE
=T max (a) ydoow (a, b)) - E Σ a.bE,4?
uP (At) + goow Bi)
= (T,1" Iddww)..
hence the result.
For a downstream player's policy Idwow, we define Ryp as the upstream player's regret without expectation, following
Re ((s 1, L...., s t), 11p 11 (nown)=
max (P)(a) + 1a, (a) (v*)(())))((AA)) 1=s+1
Σ
(Ar)(Ai) + 1a (Ai)T(1))
where (ā,, (())) are the incentives output by IIdown and (At)te( are the output of IIFP. Recall the assumption that satisfied by typical no-regret bandit algorithms.
the upstream player's regret for policy Thp We show here that it is
H2. There exist C, 0, K E [0, 1) such that for any 8, 1. E (T) with s + & T, any [Ta)aE[K] RRK and any policy IIdown that offers almost surely a transfer (āt, T()) = (āz, Tai) for any {s 1..... s + t). the batched regret of the upstream player following 11u0 satisfies. with probability at least 1 - 1-
stt
Σ 1=+11
max(v"" (a)((a) + 1a, (a)Ta,) (U"P(AI) 1a, (Ai)Ta)) < Ct.. aEd
We present the upstream player's UCB subroutine.
Proposition 2. Let s,t [T] such that + & T. Suppose that there exists family (Ta)aE of constant incentives associated with each arm a E A such that we have in Algorithm 3: (āi, (()):(()))+(((((......)))))
output of Idoon. Suppose that the dis- tributions Ta are 1-sub-Gaussian Then with probability least 1 T the regret of the version of UCB given in Algorithm 3 run by the upstream player satisfies
(01, Tai (sst.tt...).4))
Ap (fs + +l.... t), UCB, II [nwown &
Note that the major difference between this assumption and the regret bounds that we generally consider in multi-armed bandit problems is that consider the regret without expectation here.
18

---

Algorithm 3 Upstream player's UCB
1: Input: Set of arms K, horizon T.
2: Initialize: For any
[ set Po. 0, Ta =0. 0.
3: for 1 & t & K: do
4: Pull arm A &
5: Update PA. = XA, (t), (t) =1
6: end for
7:
for t K + do
8:
Observe the incentive (ā,, t(t)).
9: Pull arm A, E argmax,e(K] Aa (t 1) + 2 Tall-I] 1ā, (a)
loR(A
10: Update (t) = TA. 1) + 1, PA. TA,(0) (TA, 1)RA, - (X
XA,
11:
end for
Proof of Proposition 2. The proof is adapted from the proof of Bubeck et al. [2012, Theorem 2.1].
Let s,t [T] such that s + & T. For any integer E {s + 1..... - t}. we write nı(a) Card {T' E [1] such that Av a} for the number of pulls of arm a and (I) for the empirical mean utility of the arm E A estimated on the batch {1,.... 1): (t)() = mr(a) E 1. (Axx) x Since the rewards the incentivized bandit instance are -sub-Gaussian, Hoeffding bound gives that for any 5 E (0, 1). E A. E {s + 1,..., tj. and any family of arms (ar ( such that Card (j: 03 = a} = k, we have that
IP (( (1) v "P (a)) > 2/lo((2/0)/ (Av (Ar))e()....t)) = (ar ((er))(((....ttt) < 8 Therefore, for any E (0, a A, (s +J, we have the following bound P ((a (a)) > 2/1og((/00/mm(a))
U
- (1Aa(1)-
> 2//og((/88/8)
k=1
(ord) st. C um-
U
(lAa( + vaP(a)) > 2 2/
(arr) s.. Cod(i mpma)=k
Σ (agr)e st. (l..if) up-u]-k
-) > 2 logg(//6)
A -==ai)((A, = o1)
T'8
and with an union bound, we obtain that
P(31e E [t),a A such that (1a()) nP (aP(()) > 2/1g(2/6)/m((())
< <TKK8,
Considering the probability of the opposite event, we have that
P fforr any 1 E [t].a (l) uP (a)) & 2 22 21-5,
(20)
where we rescaled 8/T2K.
For the remaining of the proof, we take 5 = - and define of = argmax (a) fo 1 (a)T).
We now assume that the event {for any {s + 1,..., 8 + 1),a a A, (. v (a) <
2 II (2T2 (/))/n(aa) holds. If at some step {s + l.....s + t), action A chosen in Algorithm 3, it means that
A. (1) 2 [og(tk(/)//mmAA) 1a, (Ar)aa, > Pap (1) + 2 log(tK/6)/nn(c// + 1a. (ai) (aj) Tay
19

---

with regards to the choice of actions in UCB based on the upper confidence bound. We now decompose the whole regret the batch (s + 1....,& 8 (20) ensures that with probability at least 1/T
1) defined as P ({s + 1, f), UCB, IIdown).
*++.
Ri ((+ I,....,&& & + 11 UCB, ml =
Σ
uh (ai) lā (af - (vu
+ 1a, (Ar)Ta,)
1=++1
Ba; (1) + 2 log(Kt/0)//n(()) - uu (Ai) + (,, 1a, (At)
1=st1
(1) (/(00)++2/g(gg/////////a (PP(AA)
(1) + 2o1oo((t/0)/mm(A) (1) - 2 (og((K//)//mm()))
1=$+1
s+t
< 4 MoVooKK///
Σ (1/m(Ai),
1=++1
and we have
++1
K s+1
Σ
VI/ni(AI)
Σ Σ
(1)/m(((
1=s+1
i=1 1=st1
K
K
Σ
Σ
1/v1 < Σ v (i) - no(1),
(21)
t=
j
where the last step holds because for any integers 8, t E No, we have that
Σ Vi=
Σ
#+t
1
de Σ E
E
dx
= -
+++ dr
2(v Vs).
I=s+1
1=s+1
1-1-1
1= s=1-1 V
x= VI
Using Cauchy-Setee Schwarz inequality we obtain from (21)
1/K Σ
VI/mi(A)) & 2,
1/K Σ
note(() (i) = 22/t/K,
1=st1
1=1
which gives Eest1 T/m((A)) 2VIK.
Finally plugging all the terms together, since d 1/T², we obtain that with probability at least 1 1- 1/72
Rpp ((s 1, 1,....... + f), UCB) Booo(KK9))/
Lemma 2. Assume H2 holds and consider some arm A such that we run the d-th batch of binary search on with d E {l...., . [log, T for any t E {ka,d + 1...., ka,d + T), we have (()))())
(a,Ta) with Ta qimdd (d) and T [T Recall that we defined in (18): To Card (1 (ka,d 1,...,,ia.,, Kiad T} such that A, * a). Let B (0,1) be such that 3 < <<(1-1 -K). Given that the event (DRUP (PRyp((kia.)) ((kin 1, ka...,kad T}, IIu II Idown) & CP*} holds,
we have that
HT < T Cff+t then - < + 1/T3.
IIT Cfa+B/a then + - 1/T9.
Consequently, with probability at least 27 as, if Cintsla < T < Cīm+3/a, then
| Tal 1/78.
20

---

Proof of Lemma 2. The whole proof is done conditionally on the event
p (tkia,d + L,...,,ia... + 1pp .1pp 1I & CT
hia,"
Note that it holds with probability least 1 - > - T-a since suppose that p satisfies H2.
Suppose that we have 2 Tá + 1/T By definition of the optimal incentives, we obtain, using by assumption Ta 2 To + 1/T8
(a)TT + 1 3 Ta + ("P(a) + 1/7
max v (a)) - v (a) + 2 + 1/T
d'EA
max (a') + 1/7
which ensures that a is the optimal arm for the upstream player during the batch {Ka,d .,...,,.. hin, T) that we consider. In that case, since a is the best arm, by definition of the upstream player's utility, the reward gap ([(uP(a) (a) To (v"P(A,) + (A)))Ta) for the upstream player at any step t (ho.d + -,...,,hia. Ka,d 7 is at least e (a) + Ta - maxa'EA ua (a'). and we obtain
cT > RR + l...., ka.d + }}, 11p u > TTaaTTa + v (a)
max(v"F(d)))).
d'EA
T by H2, a,d being the number steps for which a suboptimal arm has been chosen. Therefore, by definition of the optimal incentives, we obtain that
CT TT - Tx)) 3 T
T > T T-
which gives: Tx CT Therefore, if we take the contrapositive, obtain that during the CT.+t/a, then with probability at least T sequence {ka,d + 1,.... ko, T}. if T a.d
Ta < < 1/T9, or equivalently 7 > Ta 1/T
Now suppose that Ta ra 1/T9. By definition of the optimal incentives, obtain (a + (a) < -r + (a)
< max e uP (a') - - (a) u (a) 1/T
a'EA
max "PP (a') - 1/T
which ensures that a is suboptimal arm for the upstream player during this batch of time steps. Therefore, arm a which has a reward gap bigger than 1/T since max.'e ( (P) + la))) (a + Ta) 1/T and arm has been picked T - T* times. Consequently, we have that
c > R ((hin, 1, ,,...., had + î}. Tup ITdow)) 1,....,,,,44 1 a (max u (P((a) (Ta + (a)())) a'EA
>1/T#
T f f- 8/0
which gives T î CB Therefore, if take the contrapositive, we obtain that if a.d < T CB/a then with probability at least T- Ta Ta 1/T equivalently To < Ta + 1/T3.
For the second part of proof, suppose that: CFn+3/a T a.d Tu+Bia C/a-B/a
From the above result, we have that 7 < Ta + 1/T and T > Ta 1/T with probability at least 1 27-2--00 oc, Plugging these inequalities in the absolute value | Ta concludes the proof. O
Lemma Assume that we run Algorithm and consider some binary search batch iteration d E [log 2 run arm A. Then 0 < Ig(d) (mid(d) < Fa(d)= < 1.
21

---

Proof of Lemma 3. The proof proceeds by induction. Considering some action E A, we have for the initialisation before any binary search run: (0) (0) and therefore - (0)
IL (0), Ta (0)). We now consider that number d of binary search batches has been run on Suppose that we run an additional binary search batch on action a. We have
mid (d + [d( + (d) which gives --mid (d + 1) E (d),
(22)
2
After this iteration of binary search, either have Ta Fd(++1) (m+ (d+1)+1/T+ and In (d+1)
(d) (a + rauid (d) and I,(d + 1) T (d + 1) 1/T Therefore, still have
0 & I. (d + 1) & raidd (d + 1) & Fa(d+1 + 1) < 1, hence the result for any d [loga T by induction.
Lemma 4. Consider same E A and suppose that we have D N batches of binary search of length T Then, have that
(Pop(( 1, I,..., Riad + π), 1pp. I[down) & CtOO) dE(D)
> 31 D/Ta/
Proof of Lemma 4. First observe that for any batch d (1...., D} of binary search run on arm during steps (ka,d + 1,...,,.u Ka,d a + T3. we have by H2 that
P (RAp (Skop 1...., ka.d T}. IIp Iddoa)
C²*H < $1/T5
and applying union bound over the D batches, we have that
U dE|Di
(oun (tka,d + l....,,ko kadd d + TJ, 11 (ldown) > CI.
D
Σ
(5Ap +l....,...,.................... I....,,ia,,, d + F}, Nup .1p Iddwn) > CP
j=1
< D/T
which gives that
n
(DRUP (flia, + I,...,,,,,, ka,d + TJ, IIDp,,doww (Idown) & CT*2 > 11 D/T
dE(D)
hence the result.
Lemma 5. Suppose that the upstream player rans subroutine Hup satisfying H 2. Consider some tion a E A and the D-th binary search batch of length T run on arm a with D E {l,..., [log2 T 11. Then
(RRm (Dho,a + I,..., Kaa,d + P}, Tlup Iddow)) & C C (T (D),
dE(D]
and the probability of these events least [log2 T0T/ToC We also have that -I, < 1/2D + 2/T holds almost surely
Proof of Lemma 5. Suppose that the conditions of the lemma hold and consider some arm
We show by induction the number of binary search batches 1 that have been that Naeppi (DRU
1,..., Radd T}. ITu Idoon) & CT*) S {oz E (I.(D), If true, Lemma completes this first part of the proof.
The initialisation holds since I, (0) = 0, Ta (0) and = max "PP(d - (P) E [0, with probability 1 since max,'eA "P (a') E [0, 1] and (a) (a) [0, 1].
22

---

We suppose that the property is true for some integer D < [log2 T and that we have run one more binary search on arm We have
mid (D (D+1) +
2
mid (D + 1) being the incentive offered to the upstream player he chooses action a during the D-th batch { + 1.... D + T7. After this batch, if T < T CT*+B/a, BELGIC updates Ta
Ia (D) and Lemma ensures that I, I,(D 1)) < Th < (D. + 1) given ( ((ka,D44 + ,,..,, k4. + T]. p. Idowa) < CĀ*).
T (D + 1) Ta (D + 1) + 1//79 Ia (a
Thus the induction holds.
Otherwise, if T > CT BELGIC updates (D + 1) =a - (D + 1) 1/T Ta
1) (D(D) and Lemma ensures that Ia (D + 1) <² < Fa(D + 1) given ( (fka,
1, I,..., D4. + T3, 11p. ( < C. The induction still holds.
Consequently, we have that for any number D of binary search batches run on arm To E [I,(D), (D)] with probability 1 - D/T
For the second part of the proof, we define u/ = T. (D) (D) > 0 as the length of the interval containing Th with probability at least 1 DDD/TSS We have u(0) 1. Suppose that after D iterations
of binary search batches, the next batch of binary search ( + ,,...,k.. kDD++1 + T outputs
1 0,1 < Cf Then, the update of Algorithm 2 gives
uD-1 = Ta(D + ID (D+1) +
- [D + 1) 1/7 (D)
Ta(D)+ + +I( (D) + 1/7
2
Ta(D) ID)
+ 1/T
2
uup/2 1/T
On the other hand, if T
011+1 > CTu+B/a the update gives
4D-1 Fa(D + 1) Ia (D + 1)
= (D())) - (T.."dd (D + +1) - 1
Fa(D) - Fa(D) + (D) + 1/7
2
TD(D): (D) + 1/T3
2
=wp/2+ 11241/77 1/778
We that (uD)Dzo is an arithmetico- sequence defined by uD+1 up/2 + 1/T3 with initial term u0 = 1. Writing 1 1/2) 2/T we obtain that
(F((D) - (D) up 1/22 - -r
2/T + 2/7 < 1/2" 2/T3
for any D E (I, [log, T hence the result.
Lemma 6. Suppose that the upstream player runs a policy IIPP satisfying H2. Considering some action E A. we have that after the binary search batch D [log, T P(I,(D) < & (D) < II +/TP) > 1- DDDD/TO a
(oyp(ffaa (fkead + 1.... ".....ka. kadd Proof of Lemma 6. We suppose that the event Nae T=1 (RRP
T3,11pP IIdow)) & Cf*3 holds. Lemma 4 ensures that this event holds with probability at least 1 [lgg, 0 1T05. /
23

---

After D = [Blog T batches of binary search on arm we have by Lemma that
[Ta D) - II. < 1/2" + 2/T
< 1 1/2 loga T + 2/ 3/T
Lemma 5 guarantees that T2 E IT, (D):Ta with probability at least 1 - D /T and we obtain (D) < T < TD( < (D) + 3/T with the same probability.
Proposition 1. Under and H2, after the first phase of BELGIC which consists in K [og T steps of binary search grouped in [log, T batches per arm A, we have that
P( for any E A, - 4/77 CT(K- 1)/2
fa > 1 - K[oog /////as..
Proof of Proposition 1. We consider number of binary search batches D [lg T and we define the event G as G {for any E A. & & <T.(D) ID) + 3/T8) }. We have that
P(G) = = n Ia (
AeEA
1 P
< (D)
+ 3/Tu]/
AaE
3
Σ
(((aa(D) < (D( & (D) 3/TT83)
aEA
where the last inequality holds with an union bound. Lemma with D = [log, I have
ensures that we
P((I,(D)
(D) (1 D/Tas,
and since (Ard(AA= K, we obtain
(()) > 1 1 K [log T /
Since the estimated incentives are defined as i = Fa ([log, 1 + 1/T + CT(x-1)/2 1)/2 conclude
we can
P( for any a E A, - 4/T (T(x-1)/ 1)/2 $ :/ $ ta) > 1 - K k /
since whenever Ta ( (flogg 1) & T < (a 1) < T, (log, T + 1/T we also have by
definition: ta ([log, T - 4/T CT 1)/2 < Ia (llog, 1) < T < (,lo,, 1 E
Theorem 3. Assume that HI and H2 hold. Then BELGIC, run with a, B satisfying (13) and any bandit subroutine Bandit-Alg has an overall regret Rdowwn such that
Dalown (T, IIUP BELGIC) & 2(3 2C + 8 v) loga (T) (2T T(x+1)/2 [T 447
+ Roandet-Aig (T, (T
{Fa )aEa)
where, for ease of notation
min fo down (a, and a.E
{o down (a, b)}
max abEAAA
Proof of Theorem 3. Suppose that the conditions of Theorem are satisfied. By definition,
AK+1 + 1 E [T] is the step at which starts the run of the subroutine Bandit-Alg, since AK+1 K 1 log 17. All the binary searche batches have length T [] For any E A, (1..... ... [loga T& I), we define the event
Band (aann (flkfffa + 1,...,kor + T}. IT Idowny & C
as well as
Badd d n SA ([AK+] + 1...., TH < C(T - AKt1)"}
3
K dEll m]
24

---

and by H2 and Lemma 4, with an union bound, we have that
U Ba U(SEp((AACH + ,..................... ,T, p M & C(T Axti)
P(E) = 1-
aE[K]
dmellloo 11
> 1- E
P(B (P 17, & C(T Ak+1)*)
[E[K]
aclllog 191
> K log T -TT-)))
KTBlog - - T
and we now decompose
Rddown (T, (T, un E I(E)) (T, 11p [ldowa) + (o 11. (Idown)
(23)
where Adwon defined as
jadown (T, mpp. Iddow)) Tu" down
down (Ae, Bτ) (A))
By definition, 1 down > min AEAXA down (a, b) > and since Lemma allows to write μ downn
maxa,beAxA down (a, b) + v (u)(()) (a)) max (v"P(a')) (a')): we have that
down 1
and note that since for any a i, < 2 C7(x-1)/2 < 2 + C. Consequently, Ty < fodowa (T, Hup, Iddww)
< C + 2)T almost surely. Therefore
e 1 (T, II ITdown)
< (3+C+E-- - u) T 1 + TI-5). (24)
We consider the second term in (23). We decompose it between the steps of binary search {1...., K[T [[gg Th during which
the Binary Search Subroutine and the fol- lowing ones when we run Bandit-Alg which gives
E (E)) (T, Tlu p
Mdown)
(25)
K[T [log T
&
1(8)
# down (mdown/ (At, B:) - 11, (Ai)((()
(A)
+ IE 1(8)
p dowwn (ndown (Ar, Bi) - 1a, (Ac))(1))
t= [ Bog, 19141
Similarly to (24), use the bound μ dlown to bound (A), which gives
AK+z
([)(E)
1(
1 (v
C) < (1 + log, T)(3+C+++
(26)
25

---

After the binary search, at each step t E {Ak+1 + +1....,Ty T) Bandit-All Alg recommends (ā,, B.) E
A x A following (15) and BELGIC offers an incentive (ū,, fa.) with ia = ((ogg 1) )) 1/70
CT(x-1)/2
Lemma ensures that & C {Ta [L (Boogg 1), Fa ([log2 1d] for any E A) Mo ({A++++ 1,..., 7) mpP) & C(T A--1 }r.. Therefore, if & holds, for any A, we have that
ouP (a) + fa = + CT(x-1)/2
(aP(a) + C7(x-1)/2
= [a) + max 8. (a") (a)(a) + CT(K-1)/2
e"EA
and therefore, for any a' A such that a' + have that
(a) + (a') + CT(x-1)/2
(27)
This shows that at any steps E {Ak+1 I..... T after the binary search, we have on the event
that
ã arggaa " 1a, (a')aat).
(28)
and the reward gap at step for any + ä defined as
max (a') 1a, (a') fo.) (v (a) + 1a, - + +
(a)
(29)
Following (27), the reward gap from (29) satisfies
deA max(o")(a') (a') 1a, (a') (a) + (a)fa)) CT(x-1)/2
We now define sets
I (t E [M
llog T + ., such that ā; =Ar) JT = (t [K 7 logg T + 1,..., such that ā, + Ar)
which satisfy Ir Jr [K[T [log, T + 1.....,y T} almost surely. As shown in (28), Ir corresponds to all the steps during which the upstream player picked the best arm and for any L E TT
v "P (At) + La. (t))=(t) > max(u"P( + 1a, (a)r(t))
aEA
while by (29), for any t Jr, have that
max
max(f"P(a)) + 12, (a)faj) (c"P(Ai) (Ai)fa)))))) > 11/2 a
(30)
H2 ensures that if & holds, then A ([Ax+1 +1. 1,..., .T. H BELGIC) & CT*, and this condition together with (30) gives that
Card(Jr) CT(c-1)/2 & CRP + +1,... T), T3.1 BELGIC) & CT
26

---

and consequently Card(Jr) & 1(/+1)/2 We now bound (B) as follows
(BB) - E 1(8)
Σ
1 *:owa
(udowa (Ae, BB) - Fai)
E
1(E)
Σ
max fodown (a, [/o (uddww (āe: BB) Fax)
a.EEAA
E
1(8)
E
down (odown( (Ac, Bi) Fia))
LEJT
<3+0+0-0
< 18 1(8) Σ
max (ddown (a, Fa -uudow (āz, Bi) - -ta)} + maxifa -oan--ao [ac
a.EEAA
a'Ed
EEI
(3
+ C - [)
E 1(8) Σ tEl aEAEA
(odown (a, -Fa} - -oodowm (āz. Bi) F(x))
a'EAA E (EE) (El
Σ
max - T (3 + C+ v- 2) 7(x+1)/2
< Rgandit-ALg
(Crrd "Bandit-Aug(Card([
(Fatae)) + ((rd max -
deA
C + (x+1//22
where the first step holds by Lemma 1. Using Lemma 5, as well as the definition of E, we obtain
E (E) max r
E [(E)Card (E)/TTT CT((-11/23)
d'EA
(4 + +CT(x-1)22
+
which finally gives
(E) < Reandit-Aig(TT (Fa)nee)))) 4 (3 2C + - (11+)//2
(31)
and plugging together (26) and (31) in the decomposition (25) gives the following bound
E (8))) Srdoow (T, TT BELGIC))
Rlandit-Aig (Fa)oeA) + 47 + +(3 2C + -- u) ((1+))/2
+
log, T),
and summing the bounds on the events E and E finally gives
mmdooe (T. 11.P; BELGIC) & Rraandit-ig((; (FalaeA) 17 + (3 + 20
20 +0 (05-g)((10 7(1xx//2
( log, T)
+ 03+C-0- log, 1 T-1
R (T, - 47
2C + T -T + T2-5)
(1+x)/22
+ +3 - log, ( -
12 (1 log, () + TT
+ Rigndit- (T,
+ 1
2(3 + 2C + 8 - log, (
127 + 12/21//2 + (Te] + 1-
+ Riganit- Aagiit--iiggg (T, f
aEA)
27

---

Corollary 1. Assume that the upstream player's distribution (Na)aEA is such that H holds. In addition, suppose that the distributions (Na)aE and (Va.)a.beAAA. are Saub-Gaussian and that the upstream player plays p Algorithm 3 (a slight modification of UCB to take into account the incentives). Then the downstream player's s regret when she runs BELGIC with parameters 3/4 and B 1/4 (which satisfy (13)) and subroutine Bandit Ang UCB satisfies the following upper bound
Ro (T, UCB, BELGIC) & (10+4K+33) + K 2ogg (KT3) + ū - 2)) logg (T)++
+ +3K² ()- -2)
Proof of Corollary 1. First note that I1. = Algorithm 3 satisfies H2 with constants a 1/2,
< 2, C 8 log (KT)), following Proposition 2. Note that B/a 1/3 < 1/2 1
therefore Equation (13) is satisfied. Plugging these terms in the bound from Theorem with
3/4, 3 1/4 gives
andowa (T, UCB, BELGIC) < 2(3 16V K ( + 8 - 2) logg (T) + 78/4 + (73/41))
+ 44 + 8V R2 (T) T1/2 3バ 2 (8 -2 2)
where we the bound for Agandit-Aig (T, V, f A with Bandit- All UCB any bandit instance with K2 arms, 1-subgaussian rewards and reward gaps of most max,,bE.Ax.. ydown (a, b) mina, bx A gdown (a, b) u. following [Lattimore and Szepesvári, 2020, Theorem 7.2]. There- fore, we have that
Dndonn (T, UCB, BELGIC)
< (6+32 K loga (KT3) - 1)) log, (2 273/44
+ +4T + 3K - 8K log, 1/
< (10+ (2 + 5 2) logg (T) 2T
+ +3 (8
8K 8K Log,
which finally gives
Dndown (T, UCB, BELGIC) < (10 + 4K + 3 K log, (K73) + 0 - m) log (3) (T) +3K2 (o- 2)
hence the result.
'Note that it is K and not / K here, since the action space is of cardinality 2² for the downstream player.
28

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract mostly presents the issue that we tackle the paper, namely presenting online version of the Coase theorem. This contribution is the most important part of our paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
29

---

Our work presents model to explore an online version of theory from economics. Thereby, it implicitly has limitations due the fact that choice was made in the model.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiscless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Our work presents lot of theorems supported by assumptions (see H Theorems 2 and 3.... All of Appendix C is here provide theoretical support to these results.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
30

---

Since our work is mostly a theoretic contribution, we do not present experi- ments. Therefore, our paper is not concerned by this issue.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Since our work is mostly theoretic contribution, we do not present exper- iments. Therefore, our paper is not concerned by this issue (same answer as for item 5).
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Souidees/CodeSuuiissiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.co./ wwtppcppppccccoc.ecc..cc.....clc http://ggiidee/eeeeuuuiiiiiaeeee Sooodeeubmissiooool1111
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
31

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Since our work is mostly theoretic contribution, we do not present exper- iments. Therefore, our paper is not concerned by this issue (same answer as item 5).
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Since our work is mostly theoretic contribution, we do not present exper- iments. Therefore, our paper is not concerned by this issue (same answer as for item 5).
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
32

---

Answer: [NA]
Since our work is mostly a theoretic contribution, we do not present exper- iments. Therefore, our paper is not concerned by this issue (same answer as for item 5).
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https //nuurnursp...e htapp.cccpppppe httpppblccccccccccctteeeeeeeeeee htte//ettiiiieeeeeeeeeeeeeeeeeee
Answer: [Yes]
Justification: As explained in the Related Works, an issue with externalities the harm caused to all the parties involved in the considered setting. Here, we try provide a setup so the players can negociate and achieve social welfare optimal equilibrium. Therefore, we are confident in the fact that we follow the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We consider an issue arising in several real-world situations and provide an algorithmic solution to it. We realize that this theoretical contribution still needs some work to be implemented but we hope that it will contribute to positive social impacts in the future.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
33

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks. mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: Our work is thcoretical contribution. Thereby, it does not propose release data or any kind of trained model. We mix learning and theories from economics, which does not involve yet risks for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do any assets requiring such conditions here.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, sepperswithhode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do present such kind of new assets.
Guidelines:
34

---

The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: We do not incorporate any experiment involving human subjects. Therefore, we concerned by this item.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not incorporate any experiment involving human subjects, hence our answer.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
35


Reviews:
[{"review_id": "HjxGywj05M", "reviewer": "Reviewer_aRFf", "summary": "The paper presents a two-player sequential game with bandit feedback where one player's actions create externalities that affect the other player's outcomes. In this model, the utility of only one player (the downstream player) is impacted by the collective actions of both the upstream and downstream players. They consider two scenarios: one where players act independently to maximize individual utility, and another where players can interact via transfers.\n\nIn the first scenario (without transfers), the authors show that individual utility maximization can lead to suboptimal social welfare in some instances. In the second scenario, where the downstream player can choose a transfer, they demonstrate that social welfare can reach its optimum. They propose an algorithm for the downstream player that achieves this outcome, provided the upstream player follows any no-regret policy. This effectively presents an online version of the Coase theorem, establishing that even with imperfect information, the two-player sequential game converges to the global optimum outcome when transfers are allowed.", "questions": "1. It is not clear whether the regret incurred by the downstream player is optimal. Even if the upstream player is assumed to follow UCB, it's not evident whether a regret scaling as $\\sqrt{T}$ policy is achievable for the downstream player as well. \n2. It is stated (on lines 111-112) that the assumption that the rewards are bounded is \"without loss of generality\" (WLOG). Can you please explain why? Would this work even in the case of other standard reward distributions in bandit literature, such as sub-Gaussian rewards?\n3. 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. Is there a particular reason for assuming such a transfer function? Can we work with more general transfer functions where the downstream player can choose to make transfers on multiple actions? How would this affect the regret of the downstream player?", "limitations": "This paper does not have any negative social impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The algorithm does not assume a specific policy for the upstream player and achieves sublinear regret for any no-regret upstream policy (with regret scaling as $T^\\kappa$).\n2. Lemma 1 provides a clean problem formulation, showing that bounds on regret in individual utility (with transfers) lead to a bound on the social welfare regret.\n3. For the specific instance where the upstream player follows the Upper Confidence Bound (UCB) policy (or any other algorithm with  $\\sqrt{T}$ regret) the proposed algorithm achieves regret scaling as  $T^\\frac{3}{4}$.", "weaknesses": "Please see the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> It is not clear whether the regret incurred by the downstream player is optimal.\n\nSee our general answer on optimality of the regret bound for BELGIC for more details.\nTo 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.\n\n> It is stated (on lines 111-112) that the assumption that the rewards are bounded is \"without loss of generality\"\n\nNote 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. \nH1 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.\n\n> 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\n\nMore 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BliBg5tt8a", "reviewer": "Reviewer_rbRK", "summary": "The paper explores the field of mitigating externalities in economic interactions by applying the Coase Theorem with hindsight rationality. The Coase Theorem, a fundamental concept in economics, suggests that in the presence of externalities, property rights, and bargaining strategies can be utilized to achieve an optimal outcome for all parties involved. However, traditional applications of the Coase Theorem assume that players have perfect knowledge of the game, which may not hold true in real-world scenarios.\n\nIn this paper, the authors introduce the concept of hindsight rationality, where players learn from past interactions to improve their decision-making processes. By incorporating hindsight rationality into the Coase Theorem framework, the paper aims to provide a mechanism through which players can adapt their strategies over time to maximize social welfare, even in the presence of uncertainty. The theoretical foundation of the paper is built upon a series of theorems supported by assumptions and proofs. \n\nOverall, the paper offers a novel perspective on addressing externalities in economic settings by integrating hindsight rationality into the Coase Theorem framework. Through a rigorous theoretical analysis, ethical considerations, and a discussion of limitations, the paper contributes to the ongoing discourse on optimizing social welfare in the presence of externalities.", "questions": "Please clarify the points in the Weaknesses section.", "limitations": "Yes, the limitations of the proposed method are discussed in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. One of the main strengths of the paper is its solid theoretical foundation. The authors create a clear framework based on well-known economic principles, like the Coase Theorem, and expand it by adding the idea of hindsight rationality. The thorough theoretical analysis, backed by detailed proofs and assumptions, strengthens the credibility and robustness of the proposed approach.\n\nS2. By introducing the concept of hindsight rationality within the context of mitigating externalities, the paper offers a novel perspective on addressing economic inefficiencies.", "weaknesses": "W1. One significant weakness of the paper is the lack of empirical validation or experimental results to back up the proposed theoretical framework. Although the theoretical analysis is good, empirical evidence would improve the practical applicability and real-world relevance of the research findings.\n\nW2. It would have been insightful to see a comprehensive discussion on the potential challenges and complexities associated with implementing the proposed approach in practical economic settings. Addressing implementation hurdles could provide valuable insights for policymakers and practitioners.\n\nW3. The setting (extension of Coase theorem in a two-player bandit setting where the actions of one of the players affect the other player) considered in the paper is narrow and limited. The results are also exemplified for a simple setting of two firms, an upward and a downward. Do the observations apply to potentially broader settings? \n\nW4. The mathematical notations provided in the paper sometimes become too difficult to follow and correlate with the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> W1. One significant weakness of the paper is the lack of empirical validation or experimental results to back up the proposed theoretical framework. \n\nWe 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. \nAs 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.\n\n> W2. Addressing implementation hurdles could provide valuable insights for policymakers and practitioners.\n\nAddressing 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).\n\nAs 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.\n\n\n> W3. Do the observations apply to potentially broader settings?\n\nPlease see our general answer on the use of our work for more general settings.\nTo 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.\n\n> W4. The mathematical notations provided in the paper sometimes become too difficult to follow and correlate with the text.\n\nWe 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.\n\nIf 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.\n\n--------\n\nWe hope that we answered all your different concerns. If you still have any, we would be happy to answer any further questions.\n\n---------\n**References**\n\nAbildtrup, 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QRcORGpERQ", "reviewer": "Reviewer_UVPQ", "summary": "This work considers a two player game with externalities imposed from one agent (“upstream”) to the other (“downstream”) agent. Equilibrium in the absence of taxation or payments between players would result in heavy efficiency loss due to the externalities.\n\nThe Coase theorem tells us that in these situations we should expect to see payments from the downstream agent to the upstream agent in order to restore the socially optimal outcome.\n\nThis work formulates this scenario as a multi-armed bandit problem, in which the payment term forms a part of the players payoffs and options. Namely, the downstream agent can put a conditional payment on the arms played by the upstream bandit. In this situation, the paper asks whether or not normal bandit learning algorithms can learn the optimal outcome.\n\nThe paper puts forwards an assumption that must be satisfied on the upstream agents learning behavior, which is satisfied for many common bandit learning algorithms. A translation is given for the downstream agent to go from the raw bandit problem to a transformed bandit problem. With these, sublinear regret is realized relative to the socially optimal outcome.", "questions": "How broad do you expect the BELGIC routine to be applicable? In a general $M$ agent situation with less obvious structure on the externalities would you expect optimal transfers to still be learned efficiently?", "limitations": "Yes the authors have adequately addressed limitations of their work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The work takes a well-known economic theory and asks whether a given type of ML can recover the expected phenomenon without knowing the specific externality a prior. Rather than showing an exact algorithm for recovering it, mappings are done so that any suitable bandit learning algorithm can successfully learn the results. This is a nice addition over prior work, and helps in suggesting that this is something with broad learnability. In the process, it is interesting to see the manner in which the externality needs to make it into the payoffs and how that space needs to be structured.\n\nOverall the paper is well written and has good fit at NeurIPS. Relative to prior work, it is able to show that as long as the upstream agent is using a suitable approach, any bandit learning algorithm will work. This is a much stronger guarantee for the downstream agent as they are less dependent on exactly what the upstream agent is doing.", "weaknesses": "The paper and situation is quite interesting, but is one specific (classic) example scenario so applicability is good because it is a classic example, but still limited. A natural followin question is how broad do we expect these situations to go - can we recover general externalities in multi agent situations?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> It will be nice to see a discussion about possible notions of optimality of mechanisms that incentivize participation in this context.\n\nAs 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.\n\nYet, it might be possible that stronger assumptions on the upstream player strategy (that remain realistic) could lead to better regret bounds in the end.\n\n> How broad do you expect the BELGIC routine to be applicable?\n\nWe 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.\nOur 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their detailed and insightful feedback. All their comments will be taken into account in the revised version of our work. We answer individually to each reviewer's concern. Besides, a couple points were raised by multiple authors: we answer these points below.

## About the optimality of the regret bound for BELGIC

This is a very interesting question. 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}$ times, while still having a regret smaller than $T^{\kappa}$. This would then imply a total regret of order $\frac{T^{\kappa}}{\varepsilon}+T\varepsilon$ to the downstream player, 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, better bounds might be reachable under stronger assumptions on the upstream regret (e.g., instance dependent bounds), which is open for future work.

## Can our algorithm be used for more general problems?

Naturally, 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 our work to more than two agents is indeed a very interesting direction that we plan pursuing in future works. A potential extension of the setting could be for instance to consider a chain of agents, whose actions all influence the following agent in the chain. 
A stronger set of assumptions would be needed in that case, as we would need to control the behaviors of all agents. We believe that our work can pave the way towards designing satisfying learning strategies in such games and it is a promising direction for future work.

Meta-review: There was a consensus that this work tackles an interesting problem and provides significant results. All questions raised by the reviewers were addressed by the authors, and no further issues were raised during the discussion period. This is an easy accept (spotlight).
Decision: Accept (spotlight)