Envy-free Policy Teaching to Multiple Agents
Authors: Jiarui Gan
R Majumdar
Adish Singla
Goran Radanovic
Venue: NeurIPS 2022 Accept (2022)
Keywords: policy teaching
reward design
fairness
envy-freeness
price of fairness

Abstract: We study envy-free policy teaching. A number of agents independently explore a common Markov decision process (MDP), but each with their own reward function and discounting rate. A teacher wants to teach a target policy to this diverse group of agents, by means of modifying the agents' reward functions: providing additional bonuses to certain actions, or penalizing them. When personalized reward modification programs are used, an important question is how to design the programs so that the agents think they are treated fairly. We adopt the notion of envy-freeness (EF) from the literature on fair division to formalize this problem and investigate several fundamental questions about the existence of EF solutions in our setting, the computation of cost-minimizing solutions, as well as the price of fairness (PoF), which measures the increase of cost due to the consideration of fairness. We show that 1) an EF solution may not exist if penalties are not allowed in the modifications, but otherwise always exists. 2) Computing a cost-minimizing EF solution can be formulated as convex optimization and hence solved efficiently. 3) The PoF increases but at most quadratically with the geometric sum of the discount factor, and at most linearly with the size of the MDP and the number of agents involved; we present tight asymptotic bounds on the PoF. These results indicate that fairness can be incorporated in multi-agent teaching without significant computational or PoF burdens.

Envy-free Policy Teaching to Multiple Agents
Jiarui Gan
Rupak Majumdar MPI-SWS rupak maankmmii-sssoor
University of Oxford jiarui. gandcs. ox ac.uk
Goran Radanovic
Adish Singla
MPI-SWS
MPI-SWS
gradanovic@mmissssoorr
adish@mpi-sws.org
Abstract
We study envy-free policy teaching. A number of agents independently explore a common Markov decision process (MDP), but each with their own reward function and discounting rate. teacher wants to teach a target policy to this diverse group of agents, by means of modifying the agents' reward functions: providing additional bonuses to certain actions, or penalizing them. When personalized reward modification programs are used, important question how to design the programs so that the agents think they are treated fairly. We adopt the notion of envy-freeness (EF) from the literature on fair division formalize this problem and investigate several fundamental questions about the existence of EF solutions in our setting, the computation of cost-minimizing solutions, as well as the price of fairesss (PoF), which measures the increase of cost due to the consideration of fairness. We show that I) an EF solution may not exist penalties are not allowed in the modifications, but otherwise always exists. 2) Computing cost-minimizing EF solution can be formulated as convex optimization and hence solved efficiently. 3) The PoF increases but at most quadratically with the geometric sum of the discount factor, and at most linearly with the size of the MDP and the number of agents involved; present tight asymptotic bounds on the PoF. These results indicate that fairness can be incorporated in multi-agent teaching without significant computational or PoF burdens.
Introduction
Incentive design is an important approach to influencing rational agents' behavior. In reinforcement learning (RL), the incentive of agent is expressed through their reward function M. One can thus teach desired policy to an agent by modifying their reward function, in a way that makes the target policy optimal with respect to the modified rewards. In safe RL, for example, penalties can be imposed on dangerous actions to prevent an agent from executing them [2 In many cases, personalized teaching programs are useful against heterogeneous agents, who might have very different innate reward functions or apply different discounting rate. As result, the agents may find them rewarded/penalized differently for performing the same action in the same situation (see Figure D. Concerns of fairness arise, and we ask the question of how to design fair personalized teaching programs so that the agents think that they are treated fairly.
To be more concrete, consider a language teaching setting modeled as an MDP. Each state of the MDP represents the overall skill of student (agent) and is encoded as the student's performance on different components such as listening, reading, speaking, and writing. Actions available to the students are defined by the levels of effort they put into the components, and it is desired that they always put more effort into the components that they are currently weaker at, which is also the target
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Sm
0
81
B2
8=
Figure 1: To teach agents to choose the action leading to state an additional reward is necessary for an agent whose innate reward function the one on the left, whereas an agent with the reward function on the right already finds this target policy optimal, so no additional reward is needed. When these two agents are being taught together, the agent on the right would think they are treated unfairly as they get no bonus for following the target policy while the agent on the left gets bonus 1.
policy the teacher aims to teach. The students' innate reward functions are defined by their interests, which vary across the classroom: some students may be more interested in reading, some enjoy speaking, and some are just not fan of any of them. The teacher can assign additional credits to incentivize the students to follow the target policy (e.g.. credits that can be used to exchange snacks, or that will be considered in the final evaluation). Similar interactions may also happen with other types of training programs in various domains, such as sports training. They can happen both in physical classrooms and virtual classrooms such as language educational apps (e.g., Duolingo uses a credit system where credits can be used to unlock next learning levels). Beyond classroom teaching, examples can also be found in principal-agent settings. For example, a company wants to outsource task to different contractors. Rewards or penalties are stipulated through customized contracts to ensure that contractors comply with a desired policy when performing the task. Mcanwhile, fairness is important as a beneficial factor for long-tery term partnerships.
1.1 Approach and Results
Our first step is to understand what it means to be fair in the setting of policy teaching. Indeed, in world with growing awareness of equality and transparency, fairness has been discussed and evaluated in a wide range of domains. Various concepts and notions of fairness have been proposed and used (. We borrow the well-studied fairness notion of envy-freeness (EF) from the literature on fair division. is a notion that has been used for settling disputes over property divisions or deciding how to split an apartment rent [c.g.. 4 [.. Applying EF to policy teaching. we aim to find set of personalized teaching programs, such that no agent would prefer to switch the program they receive with another agent. At the same time, as a basic requirement of policy teaching, each program should also incentivize the corresponding agent to use the target policy. Besides the basic version of EF, we also consider two stronger variants: one allows an agent further deviate from the target policy when evaluating how much they would have got had they been offered another agent's 's teaching program; the other simply requires all teaching programs to be identical, which completely fair in a sense.
We investigate several fundamental questions about EF policy teaching.
Existence of an EF Solution. The first question about the existence of an EF solution under the three EF notions of interest. We show that an EF solution always exists and one can be obtained simply by penalizing undesired actions by a sufficiently large value. Nevertheless, the reverse does not hold true: one cannot hope to find an EF solution only by rewarding actions desired by the target policy. We demonstrate instances that do not admit any EF solution when penalties are not allowed even with the weakest EF notion; we also prove that this non-existence issue is resolved if the agents have the same discount factor.
Cost Minimization. Since reward modification can be very costly, we are also interested in finding out an EF solution with the least cost. We consider the norm of the modification and show that computing a cost-minimizing EF solution can formulated as convex optimization and can hence be solved efficiently.
Price of Fairness. Finally, we analyze the price of fairness (PoF), a quantity that measures the (multiplicative) increase of the cost due to consideration of fairness and in similar spirit of the price of anarchy (PoA) in game theory [ We present tight asymptotic bounds the PoF. The

---

PoF increases at most quadratically with the geometric sum of the discount factor and linearly with the size of the MDP in general, while it may also grow linearly with the number of agents involved depending on the specific EF notion considered.
In summary, our results indicate that the consideration of fairness, in addition to the original goal of policy teaching, may result in non-existence of workable solutions but the existence is guaranteed in a fairly wide range of important settings. It does not appear to increase the computational complexity of policy teaching, while the additional cost it incurs grows moderately with the size of the problem. The results indicate that fairness can be incorporated in multi-agent teaching without significant computational or PoF burdens.
1.2 Related Work
Our work lies at the intersection of policy teaching and envy-free resource allocation.
Policy Teaching Without the fairness constraints, our model can be seen as a policy teaching problem for each individual agent in the model. A number of studies have looked at this problem [ The problem can be computationally harder though when the target is to hit one in a set of policies rather than a single target g When the teacher is targeting a malicious policy, policy teaching can also be interpreted as reward poisoning [10
[3 [4]. From a technical point of view, these two problems are almost identical and can be solved by using the same techniques. However, conceptually, it is less likely that one would take fairness into consideration when designing a poisoning attack. More broadly, policy teaching can be seen as a sub-field of reward design, a broader area that studies how to influence agents' behaviors thought tweaking the reward function. The objectives of these studies are not limited to inducing a target policy. A notable example is reward shaping [15] 16 [7]. which aims to accelerate an agent's 's learning process through reward design. Indeed, while our focus on policy teaching, the same question of how to design rewards fairly can be asked with other objectives well. These can be potential directions for future work.
Fair Division The study of fair division dates back to the early work of Foley 18 and the formal concept of envy-freeness appeared even earlier [19] Research on fair division has since evolved into
a large body of work, with focuses on allocation of divisible or indivisible items 200 21 2
[3] J Our
work is in particular related to fair allocation of indivisible goods with subsidies 24 w Where external
benefits are provided to change the agents' original incentives. The difference is that no items are allocated in model and our goal in addition to achieving fairness is to teach the target policy.
We note that there are also other studies on machine teaching settings involving multiple agents or multiple teachers 255 26 2 though with very different models from ours. From a mechanism design perspective, our model can also be viewed as one version of the contract design problem (28. where a principal offers an agent a contract for performing a target policy, but might be uncertain about the agent's 's type (i.c., the original reward function). Our EF solutions correspond exactly to truthful mechanisms that elicit the agent's true type.
2 Preliminaries
There are n agents 1, 1,..., n. Let [n] = .RI............. Each agent E [n]] faces an MDP M, = (S. A, R, P, z, 7t)- The MDPs have the same state space S, action space A, transition function P : S x A x S + Jo. 1]. and initial state distribution z. Moreover, there is a reward function R, : x A IR and discount factor 7/ for each agent i [n]. Whenever agent takes action in E S with probability P(s, a, 8²). We consider the setting where each agent is concerned with the (expected) cumulative reward, i.e., the discounted sum of rewards with respect to the factor ni obtained over an infinite horizon. More specifically, the cumulative reward of agent i for executing policy S A(A) is
state s, a reward (2 a) is generated for this agent; meanwhile the state transitions to
00
E Σ
(n)' (st, at) 30 ~ 2, π
P
where the expectation taken over the trajectory (st, ax 22 resulting from an initial state so sampled from and the agent executing π subsequently. Each agent aims to find optimal policy, which
3

---

maximizes p and this can usually be handled by standard planning and reinforcement learning algorithms.
Throughout the paper, we consider the setting where the agents operate independently separate environments. Their payoffs are only determined by their policies.
2.1 Single-agent Policy Teaching
Consider the situation where we want an agent to execute target policy x², but the agent finds a different policy x' optimal for M, To incentivize the agent the reward function by providing additional rewards (positive or negative). We follow the literature and consider only deterministic target policies. (Indeed, in general, one cannot hope to incentivize an agent to use a non-deterministic policy only by tweaking the reward function.)
n², typical way is to modify the
Specifically, the teacher chooses reward adjustment function 8; S x A - IR, or adjustment for short, whereby an additional reward (s a) is provided whenever the agent takes an action a E A in a state E S. Effeetively, the adjustment changes the agent's reward function to (s(s, = R. + ós(s, The agent then optimizes their policy with respect to R. and will be incentivized use x² if it offers the maximum payoff (cumulative reward) with respect to RG- We view each agent's payoff for policy π as a function of 6; as follows:
P (6,) E
Σ (ra)* Rs(s,, 80 ~ 2, π
Moreover, define the V-function and Q-function of æ given adjustment 8; as:
(s 6.) = Q7 xxs) 8.).
and (s, 6.) (s, + P(,,a) Vi" (s' [
The V-function captures the expected cumulative reward by starting from and following x. The Q- D-function captures the expected cumulative reward by starting from s, taking action the first step, and following π subsequently. We have
P (6,) V (z 6,) E VTT (6)-
Using these two functions, the Bellman equation further characterizes the optimal policy in the MDP: policy optimal if and only the following Bellman optimality equation holds: QT (s, (()) 5,) Q (s, a 6;) for all E S and E A.
Incentive Constraints Hence, the goal of policy teaching is to make the target policy x solution to the Bellman optimality equation. Since the agent may find multiple policies optimal, robustness guarantee > 0 imposed to strictly incentivize the agent use π and this results the following incentive constraints:
O (s, (s) 6.) 2 QT (s.a 52) +e for all a + (s).
The constraints ensure the optimality of .* even if there is a small error in the Q-values.
Cost Measures In addition incentivizing œ² the teacher also wants to find the most cost-efficient way of teaching. We consider the norm of the adjustment, which means the following cost measure:
1/2
cost
|| =
Σ
())(s,
eES.aEA
3 Teaching Multiple Agents and EFness
In the multi-agent setting, the teacher provides an adjustment to every agent [r]]. We call collection of adjustments (d:)ae(n) adjusiment scheme. A basic approach for this setting is to deal with each agent separately, by solving a single-agent teaching problem for each agent. The solution obtained via this approach provides personalized adjustments to the agents and it minimizes the

---

teacher's total cost. Nevertheless, it might not be fair as we showed in the example of Figure I To be more specific, we define three fairness notions, each being stronger than the previous one. We start with the following weak EF notion.
Definition 3.1 (Weak envy-freeness (WEF)). An adjustment scheme (ō:) is weakly envy-free if it holds for all i E [r|] that
pF (6) P (6)) for all j E [n].
In other words, no agent i would prefer the adjustment for another agent j to their own.
The above notion only compares the agents' benefits under n². When 5, incentivizes agent to use n², the left side of ( is also exactly the highest possible benefit can obtain given adjustment 6; But this is not true for the adjustment on the right side: x need not be optimal for agent with respect to R2 + 6y; higher cumulative reward might be attainable if the agent switches another policy. In some scenarios, this higher potential reward may be legitimate concern when fairness is evaluated. The following stronger notion takes this aspect into account.
Definition 3.2 (Envy-freeness (EF)). An adjustment scheme (6.) is envy-free if it holds for all i [n] that:
D. (6.) 2 max P. (6₂) for all j E [n].
(4)
An even stronger fairness notion defined below simply requires the same adjustment to be applied to all the agents. It is completely fair in sense.
Definition 3.3 (Strong envy-freeness (SEF)). An adjustment scheme (ō.)xE()) is strongly envy-free if 6, = Ōÿ for all i E [n]]
Let DWEF, DEF, and DSEF denote the sets of adjustment schemes complying with the above fairness notions respectively. It is not hard to see that: DWEF DEF 2 DSEF-
Besides achieving EFness, the original goal of policy teaching is to incentivize the agents to use π Hence, will call adjustment schemes that satisfy equation ① feasible schemes (Definition 3.4 Indeed, the definitions of WEF and SEF would be meaningless without the feasibility requirement, in which case they can be achieved trivially by providing zero additional reward every agent. (The definition of EF, on the other hand, already incorporates the incentive constraints as equation 3 also includes the where = j. except that there is no robustness requirement.)
Definition 3.4 (Feasibility). An adjustment scheme (6.)sE(n) is feasible (with respect to robustness guarantee 0) if equation holds for all i [n:].
Sometimes only bonuses (non-negative additional rewards) are allowed, e.g., when one can provide the agents with subsidies but cannot penalize them. Hence, we are also interested finding non- negative adjustment schemes defined as follows.
Definition 3.5 (Non-negativity). An adjustment scheme (ō:))e(m) is non-negative if 5; o) 2 0 for all i [n). E S, and E A.
Similarly to the single-agent policy teaching problem, cost-minimizing solutions are desired. We consider the sum of the teaching costs in the multi-agent setting:
cost (5)
Σ kE
(5s).
4 Existence of Fair Solutions
Before we delve into the computation of a cost-minimizing solution, we first investigate the existence of a solution with respect to the above defined fairness notions and requirements. Throughout this section, we assume that the original rewards are bounded in the interval [-h, h1. i.e., R1(s, a) [-h, hi] for all 8, a, and i. Our first result shows that a fair and feasible solution always exists under all of the above faimnss notions, in particular under the strongest notion SEF.
5

---

(1,1)
(0,0)
8ar
Sy
A=
(0, 0)
(1, 1)
Figure 2: There two agents, whose discount factors are " 0.9 and 7/2 0.5, respectively. S= {82, Sy: 83 = {a, b). and all transitions are deterministic. Originally, the agents' reward functions are the same and their rewards are annotated (s, a) = 0 and Rt (s, =
vectors on the edges, with Rí (s, a) (2(s,6) = for all s E S. The states and Sy are chosen as the initial state with equal probability. The target policy π², highlighted in red, such that ' T*(s) for all s S (i.e., it always selects action a).
Theorem 4.1. For any robustness guarantee an SEF and feasible adjustment scheme always exists
Proof sketch. The idea is to penalize actions not following the target policy by a sufficiently large value. We construct adjustment scheme (ōt)ies where
0,
if = =
8,(5, a) -
maxvelm)
2h
otherwise
1-7,-
for all and [n]. The scheme is obviously SEF 6; is the same for all the agents. can also be verified that it is feasible. Intuitively, the penalty is so large such that once the agent is penalized, the subsequent cumulative rewards cannot compensate for the loss due to this penalty even the highest rewards are attained at every subsequent step.
Nevertheless, the reverse is not true. If we only allow non-negative schemes, the existence of feasible solution cannot be taken for granted, and in general one cannot hope teach a target policy by placing large bonuses on actions following the target policy. As we prove in Theorem 4.2) the example illustrated in Figure P does not admit any EF feasible solution (and hence neither an SEF one), even though it involves only two agents and the agents have the same reward function (but different discount factors).
Theorem 4.2. For any robust guarantee
feasible adjustment scheme that WEF and
non-negative may not exist, even when there are only two agents and their reward functions are the same.
Proof. We show that there exists no feasible adjustment scheme that WEF and non-negative in the example illustrated in Figure 2 Suppose for the sake of contradiction that there exists scheme (81,5) which EE, non-negative, and feasible.
Without loss of generality, we can assume that (s, (s, = 0 for all s E S. Indeed, it is not hard see that if there exists a WEF and feasible scheme with some or all of these values being strictly positive, it will remain WEF and feasible if these values are reset to 0. Hence, it remains to pin down the values for action in the adjustment scheme. For ease of description, let x; 5,(5,, a) and y (g a) for i 21,2).
We first argue that the following two inequalities hold:
I 22: and y2 91.
(5)
To see this, consider the WEF constraints defined in B. The adjustment scheme considered is WEF, so pf (8)) 2 PT (8_.), where -i the index in {1,2) 2} that is different from i. Hence,
0.5 V.T" (s, (.) + 0.5 V (sy 6,) 2 0.5 Vi"" (sz 8 - 0.5 V," (sy 6_1),
(6)
Full proof's and omitted proofs all be found in the appendix.

---

where 0.5 is the probability in the initial distribution. It is easy to derive the V-values of 82 and sy under n² as neither of them depends on the V-values of any other states. We have
V (ex 6,) QF (s a 0gz) --m 43g
(7)
and
V (sy 8,) OF (sy: a ,ÿ) V/-
(8)
Plugging these two equations back into 6 gives
0.5 1-% + 0.5 2 0.5
1 1-7-1 x + 0.5 yー--
Replacing Y with the corresponding values gives
10 xι + 91 2 10 x2 + 1/2
(9)
2. V2
2 + y1
(10)
Hence, 2 gives #1 2 T2, and
O +5x
IC gives 1/2 2 y1.
Next, we turn to the feasibility constraints. The assumption that 6; is feasible means that
Q (Sg, 6,) 2 QT (s2, b 6.) + = 1 + 7 V." (sy | 6.) +
and O (sy, 62) 2 QT (sy, b 0.) - 78 V (sx 6.) te
Substituting and into the above two equations gives:
1 2i I2 yi (1-)) 1j 7
(11)
Using 5 and
we get that
9 +1 S 1/2 < 4 22 - 4-21- 21
This means that 1 < 0 and contradicts the assumption that is a non-negative scheme.
It turns out that the agents' discount factors play a crucial role: an identical discount factor is sufficient for ensuring the existence of feasible SEF solution. We present this result below.
Theorem 4.3. When the agents have the same discount factor, feasible adjustment scheme that is also SEF and non-negative always exists, for any robustness guarantee >
Proof sketch. Suppose that 71 Yn 7. Let H scheme 8 (ō)))
-
2- h We construct the following
H +++2 1 H Evesr P(s,a,8'), =f)= otherwise
(s
0,
for all s and E [ni], where ST denotes the set of terminal states in S.
The scheme is obviously non-negative and SEF, so it remains to argue that is feasible. Intuitively, 6; results in the agent receiving reward that is sufficiently large (and is roughly the same) at every step if the agent follows n². Rewards are adjusted by a factor of 1/(1 - 77 at the subsequent terminal states that is if the process continues forever with the same reward H generated every step (but the cumulative reward r-1- H is paid off at once). Therefore, under d, the process is equivalent to an fhiiite-horizon process where the agent gets (roughly) constant positive reward H at every step if the agent follows x² This loss due not following s² at some step is H. and it is sufficiently large so that the optimal choice for the agent in such process is to always follow n²*
5 Computing an Optimal Fair Solution
In terms of the computation of a cost- minimizationn fair solution, our main result is as follows. For each of the EF notions we defined above, the set of fair solutions lie in a convex polytope defined by polynomially many linear constraints. Hence, to find out cost minimizing solution can be formulated as convex optimization problem given that the cost function 2 is a convex function of the adjustment scheme. We show how the various types of constraints that need to be incorporated can be written as linear constraints next.
7

---

Feasibility Constraints A feasible scheme is characterized by the following linear constraints, where addition to the variables (, a) encoding the adjustment scheme, we add an auxiliary variable (i(s) for each 8 E S, and Qi(s, a) for each pair (s, a) E S x A. The auxiliary variables correspond to the V- and Q-functions of the target policy when applied.
Vi(s) (
for all i, for all i, s,
(12a)
Qi(s,a) = Rs(s, + 6,(s,)) + Σ a(s,a,s)) Vi(s') s'E8
(12b)
Qi (x, 2 (,( +E
for all i, + (b)
(12c)
Specifically, the first two lines follow from the Bellman equation and capture the values V (s 6,) and O7 (x, 6)); the last line is the incentive constraints and enforces á to feasible.
Next, we consider each of the fairness notions.
To enforce SEF simply amounts to the following constraints for each pair of agents i, E [n), which enforces the schemes to identical.
SEF Constraints
0,(s, a) as)
for all s, a
(13)
WEF Constraints enforce WEF, we add variables Vi, and Qu, to capture the values V (s 5,) and Q, (s, a 65), i.e., the values agent would have got had they been offered the adjustment for agent j. Then we add the following constraints, which are similar the Bellman equation, that these additional variables acquire the desired values.
Vis(s) = Qis(s, Qry(s,a) (, + 0,(0,
for all i,j,
(14a)
Σ P(s,a,s') Vo'( s'E8
for all 8,
(14b)
Thus, WEF simply amounts to the following constraints for each pair of agents i, e [n] (recall that z is the distribution of the initial state);
Exes 2a Vi(+)= 2 Exes R. (s,(s)
for all 8, a
(15)
EF Constraints Similarly to the approach for handling the WEF constraints, we need additional variables to capture the values of each agent had they been offered adjustment 5,. Indeed, we also use the constraints in and (15 but replace (44a) with the following one:
(*)( Z Qi)(s,a)
for all i,
(16a)
which associates (s) to the maximum Qi,(s, a), instead of (i, --' (s)). Note that under these constraints, the value of Vs)(() (s) in solution is not necessarily equal to the V-value of under the optimal policy; is only an upper bound of them. This will not cause any issue to the approach since the solution EF if and only if 15 holds for some upper bounds (s) of V, (s 6,).
Non-negativity Constraints Finally, to enforce non-negativity, we simply need the additional constraint: (5 a) 2 0 for all i, s, and
Price of Fairness
We now consider the price of faimess (PoF). The PoF measures the increase of teaching cost due to similar spirit the celebrated concept of the price of anarchy (PoA)
consideration of fairness. in game theory, the PoF compares the ratio between the minimum costs with and without fairness constraints. We define the POWEF PoEF, and PoSEF for our three fairness notions, which stand for the prices of WEF, EF, and SEF, respectively. Formally, let In,m, be the set of instances with agents, state-action pairs (i.e.,
|S| |4D, and < X for all E [n]. We define
min EF and feasible / cost(8)
PoEF (n, m, A) = max
IEIn,
minl; feasible for cost
8

---

copies
S1
8r
(c.
(0.
0)
(0,...,0) 0)
8.
(-1.0......)
Figure 3: There are n agents with discount factors m ....:" ./n y. A b,, c) and all transitions are deterministic. The initial rewards are annotated at the corresponding edges, and they the same for agents 2,..., n (agent 1 has different reward for action c). There are L 1 sets of additional copies of 8t. 8m. and 8r. Every copy of 81 and 8p is connected to the copy of 8m in the same set. In addition, copies of 81 and 8, are also connected to 8. (who has no copies). Each new connection has the same initial rewards as its original copy. The initial state follows uniform distribution over St, Sm, and all their copies. The target policy is highlighted red: x x*(s) = xt (s,) d. and nt (s+) (and the same for the corresponding copies).
Namely, the value indicates how large the price can be for instances at the same scale. The PoWEF and PoSEF can be defined in the same way with the corresponding notions.
We analyze the asymptotic growth of the PoF as functions of n, m, and X. The results are presented in Theorem 6. and all the bounds are tight. The PoF increases linearly with À and sublinearly with the size of the MDP in all the cases, and the PoEF and PoSEF also grows linearly with the number of agents involved.
Theorem 6.1. PoWEF m. A) O(A Vm), PoEF m, A) @(2 n /m). and PoSEF(n, m, A) O(A mm).
Due to space limit, we leave the detailed proofs of the PoF bounds the appendix and only provide some intuition about the bounds here. The lower bounds are obtained with the hard instances illustrated in Figure Without fairness consideration, all agents except agent already find the target policy optimal, whereas agent 1 prefers action e to d at state s,. Hence, it suffices to give agent a bonus of for taking action c, and the overall cost is 1. Now consider the fairness constraints and suppose that we still provide a bonus 8, (s., c) = 1. The consequence is that agents 2,.... n will be envious of this bonus agent 1. To achieve SEF for example, the same bonus will have be offered to these agents as well. However, a bonus on will also incentivize the agents to take action b instead of a, leading to violation of the feasibility constraint. Inevitably, to construct feasible and fair in this example, we cannot hope to only modify the reward for action (and only the reward for agent 1 when EF and SEF are considered). Modifying the other rewards however much more costly since each one of them has L copies of themselves, which requires the same modification by symmetry.
To derive the upper bounds, for the POWEF we construct the following adjustment scheme 5 (dt)sejn in a similar approach to proving the existence of a fair solution in Theorem 4.1
0, 2 I-77
if (s)
((
C, otherwise
where C; denotes the minimum cost for teaching agent i when fairness is not considered. Let o; be the adjustment achieving the minimum cost for each i. It can be easily verified that ||
< 2 v
for all i E [n]. and hence Po PoWEF(n, m, A) E.etn 11&:ll
O (A. Vm). Moreover, 8 is WEF since
Exemy |.TT|
the scheme only penalizes actions that do not follow the target policy. The argument for showing that 6 is feasible is more involved and we leave it to the appendix. A similar approach can be used to derive the upper bounds of the PoEF and the PoSEF, where we penalize actions that do not follow the 3 policy even more, by max T-%5" Cy. This also leads to dependency on n in the bound.

---

POWEF
PoEF
POSEF
No restriction Non-neg & identical 7
@ vm)
@(A. n m. O n m
@ n m O n -V
O(A- -n- vm)
Table 1: Summary of the PoF.
6.1 PoF with Non-negative Adjustments
We also investigate PoF with non-negative adjustments and compare the costs of the best non non-negative adjustment schemes with and without the fairess constraints. Since a feasible and fair solution may not exist with non-negative adjustments, we analyze the case where the agents have the same discount factor. The existence of feasible fair solution is guaranteed in this case according to Theorem 4.33 The PoF bounds are presented in Theorem 6.2 where the PoWEF now also depend on the number of agents, and the bounds of the PoEF and PoSEF depend quadratically on X.
Theorem 6.2. When the scheme is required to be non-negative and all the agents have the same discount factor, holds that PoWEF (n. m, A) = @(x n vm). PoEF(n, m, A) O(22. n /m). m,
and PoSEF (n, m, X) = ( n .e.mm m)).
The reason why the lower bound of the PoWEF now increases with n can be seen intuitively from the instances in Figure 3 too. Now that the adjustments must be non-negative, to incentivize agent 1 to choose action e, a bonus of at least has be offered. Accordingly,
order for agent (or any agent i 2 2) to not envy this bonus, additional bonuses must be offered to them as well, resulting in growth with the number of agents. (Without non-negativity, we can penalize agent 1 instead of offering agents 2, n bonuses to avoid dependency in the lower bound of the POWEF.) The proofs of the bounds can be found in the appendix and all the PoF bounds are summarized in Table
Conclusion
We studied the fairness issue in policy teaching and adopted the notion of envy-freeness to formalize the problem. Several fundamental questions regarding the existence of a fair solution, the computation of cost-minimization solution, and the price of considering fairness have been answered in the paper. For future work, it would be interesting to generalize the model to other reward design settings, where a larger set of design objectives or cost measures can be considered. For example, one can use the cumulative payment of the teacher as the cost measure. Indeed, since the cumulative payment is linear function of the adjustments, the same computation approach we presented applies by replacing the objective function, whereby we obtain a linear program. In terms of the PoF bounds, in a previous version of this work we conjectured that similar bounds can be derived with the cumulative payment cost measure, but it turns out the PoF might also depend on other factors such as the initial state distribution. A detailed analysis of the bounds is an interesting direction for future work.
Limitations As we mentioned earlier in the paper, policy teaching is equivalent to reward poisoning from technical point of view. Hence, almost any techniques that applies to policy teaching also applies immediately to solve reward poisoning problems. We note this potential negative social impact of our results but also remark that since our consideration is fairness we are not aware of any scenario where malicious party considers fairness when launching a poisoning attack. There are many other notions of fairness, equity, and equality. The EF notions we studied are concerned with the additional rewards provided by the adjustment scheme but not with the overall rewards. Hence, they are not applicable the latter should be the key consideration.
Acknowledgments and Disclosure of Funding
The authors thank Warut Suksompong for useful suggestions on the related work and the anonymous reviewers for their insightful comments.
10

---

References
[1] Richard Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press, 2018.
[2] Chen Tessler, Daniel Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference on Learning Representations (ICLR "18), 2018.
[3] Deirdre K. Mulligan, Joshua A. Kroll, Nitin Kohli, and Richmond Y. Wong, This thing called fairness: Disciplinary confusion realizing a value in technology. Proc. ACM Hum..CCmmp Interact., 3(CSCW), nov 2019.
[4] Francis Edward Su. Rental harmony: Sperner's lemma in fair division. The American mathe- matical monthly, (06(10):930-944) 1999.
[5] Jiarui Gan, Warut Suksompong, and Alexandros A Voudouris. Envy-freeness in house allocation problems. Mathematical Social Sciences, 101:104-106, 2019.
[6] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual symposium on theoretical aspects of computer science (STACS pages 404-413. Springer, 1999.
[7] Haoqi Zhang and David C. Parkes. Value-based policy teaching with active indirect elicitation. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI '08), pages 208-214 2008.
[8] Haoqi Zhang, David C Parkes, and Yiling Chen. Policy teaching through reward function learning. In Proceedings 10th ACM Conference on Electronic Commerce (EC '09), pages 295-304, 2009.
[9] Kiarash Banihashem, Adish Singla, Jiarui Gan, and Goran Radanovic. Admissible policy teaching through reward design. arXiv preprint arXiv:2201.02188 2022.
[10] Yuzhe Ma. Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. In Advances in Neural Information Processing Systems (NeurIPS '19), pages 14543-14553, 2019.
[11] Yunhan Huang and Quanyan Zhu. Deceptive reinforcement learning under adversarial manipu- lations on cost signals. In International Conference on Decision and Game Theory for Security (GameSec '19), pages 217-237, 2019.
[12] Amin Rakhsha, Goran Radanovie, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching in reinforcement learning via environment poisoning attacks. CoRR, abs/201 2020.
[13] Yanchao Sun, Da Huo, and Furong Huang. Vulnerability- aware poisoning mechanism for online rl with unknown dynamics. In International Conference on Learning Representations (ICLR
2 I), 2021.
[14] Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive reward-poisoning attacks against reinforcment learning. In Proceedings of the 37th International Conference on Machine Learning (ICML 200, pages 11225-112322 2020.
[15] Maja Mataric. Reward functions for accelerated learning. In ICML, pages 181-189, 1994.
[16] Marco Dorigo and Marco Colombetti. Robot shaping: Developing autonomous agents through learning. Artificial intelligence, 71(2):321377,, 1994.
[17] Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transfor- the mations: Theory and application to reward shaping. In Proceedings the 16th International Conference on Machine Learning (ICMI. '99), pages 278-287, 1999.
[18] Duncan Karl Foley. Resource allocation and the public sector. Yale University, 1966.
[19] G Gamow and M Stern. Puzzle-math, edn. Viking, 1958.
[20] Hervé Moulin. Fair division and collective welfare. MIT press, 2004.
11

---

[21]
Kenneth Arrow, Amartya Sen, and Kotaro Suzumura. Handbook of social choice and welfare, volume 2. Elsevier, 2010.
[22] Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78-86, 2010.
[23] Ariel D. Procaccia. Cake cutting: Not just child's play. Commun. ACM, 56(7):78-87, 2013.
[24] Daniel Halpern and Nisarg Shah. Fair division with subsidy. In Proceedings of 12th International Symposium (SAGT 119), page 374-389, Berlin, Heidelberg. 2019. Seringer-Verlag
[25] Xiaojin Zhu, Liu, and Manuel Lopes. No learner left behind: On the complexity teaching multiple learners simultaneously. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI '17), pages 3588 -398,599, 2017.
[26] Teresa Yeo, Parameswaran Kamalaruban, Adish Singla, Arpit Merchant, Thibault Asselborn, Louis Faucon, Pierre Dillenbourg, and Volkan Cevher. Iterative classroom teaching. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI '19), 2019.
[27] Ritesh Noothigattu, Tom Yan, and Ariel D. Procaccia. Inverse reinforcement learning from like-minded teachers. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2/), pages 9197-9204 2021.
[28] Paul Duetting, Tim Roughgarden, and Inbal Talgam-Cohen. The complexity of contracts. SIAM Journal Computing. 50(1):21 1-2244, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "lNtHKM3ZGmy", "reviewer": "Reviewer_CDiZ", "summary": "The paper looks at the problem of policy teaching, where a teacher wants to incentivise agents to follow a particular policy, under the constraint of incentives being fair in the sense that they are envy-free. The paper first proposes some definitions of envy-free (EF) teaching and fairness in this context. They then prove a negative and a positive result characterizing when EF policies exist. They discuss the tractability of finding cost-minimizing solutions under two natural cost functions, and introduce the concept of a price of fairness - the additional cost of the teaching incurred by following the EF conditions\n", "questions": "The result that EF strategies may exist for non-negative incentives, if agents’ discount factors are not equal, receives a large amount of the total text. I think theorem 4.3 and section 6 are more important contributions and could be prioritized.\n", "limitations": "The authors have a good argument as to why the connection to reward poisoning isn’t a concern, which is actually repeated (I’m not sure that’s necessary).\n\nThe authors don’t discuss / reference the limitations of EF as a concept. While it is a common concept in game theory, it may not correspond to what we consider to be fair or equitable. E.g. if two people are both given the same large incentive to use their right hand to complete a task, in the sense of the paper this is envy free (indeed, ‘completely fair’), but a left handed person would probably not agree that it was actually fair.\n\nIt seems a little unlikely that the EF concept cannot be extended to a situation where agents are incentivized to follow different strategies, because in general effective EF incentives may not exist. This limits the potential of future work unfortunately.\n", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper was written clearly, the contributions were well spelt out, and the preliminaries detailed thoroughly. (A minor comment on presentation: I found the notations x_i = \\delta_i(s_y, a) (and vica-versa) a little confusing, it seemed like a more natural choice was x_i  = \\delta_i(s_x, a)).\n\nThe results given establish some useful properties about the new concepts introduced, and I feel like they provide some intuition about the nature of the EF teaching policies. I liked that the authors considered the case of only positive reward interventions.\n\nThe limitation that the agents are operating in independent environments is an unfortunate but clearly necessary limitation. I think there are practical examples where this is a sensible model though, so I would suggest adding some examples to this effect to motivate the setting.\n\nI would have liked to see some analysis of the case where agents are being taught to follow different policies. There are some reasonably obvious negative results in this case (if agents A and B prefer different strategies, you can’t swap their strategies around without one of them envying the other), but are there any cases where (s)EF conditions can be met?\n\nThe definition of EF is quite weak: it amounts more or less to all agents receiving the same reward adjustments when following the incentivised policy. But agents would adapt, so I think EF is much better captured by the SEF definition. I would recommend naming EF - Weak EF and Strong EF to EF to reflect this.\n\nI found section 5 less interesting, it more or less only points out that the constraints are linear ones.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JeJNA_Vnfs6", "reviewer": "Reviewer_LYiW", "summary": "The authors present a theoretical contribution, connecting concepts from the theory of fair division to the problem of policy teaching in reinforcement learning. More precisely, they introduce several constraints inspired by \"envy-freeness\" to the setting of policy teaching by reward adjustment for heterogeneous reinforcement learning agents, each of which is interacting independently in the same single-agent Markov decision process. The authors prove that envy-free adjustment schemes exist in general if and only if negative reward adjustment are available. They go on to show that the problem of finding such schemes is tractable in principle, being a convex optimization problem with linear constraints. Finally, they prove asymptotically tight bounds for the cost of fairness, analogous to the price of anarchy from game theory. ", "questions": "1. What are the clearest motivations for this work? How do you see it impacting the field in the future?\n\n2. Is the convex optimization problem in Section 5 soluble for \"large\" MDPs (e.g. gridworlds or extensive-form games)?\n\n3. Why is the cumulative measure of cost a good one to use? It feels like there is an underlying \"implementation\" you have in mind for the teacher being an RL agent, but this isn't explicitly stated. If that is the case, how might your results be impacted by the teacher and \"students\" being co-optimized?", "limitations": "The authors could be a bit more precise about how these theoretical results might translate into empirical outcomes, sketching out any limitations along the way. Having said this, they do a good job of expressing the problem in terms of convex optimization, and of proving asymptotically tight complexity bounds.\n\nThe authors comment on a potential risk from reward poisoning, but point out that bad actors may not be interested in fairness. It is not quite clear how true this claim is: state-sponsored reward poisoning may indeed have its risks assessed for fairness, for instance. It would be great to see a stronger argument for whether methods of implementing safety against reward poisoning are likely compatible with, or antithetical to, fairness. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The paper is well written, with a clear abstract, good notation, well articulated definitions, and rigorous proofs. \n- Theorem 4.2 is particularly interesting and significant, with implications for how one might think about reward shaping choices in both single-agent and multi-agent settings.\n- The example figures are well-motivated and well-explained. Figure 3 gives good intuition for the price of fairness scaling laws. \n- To the best of my knowledge, the work is a novel intersection of these two important areas of research (RL and fair division). \n\nWeaknesses\n\n- The motivation for the paper could be more strongly articulated. Are the authors imagining that this line of research leads to better mechanism design for fair outcomes among populations of humans? Or are there particular settings where there will be heterogeneous artificial agents and fairness of reward shaping will be an important consideration?\n- In Figure 1, it is not clear why s_l is optimal on the right hand side. Should it not have a small positive reward \\epsilon to make it a unique rewarding terminal state. \n- The related work is a little thin on the ground. I would love to see a stronger connection drawn with inverse RL, which is strongly related to policy teaching. Some Inverse RL papers are cited, but I think a sentence or two here eliciting the distinction from / similarity to inverse RL in their setting would be worthwhile. \n- The conclusion does not sketch particularly clear lines for future work. In particular, might the authors be interested in extending these results to the interactive multi-agent setting? It is known that different reward shaping is required to solve different multi-agent problems (see e.g. https://arxiv.org/pdf/1803.08884.pdf) and indeed different reward schemes have lately been used in various mechanism design settings (see e.g. https://arxiv.org/abs/2004.13332, https://www.nature.com/articles/s41562-022-01383-x). \n- Some minor errors in grammar e.g. \"policy\" line 123, \"\\delta_j\" line 163, \"limits\" line 287 etc. I recommend an additional proof read.\n- There are no empirical results. In particular, it is not quite clear how feasible it is to solve the convex optimization problem in Section 5 for an MDP of real-world relevance. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H_SUFQ5vtW", "reviewer": "Reviewer_UkNf", "summary": "The paper studies how a teacher could teach a target policy to multiple agents, subject to fairness constraints. In particular, the paper focuses on envy-free fairness, under which all agents would prefer their own adjustments over anyone else's.\n\nThe contributions of the paper are theoretical in nature and include:\n1. Proving the existence of CF solutions when adjustments could be negative.\n    1.a While also showing that when adjustments are limited to nonnegative ones, there exist settings under which no EF solution exists.\n    1.b But when agents have the same discount factor, there also exists CF solutions with nonnegative adjustments.\n2. Showing how optimal fair solutions may be attained with suitable constraints.\n3. Deriving the price of fairness under different settings.", "questions": "My concerns and questions are mostly on the significance and motivation side. \n1. Are there practical use cases for the problem setting and algorithms discussed in this paper? Are there real-world scenarios that could be easily translated to policy teaching with fairness constraint? As the paper features a novel combination of fairness and policy teaching, it would be greatly appreciated if it could detail the motivation behind such combination.\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n1. Originality:\n    - The problem setting proposed by the authors is novel, combining both policy teaching and fairness. Related works are adequately cited and given credit to and the difference between this work and prior works is made clear.\n2. Quality:\n    - I have checked the supplement and could not identify any glaring mistake in the proofs.\n    - Moreover, the paper is keenly aware of the potential negative social impact of the work from the policy poisoning perspective.\n3. Clarity:\n    - Overall the paper is well-written, but there are some formatting inconsistencies (expanded later).\n\n**Weaknesses**:\n1. Clarity:\n    - Definitions 3.4 and 3.5 are not capitalized, whereas Definitions 3.1 - 3.3 are.\n2. Significance:\n    - As the paper is a novel combination of two areas, fairness and policy teaching, the significance of the work is unclear to me. Solving the constrained optimization programs outlined in Section 5 requires that the teachers know the transition probabilities as well as all agents' reward functions. It is unclear to me what kind of problems fall into this problem setting.\n        - For instance, in the motivating example of ride-share platforms encouraging good behavior from passengers, it is not clear to me what would a corresponding MDP look like.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9etmZVtVbhy", "reviewer": "Reviewer_sVfc", "summary": "The authors here consider a model of envy-free policy teaching.  At a high level, some number of agents are independently maximizing their own personal reward function over a MDP with the same state-space and transition dynamics.  The principal wants to teach a specified target policy to each individual, and does so by modifying the agent's individual reward functions with \"incentives\" (either additive penalties or costs for taking specific actions in certain states).  Naively, these incentives can lead to envy behaviour (where one agent is given a large increase cost for taking a certain action which other agents could be envious of).  The authors introduce a concept of envy freeness, and show that an EF solution need not exist when penalties are not allowed, but exist otherwise.  They also show an explicit worst-case bound on the price of fairness which scales linearly with the discount factor, size of the MDP, and number of individuals.\n\nTo be more concrete, the authors consider a setting with $n$ agents.  Each agent is faced with an MDP $(S,A,R_i, P, \\gamma_i)$ where $S,A$ are the set of states and actions, $R_i$ is individual $i$'s reward function, $P$ the shared transition dynamics, and $\\gamma_i$ the per individual discount factor.  The principal wants each agent $i$ to execute a pre-specified target policy $\\pi^\\star$ (which need not be the optimal policy).  This can be done by adding an additional \"reward adjustment function\" $\\delta_i : S \\times A \\rightarrow R$ which is provided to agent $i$ upon taking action $a$ in state $s$.  The goal of the principal then is to find a cost-efficient way of teaching this target policy to all of the individuals, potentially by minimizing the expected cumulative payment across all of the individuals.\n\nIntuitively, these incentive schemes need not be fair.  The authors then go on to model three definitions of envy-freeness (denoted EF, SEF, and CF).  Focusing on the first one, envy-freeness, stipulates that agent $i$ receives more reward under their adjustment scheme $\\delta_i$ under policy $\\pi^\\star$ than under the adjustment scheme $\\delta_j$.  This is a natural fairness yardstick, essentially ensuring that each agent prefers their own adjustment scheme to the adjustment scheme of any other agent.  With this the authors show two main results:\n1. First the authors show that there exists a fair feasible solution, and the solution is efficiently computable by a linear program.  However, under the additional restriction that $\\delta \\geq 0$ the authors show that an adjustment need not exist, unless additionally the discount factors are the same.\n2. Next the authors show explicit bounds on the price of fairness, essentially the increased cost in designing incentives which are additionally envy free.\nThese results are then repeated (and adjusted) under the other two stronger envy-freeness guarantees.", "questions": "### Questions\n1. The LP based approach for finding the reward adjustment function only works in the setting with known reward and transition dynamics.  Have the authors thought about extending the techniques to a learning framework, where the MDP primitives and the reward adjustments need to be learned jointly?\n2. The Price of Fairness guarantees presented are worst-case, do the authors have any intuition on more \"instance-specific\" losses, potentially also observed with the different choice of cost measures as well?\n\n### Minor Comments\n- Related work section was great!\n- Line 143 does not discuss the way to aggregate the cost measures across agents (although this is introduced later)\n- Line 163 $j$ for $\\beta$\n- Found the OPT notation in Equation 4 a bit strange", "limitations": "The authors do not address the potential societal impact of their work explicitly in the paper. However, while practically motivated, the model considered here by the authors is mostly theoretical. Any concrete implementation of envy-free incentive design in a real-world setting has additional challenges around scalability, choice of fairness metrics (with potential adverse side-effects for other metrics), adversarial behavior, etc, which is not addressed in this theoretical work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- Model + Theoretical Results: The paper makes strong modeling and methodological contributions by introducing the envy-free set-up for incentive design for multi-agent MDPs.  This extends the well-studied envy-freeness concepts in fair resource allocation to policy design in MDPs.\n- Quality of Results: The authors provide detailed theoretical results both outlining 1) when EF incentives can be computed, 2) how to compute them, 3) at what loss, providing a complete story behind the envy-free incentive design model.\n- Relation to Existing Literature: The authors do a good job relating the current analysis and model to the RL, reward shaping, and fair resource allocation literature.\n\n### Weaknesses\n- Weakness of Results: One of the larger weaknesses in the results is the strong assumptions for computationally finding the envy-free incentives.  The LP based approach requires exact knowledge of the reward and transitions, which is impractical for many settings.\n- Writing + Practical Motivation: The authors should include a practical motivating example to help instantiate the discussion and help the model become more clear.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept