Stateful Strategic Regression
Authors: Keegan Harris
Hoda Heidari
Steven Wu
Venue: NeurIPS 2021 Poster (2021)
Keywords: strategic regression
effort accumulation
stackelberg equilibrium
oracle access optimization

Abstract: Automated decision-making tools increasingly assess individuals to determine if they qualify for high-stakes opportunities. A recent line of research investigates how strategic agents may respond to such scoring tools to receive favorable assessments. While prior work has focused on the short-term strategic interactions between a decision-making institution (modeled as a principal) and individual decision-subjects (modeled as agents), we investigate interactions spanning multiple time-steps. In particular, we consider settings in which the agent's effort investment today can accumulate over time in the form of an internal state - impacting both his future rewards and that of the principal. We characterize the Stackelberg equilibrium of the resulting game and provide novel algorithms for computing it. Our analysis reveals several intriguing insights about the role of multiple interactions in shaping the game's outcome: First, we establish that in our stateful setting, the class of all linear assessment policies remains as powerful as the larger class of all monotonic assessment policies. While recovering the principal's optimal policy requires solving a non-convex optimization problem, we provide polynomial-time algorithms for recovering both the principal and agent's optimal policies under common assumptions about the process by which effort investments convert to observable features. Most importantly, we show that with multiple rounds of interaction at her disposal, the principal is more effective at incentivizing the agent to accumulate effort in her desired direction. Our work addresses several critical gaps in the growing literature on the societal impacts of automated decision-making - by focusing on longer time horizons and accounting for the compounding nature of decisions individuals receive over time. 

Stateful Strategic Regression
Keegan Harris
Hoda Heidari
Zhiwei Steven Wu
School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213
School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 hheidari@cmu, edu
School of Computer Science Carnegie Mellon University Pittsburgh, 15213
keeganh@cmu. edu
zstevenwu@cmu. edu
Abstract
Automated decision-making tools increasingly assess individuals to determine if they qualify for high-stakes opportunities. recent line of research investigates how strategic agents may respond to such scoring tools to receive favorable assessments. While prior work has focused on the short-term strategic interactions between decision-making institution (modeled subjects (modeled as agents), we investigate interactions spanning multiple time- steps. In particular, today can accumulate over time the form of an internal state-impacting both his future rewards and that of the principal. We characterize the Stackelberg equilibrium of the resulting game and provide novel algorithms for computing it. Our analysis reveals several intriguing insights about the role of multiple interactions in shaping the game's outcome: First, we establish that in our stateful setting, the class of all linear assessment policies remains as powerful as the larger class of all monotonic assessment policies. While recovering the principal's s optimal policy requires solving non-convex optimization problem, we provide polynomial-ting time algorithms for recovering both the principal and agent's optimal policies under common assumptions about the process by which effort investments convert to observable features. Most importantly, we show that with multiple rounds of interaction at her disposal, the principal more effective incentivizing the agent to accumulate effort in her desired direction. Our work addresses several critical gaps in the growing literature on the societal impacts of automated decision- making- by focusing on longer time horizons and accounting for the compounding nature of decisions individuals receive over time.
principal) and individual decision-
consider settings in which the agent's effort investment
1 Introduction
Automated decision-making tools increasingly assess individuals to determine whether they qualify for life-altering opportunities in domains such lending [27], higher education [32], employ- ment [41], and beyond. These assessment tools have been widely criticized for the blatant disparities they produce through their scores [43, 3]. This overwhelming body of evidence has led remark- ably active area of research into understanding the societal implications of algorithmic/data-diiee automation. Much of the existing work on the topic has focused on the immediate or short-term societal effects of automated decision-making. (For example, thriving line of work in Machine Learning (ML) addresses the unfairness that arises when ML predictions inform high-stakes deci- sions [18, 22, 31, 8, 1, 16, 11] by defining it as a form of predictive disparity, e.g., inequality in false-positive rates [22, 3] across social groups.) With the exception several noteworthy recent articles (which we discuss shortly), prior work has largely ignored the processes through which algorithmic decision-making systems can induce, perpetuate, or amplify undesirable choices and behaviors.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

Our work takes a long-term perspective toward modeling the interactions between individual deci- sion subjects and algorithmic assessment tools. We are motivated by two key observations: First, algorithmic assessment tools often provide predictions about the latens qualities of interest (e.g., creditworthiness, mastery of course material, or job productivity) by relying on imperfect but observ- able proxy attributes that can be directly evaluated about the subject (e.g., past financial transactions, course grades, peer evaluation letters). Moreover, their design ignores the compounding nature of advantages//issadvaaaag
individual subjects accumulate over time in pursuit of receiving favor- able assessments (e.g., debt, knowledge, job-related skills). To address how individuals respond to decisions made about them through modifying their observable characteristics, a growing line of work has recently initiated the study of the strategic interactions between decision-maker and decision-subjeet (see, e.g., [15, 26, 36, 30, 21]). This existing work has focused mainly on the short-term implications of strategic interactions with algorithmic assessment tools-e.g. by mod- eling it as single round of interaction between principal (the decision-maker and agents (the -euieesn-subjects) [30]. In addition, existing work that studies interactions over time assumes that agents are myopic in responding the prcision-maker" policy [4, 42, 38, 15). We expand the line of inquiry to multiple rounds of interactions, accounting for the impact of actions today on the outcomes players can attain tomorrow.
Our multi-round model of principal-agent interactions. We take the model proposed by Kleinberg and Raghavan [30] as our starting point. In Kleinberg and Raghavan's 's formulation, a principal interacts with an agent once, where the interaction takes the form of a Stackelberg game. The agent receives score y = f0, o). in which O is the principal's choice of assessment parameters, and is the agent's observable characteristics. The score is used to determine the agent's 's merit with respect to the quality the principal is trying to assess. (As concrete examples, y could correspond to the grade a student receives for a class, or the FICO credit score of a loan applicant.) The principal moves first, publicly announcing her assessment rule O used evaluate the agent. The agent then best responds to this assessment rule by deciding how to invest a fixed amount of effort into producing set of observable features that maximize his score y. Kleinberg and Raghavan characterize the assessment rules that can incentivize the agent to invest in specific types of effort (e.g.. those that lead to real improvements in the quality of interest as opposed to gaming the system). We generalize the above setting to T' >> 1 rounds of interactions between the principal and the agent and allow for the possibility of certain effort types rolling over from one step to the next. Our key finding that longer time horizon provides the principal additional latitude in the range of effort sequences she can incentivize the agent to produce. To build intuition as to why repeated interactions lead to the expansion of incentivizable efforts, consider the following stylized example:
Example 1.1. Consider the classroom example of Kleinberg and Raghavan where a teacher (modeled as a principal) assigns a student (modeled an agent) an overall grade y based on his observable features; in this case test and homework score. Assume that the teacher chooses an assessment rule and assigns a score y = Or TTEEE + HHw HW, where TE is the student's 's test score HW is his homework score, and fy, Haw E R are the weight of each score in the student's 's overall grade. The student can invest effort into any of three activities: copying answers on the test, studying, and looking up homework answers online. In a one-round setting where the teacher only evaluates the student once, the student may be more inclined to copy answers on the test or look up homework answers online, since these actions immediately improve the score with relatively lower efforts. However, in multiple-round setting, these two actions do not improve the student's knowledge (which impacts the student's 's future grades well), and so these efforts do not carry over to future time steps. When there are multiple rounds of interaction, the student will be incentivized to invest effort into studying, as knowledge accumulation over time takes less effort in the long-run compared to cheating every time. We revisit this example in further detail in Appendix A.
Summary of our findings and techniques. We formalize settings in which the agent's effort investment today can accumulate over time in the form of an internal state-impacting both his future rewards and that of the principal. We characterize the Stackelberg equilibrium of the resulting game and provide novel algorithmic techniques for computing it. We begin by establishing that for the principal, the class of all linear assessment policies remains as powerful as the larger class of all monotonic assessment policies. In particular, we prove that if there exists an assessment policy that can incentivize the agent to produce a particular sequence of effort profiles, there also exists a linear assessment policy which can incentivize the exact same effort sequence.
2

---

Figure I: Average effort spent studying vs. average effort spent cheating over time for the example in Appendix A. The line + = 1 represents the of all possible Pareto optimal average effort profiles. The shaded region under the line represents the set of average effort profiles which can be incentivized with a certain time horizon. Darker shades represent longer time horizons. In the case where T= 1, it is not possible to incentivize the agent to spend any effort studying. Arrows are used to demonstrate the additional set of Pareto optimal average effort profiles that can be incentivized with each time horizon. As the time horizon increases, it becomes possible incentivize wider range of effort profiles.
Average Effort Cheating
T=2
T=3
T=4
06
J 2
T
0.5
Avarage Effort Studying
We then study the equilibrium computation problem, which in general involves optimizing non-convex objectives. Despite the initial non-convexity, we observe that when the problem is written as function of the agent's incentivized efforts, the principal's non-convex objective becomes convex. Moreover, under common assumption agent's conversion mapping from efforts to observable features, the set of incentivizable effort policies is also convex. Given this structure, we provide a polynomial- algorithm that directly optimizes the principal's objective over the set of incentivizable effort policies, which subsequently recovers agent's and principal's equilibrium strategies. Even though prior work [39, 40] has also taken this approach for solving other classes of non-convex Stackelberg games, our work has to overcome an additional challenge that the agent's i set of incentivizable efforts is not known a-priori. We resolve this challenge by providing membership oracle (that determines whether a sequence of agent efforts can be incentivized by any assessment policy), which allows us to leverage the convex optimization method due to Kalai and Vempala [28].
Our analysis reveals several intriguing insights about the role of repeated interactions in shaping the long-term outcomes of decision-makers and decision subjects: For example, observe that with multiple rounds of assessments, both parties can be better off employing dynamic/time-senaa sensitive strategies as opposed static/myopic ones. Crucially, perhaps most significant finding is that by considering the effects of multiple time-steps, the principal is significantly more effective at incentivizing the agent to accumulate effort in her desired direction (as demonstrated in Figure 1 for stylized teacher-student example). In conclusion, our work addresses two critical gaps in the growing literature on the societal impacts of automated decision-making-by focusing on longer time horizons and accounting for the compounding nature of decisions individuals receive over time.
1.1 Related work
A growing line of work at the intersection of computer science and social sciences investigates the impacts of algorithmic decision pocision-making models on people (see, e.g., [25, 44, 34, 15]). As we outline below, significant attention has been devoted to settings in which decision-subjects respond to the decision-make 's choice of assessment rules. Liu et al. [34] and Kannan et al. [29] prrcision-maker may respond to the predictions made by predictive
strategic and
study how utility-maximizae rule (e.g., the decision-maker may interpret/utilize the predictions a certain way or decide to update the model entirely.) Mouzannar al. [37] and Heidari al. [23] propose several dynamics for how individuals within a population may react to predictive rules by changing their qualifications. Dong al. [15], Hu al. [26], Milli et al. [36] address strategic classification-a setting in which decision subjects are assumed to respond strategically and potentially untruthfiully to the choice of the predictive model, and the goal is design classifiers that are robust to strategic manipulation. Generalizing strategic classification, Perdomo et al. [38] propose a risk tisk-minimization framework for performative predictions, which broadly refers to settings in which the act of making prediction influences the prediction target. Incentive-and aware learning [45, 2] is another generalization that, at high-level, seeks characterize the conditions under which one can train predictive rules that are robust to training data manipulations.
Two additional topics that are conceptually related to our work but differ in their motivating problems and goals are adversarial prediction and strategy-proof regression. The adversarial prediction prob-
3

---

lem [6, 13] is motivated by settings (e.g., spam detection) in which an adversary actively manipulates data to increase the false-negative rate of the classifier. Adversarial predictions have been modeled and analyzed as a zero-sum game [13] or a Stackelberg competition [6]. Strategyproo//ruttuul linear
regression [14, 12, 9] offers mechanisms for incentivizing agents to report their data truthfully.
As mentioned earlier, many of our modeling choices closely follow Kleinberg and Raghavan [30]. Below, we provide a summary of Kleinberg and Raghavan's results and briefly mention some of the recent contributions following their footsteps. While much of prior work on strategic classification views all feature manipulation as undesirable [15, 26, 36], Kleinberg and Raghavan made a distinction between feature manipulation via gaming (investing effort to change observable features in way that has no positive impact on the quality the principal is trying to measure) and feature manipulation via improvement (investing effort in such a way that the underlying characteristics the principal is trying to measure are improved). Their model consists of a single round of interaction between a principal and an agent, and their results establish the optimality and limits of linear assessment rules in incentivizing desired effort profiles. Several papers since then have studied similar settings (see, e.g., Miller et al. [35], Frankel and Kartik [19]) with goals that are distinct from ours. (For example, Frankel and Kartik find a fixed-point assessment rule that improves accuracy by under-utilizing the observable data and flattening the assessment rule.)
Finally, we mention that principle-agens games [33] are classic economic tools to model interactions in which a interrentee entity (the agent) responds to the policy/contract enacted by another (the principal) in ways that are contrary to the principle's intentions. The principal must, therefore, choose his/her strategy accounting for the agent's ss strategic response. Focusing on linear strategies is common practice in this literature [24, 7, 17]. For simplicity, we present our analysis for linear assessment rules, but later show that the class of all linear assessment policies is equally as powerful as the class of all monotone assessment policies (Theorem 3.4).
2 Problem formulation
In our stateful strategic regression setting, a principal interacts with the same agent over the course of T time-steps, modeled via a Stackelberg game.' ! The principal moves first, announcing an assessment policy, which consists of sequence of assessment rules given by parameters (0, --- Each 0, is used for evaluating the agent at round f 1,... .T The agent then best responds to this assessment rule by investing effort in different activities, which in turn produces a series of observable features {o.)?== that maximize his overall score. Through each assessment round E {l..... T) the agent receives score y/= f(,,. o,). where 0, is the principal's 's assessment parameters for round t, and o, is the agent's observable features at that time. Following Kleinberg and Raghavan, we focus on monotone assessment rules.
:R" Definition 2.1 (Monotone assessment rules). A assessment rule f(0,-) R" + R is monotone if 0(0,o) Z (00 o') ) for o& 2 of. Ak E (I........ Additionally, 3k E [I,...,n} such that strictly increasing o% strictly increases [(0, o).
For convenience, we assume the principal's 's assessment rules are linear, that is, ye f(),.o.) 0, og. Later we show that the linearity assumption is without loss of generality. We also restrict 02 to lie in the redimensional probability simplex A". That is, we require each component of 0, to be at least 0 and the sum of the n components equal 1.
From effort investments to observable features and internal states. The agent can modify his observable features by investing effort in various activities. While these effort investments are private to the agent and the principal cannot directly observe them, they lead to features that the principal can observe. In response to the principal's 's assessment policy, The agent plays an effort policy, consisting of a sequence of effort profiles (ex ) where each individual coordinate of e, (denoted by et,)) is a function of the principal's 's assessment policy (0: )r_ Specifically, the agent chooses his policy (e1," ,e)), so that it is best-response to the the principal's s assessment policy (01,... (01....,0, ..r).
Next, we specify how effort investment translates into observable features. We assume an agent's observable features in the first round take the form 0 = Oo + (ei). where On R" is the initial value of the agent's observable features before any modification. e1 E Rd is the effort the agent
1 To improve readability, we adopt the convention of referring to the principal as she/her and the agent as he/him throughout the paper.

---

expends to modify his features in his first round of interaction with the principal, and ow : R - R" the effort conversion function. parameterized by W. The effort conversion function is some concave mapping from effort expended to observable features. (For example, if the observable features in the classroom setting are test and homework scores, expending effort studying will affect both an agent's test and homework scores, although it may require more studying to improve test scores from 90% to 100% than from 50% to 60%.)
Over time, effort investment can accumulate. (For example, small businesses accumulate wealth over time by following good business practices. Students learn as they study and accumulate knowledge.) This accumulation takes the form of an internal state, which has the form S; = So + 52 -EE e, Here Q E Rdxd is a diagonal matrix in which 95.5. E (l..... d} determines how much one unit of effort (e.g., in the jth effort coordinate, ej) rolls over from one time step to the next, and So is the agent's s initial "internal state". An agent's s observable features are, therefore, a function of both the effort he expends, as well as his internal state. Specifically, On in the single-shot setting). Note that while for simplicity, we assume the accumulating effort types socially desirable, our results apply as well to settings where undesirable efforts can similarly accumulate.
ow (s: + ex) (here ow (8o) is analogous to
Utility functions for the agent and the principal. Given the above mapping, the agent's goal is to pick his effort profiles so that the observable features they produce maximize the sum of his scores over time, that is, the agent's 's utility = -'= Ur = Σx= 0, oN. Our focus on the sum of scores over time is conventional choice and is motivated by real-world examples. (A small business owner who applics for multiple loans cares about the cumulative amount loans he/she receives. A student taking a series of exams cares about his/her average score across all of them.)
The principal's 's goal is to choose his assessment rules over time so as to maximize cumulative effort investments according to her preferences captured by matrix A. Specifically, the principal's 's utility The principal's 's utility can be thought of as weighted f norm of the agent's cumulative effort, where A E Rdddd is a diagonal matrix where the element A₃ denotes how much the principal wants to incentivize the agent invest in effort component ey.
= =| el],-
Constraints on agent effort. As was the case in the single-shot setting of Kleinberg and Raghavan, assume that the agent's 's choice of effort e, at each time t is subject to fixed budget B (with respect to the & norm). Without loss of generality, we consider the case where B = 1. We explore the consequences of an alternative agent effort formulation namely quadratic cost penalty in Appendix G.
Proposition 2.2. is possible to incentivize a wider range of effort profiles by modeling the principal-agent interaction over multiple time-steps, compared to a model which only considers one-shot interactions. See Appendix A for an example which illustrates this phenomena.
3 Equilibrium characterization
The following optimization problem captures the expression for the agent's best-response to an arbitrary sequence of assessment rules. 3 (Recall that refers to the dimension of effort vectors (e, 's), and n refers to the number of observable features, i.e., the dimension of o, os.).
The set of agent besponess to a linear assessment policy, {0r)T- is given by the following optimization procedure:
T Σ 2o
{e 1 = arg max
oo 50 + eet s.t. Et, 2 0.
Σ evs S 1 Vt,j
AI..... Bep
The goal of the principal is to pick an assessment policy {0)T] in order to maximize the total magnitude of the effort components she cares about, i.e.
2 Note that while we only consider diagonal Ω E R our results readily extend to general Q E iedxa By focusing on diagonal matrices we have a one-to-one mapping hetween state and effort components. Non-di- agonal l corresponds to cases where different effort components can contribute to multiple state components. 3 Throughout this section when it improves readability, we denote the dimension of matrices in their subscript (e.g.. Xaxb means X is an b matrix).
5

---

T e
(0)) = arg max Or.....r
0r)
s.t. 0: V
where we abuse notation by treating ež as a function of (Or,..., .r). Substituting the agent's optimal effort policy into the above expression, we obtain the following formalization of the principal's assessment policy:
Proposition 3.1 (Stackelberg Equilibrium), Suppose the principal's 's strategy space consists of all sequences of linear monotonic assessment rules. The Stackelberg equilibrium of the stateful strategic regression game, ((07)-- {e) can be specified as the following bilevel multiobjective opti- mization problem. As is standard throughout the literature, we assume that the agent breaks ties in favor of the principal. Moving forward, we omit the constraints on the agent and principal action space for brevity.
{0, Hi arg
max
m ei 0r)
s.L. (eili= arg
max
Eo: ow [=l
8b + 2
+
e,
oy
3.1 Linear assessment policies are optimal
Throughout our formalization of the Stackelberg equilibrium, we have assumed that the principal deploys linear assessment rules, when a priori it is not obvious why the principal would play assessment rules of this form. We now show that the linear assessment policy assumption is without loss of generality. We start by defining the concept of incentivizability for an effort policy, and characterize it through a notion of dominated effort policy.
Definition 3.2 (Incentivizability) An effort policy {er Vi=1 is incentivizable if there exists an assess- ment policy (f(O..)) )) for which playing {ct)T=) a best response. (Note: {ct)T= need not be the only best response.)
Definition 3.3 (Dominated Effort Policy). We say the effort policy {er)T= i is dominated by another effort policy if an agent achieve the same higher observable feature values by playing another effort policy (ar)7 1T that does not spend the full effort budget on at least one time-step.
Note that effort policy which is dominated by another effort policy will never be played by rational agent no matter what set of decision rules are deployed by the principal, since a better outcome for the agent will always be achievable.
Theorem 3.4. For any effort policy (e. that is not dominated by another effort policy, there exists a linear assessment policy that can incentivize it.
See Appendix C for the complete proof. We characterize whether an effort policy {e:) is dominated or not by a linear program, and show that subset the dual variables correspond to a linear assessment policy which their setting, defining a linear program to characterize whether an effort profile e; is dominated or not. They then show that if an effort profile is not dominated, the dual variables of their linear program correspond to linear assessment rule which can incentivize it. While the proof idea is similar, their results do not extend to setting because for every time-step to ensure that the budget constraint always satisfied. We show that by examining the complementary slackness condition, we can upper-bound the gradient of the agent's cumulative score with respect to a subset of the dual variables {Ar)==1 (where each upper bound depends on the "extra" term "t introduced by the linear budget constraint for that time-step). Finally, we show that when an effort policy is not dominated, all of these bounds hold with equality and, because of this, the subset of dual variables {x12 satisfy the definition of linear assessment policy which can incentivize the effort policy (er)=11
incentivize it. Kleinberg and Raghavan present similar proof for
linear program must include an additional constraint
4 Equilibrium computation for linear effort conversions
While the optimization in Proposition 3.1 is nonconvex in general, we provide polynomial-time algorithms for settings in which the agent's effort conversion function can reasonably be viewed as being linear, i.e. ow = W, where W E Raxd is the agent's effort conversion matrix. Each component wij of W is nonnegative term which represents how much an increase in observable

---

feature i one unit of effort in action ý translates to. While this assumption may not be realistic in some settings, it may work well for others and is a common assumption the strategic classification literature (e.g., [42, 15, 4J).
Overview of our solution. Under settings in which the effort conversion function is linear, can rewrite the game's Stackelberg Equilibrium in a simplified form (Proposition 4.1). Under this formulation, the agent's optimal effort policy can be computed by solving a sequence of linear programs, but computing the principal's optimal assessment policy is a nonconvex optimization problem. However, when we write the principal's objective in terms of the agent's 's efforts (incentivized by the principal's 's policy), the function becomes convex. Given this observation, we design an algorithm to optimize the principal's objective over the the set of incentivizable effort profiles (instead of over the principal's 's policy space). To perform the optimization via convex optimization methods, we first establish that the set of effort profiles is convex and provide membership oracle that determines if an effort profile belongs to this set. Given the membership oracle, we leverage the convex optimization method in Kalai and Vempala [28] to find the (approximate) optimal incentivizable effort profile with high probability. Given this effort policy, we can use the dual of our membership oracle to recover a linear assessment policy which can incentivize it. We begin by characterizing the Stackelberg Equilibrium in this setting.
Proposition 4.1 (Stackelberg Equilibrium), Suppose the agent's 's effort conversion function ow is linear. The Stackelberg equilibrium of the stateful strategic regression game, (10)) (e))==)) can then be specified as follows:
T-- Σ
VI: e arg max
o W
04::
WΩ e,
T
T- o Σ o WΩ
(0) |T arg max B1 By
arg max O2
er
Proof Sketch. We show that under linear effort conversion functions, the agent's best response problem is linearly seperable across time, and the agent's effort profile at each time is given by linear program. We then plug in each expression for the agent's optimal effort profile at time / into the principal's 's optimization problem to obtain our final result. See Appendix 1) for the full proof.
Given the principal's 's assessment policy (0:) it possible to recover the agent's optimal effort policy by solving the linear program for e, at each time t. On the other hand, recovering the principal's optimal assessment policy is more difficult. The principal's optimal policy takes the form of multiobjective bilevel optimization problem, a class of problems which are Hard in general [10]. However, we are able to exploit the following proposition to give polynomial -immal--imeeeeeeee algorithm for recovering the principal's 's optimal assessment policy.
Proposition 4.2. The set of incentivizable effort policies is convex if the effort conversion function linear.
Proof Sketch. In order to show that the set of incentivizable effort policies is convex, we assume that is not and proceed via proof by contradiction. We construct an effort policy { by taking the element-wise average of two incentivizable effort policies {x,) and {y: [y:) and assume it not incentivizable. Since {z; _ is not incentivizable, there exists some effort policy (
which dominates it. We show that if this is the case, then (57 [CT)T, must dominate either
{ (x; (x))=1 or (yr)? This a contradiction, since both are incentivizable. See Appendix E.1 for the full proof.
Note that the linear program from Theorem 3.4 can serve as a membership oracle for this set. To see this, note that given an effort policy {e:) the LP returns value of T if and only if ) is incentivizable. We now show how to leverage this membership oracle to recover the principal's optimal assessment policy in polynomial time.
Define CvxDracle(f. M, R, r. Ctp, e, 5) to be the membership oracle method of Kalai and Vempala (28), which, for convex set C, takes a linear function over the convex set C, membership oracle M to the convex set C. initial point on inside of C, radius R of a ball containing C, and a radius r of ball contained in C and centered at Oig as input, and returns member of the convex set which minimizes f up to some (c) term, with probability at least 1 - 5. We now present an informal version of their main theorem, followed by our algorithm.
7

---

Theorem 4.3 (Main Theorem of Kalai and Vempala [28] (Informal)). For any convex set C E R", given a membership oracle M, starting point ag. upper bound R on the radius of the ball containing C, and lower bound on the radius of the ball containing C, the algorithm of Kalai and Vempala [28) returns a point af such that f(az) min f(a") S with probability
6, where the number of iterations is I = O /n log( Rn/r(d)), and O(n*) calls to the membership oracle are made at each iteration.
Algorithm I: Assessment Policy Recovery
Result:
An assessment policy (0;
Define C to be the set of incentivizable effort policies;
Let [(fe:)=m) = - AE= ed] where {ex) 1 is an incentivizable effort policy;
Define MM to he the linear program from Theorem 3.4; Fix arbitrary assessment policy (0r,o) Solve for initial incentivizable effort policy (er, /er. as in Proposition
(r..)/m..
Set R 202 1)+13'
T(d-1)
{e:)==1 CvxOracle(fr M, R, (er,o)=2,,,,)
Set the primal variables of M equal to {ei) and solve a system of linear equations to recover the dual variables {0;
Theorem 4.4 (Optimal Assessment Policy). Let C be the set of incentivizable effort policies. Assum- ing that C contains a ball with radius at least centered at {c,,u) the assessment policy {0) IT recovered by Algorithm I is an e-optimal assessment policy, with probability at least 1 ò.
Before proceeding the proof sketch for Theorem 4.4, we remark that the assumption of C containing ball of radius is commonplace within the membership oracle-based convex optimization literature, both in theory [20, 28], and practice (e.g.. [5]. The assumption implics that if it is possible to incentivize agent to play effort policy {er,o) ) then it is also possible to incentivize them to play other effort policies within small margin of ()
Proof Sketch. The proof consists of several steps. First, note that the agent's effort policy consists of T d-dimensional probability simplexes, which is (dd (dddd)--dmmee dimeessioo simplex. The circumradius (i.e.,
T(d-1) the minimum radius of a ball containing the [ - 1)- -iimenssollll simplex) is v (d-(2)))-z
Next. we observe that we can use the linear program defined in the proof of Theorem 3.4 as membership oracle the set of incentivizable effort policies. Finally, we observe that the function we are trying to optimize is linear and that it is possible to identify an initial point {er.o)?=1 within the convex set C. We can then use a membership oracle-based convex optimization procedure such as Kalai and Vempala [28] to recover the incentivizable effort policy which is most desirable to the polynomial time. Given this effort policy,
principal (up to some (c) term, with high probability) we can use the complementary slackness conditions of our membership oracle linear program to recover the corresponding dual variables, a subset of which will correspond to an assessment policy which can incentivize the agent to play this effort policy. See Appendix E for full details.
The existence of such membership oracle- method shows that tractable algorithms exist to recover the principal's 's optimal assessment policy, and heuristics need not be resorted to under large class of settings, despite the bilevel multiobjective optimization problem which must be solved.
4.1 How many rounds are necessary to implement desired effort profile?
In the classroom example, we saw that a wider range of effort profiles can be incentivized by extending the fixed budget setting of Kleinberg and Raghavan to multiple time-steps. But how long does the time horizon have to be in order to incentivize a desired effort profile if the principal can pick the time horizon? Additionally, what conditions are sufficient for an effort profile to be incentivizable? We formalize the notion of (T, >--mmleementability in the linear effort conversion function setting with these questions in mind.
Definition 4.5 ((T, f)- Implementaaiiltty). A basis vector b, is said be (T, implemeetttee if rational agent can be motivated to spend their entire effort budget on b, for all times 1 S tt < t.

---

Figure 2: Contribution of studying vs T t. We plot Ωg (x-axis) T (y-axis) for our classroom example in Appendix A. Note that Sg is assumed to be 1 in the appendix. Lighter colors indicate settings in which the student has more incentive to cheat. As long as Ωg > O, there exists some time horizon under which the student incentivized to study. As Ug increases, the number of extra time-steps required incentivize studying decreases.
0
2
8 10 12 Contribution Studying
max Wmyl and Wms - Dec > 0, then by is (By:Wog Ree Wmo)
Theorem 4.6. T 2 max, minm
(I, -l-immlemeetable.
See Appendix F for the full derivation. This bound shows that any basis vector is incentivizable it accumulates faster than other effort profiles. In the worst case, the space of incentivizable effort profiles is the same as Kleinberg and Raghavan (just set T 1). However, if an effort component accumlates faster than other effort components, there will always exist time horizon T for which it can be incentivized. In our classroom example, as long as the student retains some knowledge from studying, there always will exist time horizon for which it is possible to incentivize the student to study (see Figure 2). Note that while the principal may be interested in incentivizing more than just basis vectors, there does not appear to be closed-form lower bound for T for non-basis effort profiles.
5 Concluding discussion
We proposed simple and tractable model in which principal assesses agent over series of timesteps to steer him in the direction of investment in desirable but unobservable types of activities. Our work addresses three crucial gaps in the existing literature, stemming from restricted focus (1) short-term interactions, (2) with myopic agents, (3) ignoring the role of carlier effort investments (i.e., the state) on future rewards. We observe that within our stateful strategic regression setting, the principal is capable of implementing a more expansive space of average effort investments. Our main results consisted of algorithms for computing the equilibrium of the principal-agee interactions, and characterizing several interesting properties of the equilibrium. There are several natural extensions and directions for future work suggested by our basic model and findings.
Alternative cost functions. Following Kleinberg and Raghavan [30], we assumed throughout our analysis that the agent has fixed effort hudget in each round. One natural extension of our model is to explore alternative cost formulations for the agent. In Appendix G, we provide the analysis for one natural alternative-that is, cost term which scales quadratically with the total effort expended. Our findings generally remain unaltered. The main qualitative difference between the equilibria of the fixed budget vs. quadratic cost is the following: While under the fixed budget setting, the agent's optimal effort policy is sequence of basis vectors and the principal's 's optimal assessment policy generally is not, we find that the opposite is true under the quadratic cost setting. We believe the case-study of quadratic costs provides reassuring evidence for the robustness of our results to the choice of the cost function, however, we leave more systematic study of equilibrium sensitivity to agent cost function as an interesting direction for future work.
Bounded rationality. While we assumed the principal and the agent in our model respond rationally and optimally to each other's 's strategies, in real-world scenarios, people and institutions are often not fully rational. Therefore, it would be interesting to consider models where our players' rationality is bounded, e.g., by designing assessment policies that are robust to suboptimal effort policies and are capable of implementing desired investments despite the agent's bounded rationality.
Unknown model parameters & learning. We assumed the fundamental parameters of our model (c.g., ow,
w,W. Ω, A and T) are public knowledge. It would be interesting to extend our work to settings

---

where not all these parameters are known. Can we design learning algorithms that allow the players learn their optimal policy over time they interact with their counterparts?
Other simplifying assumptions. Finally, we made several simplifying assumptions to gain the insights offered by our analysis. In particular, our algorithms for recovering the optimal principal and agent policies relied on the agent having a linear effort conversion function. It would be interesting explore algorithms which work for wider range of effort conversion functions. Additionally, we assumed that effort expended towards some action was time-independent (e.g., one hour spent studying today equivalent to one hour spent studying yesterday). would be interesting to relax this assumption and study settings in which the accumulation of effort is subjected to discount factor.
Acknowledgements
This research is supported in part by the NSF FAI Award #1939606. The authors would like to thank Anupam Gupta and Gabriele Farina for helpful discussions about convex optimization techniques, and Gokul Swany for helpful comments and suggestions.
10

---

References
[1] A. Agarwal, A. Beygelzimer. M. Dudik, J. Langford, and H. M. Wallach. A reductions approach to fair classification. In J. G. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 60-69 PMLR, 2018. URL htt.ttp:: /twp://e//s.cccnggs....m mlr press/v80/ agarwal18a. html.
[2] S. Ahmadi, H. Beyhaghi, A. Blum, and K. Naggita. The strategic perceptron. In P. Biró, S. Chawla, and F. Echenique, editors, EC '21: The 22nd ACM Conference on Economics and Computcation, Budapest, Hungary, July 18-23, 2021, pages 6-25. ACM, 2021. doi: 10. 3465456.3467629 URL https: /tt.://ooiiooo org/10 11 1145/3465455 3467629.
[3] J. Angwin, J. Larson. S. Mattu, and L. Kirchner. Machine bias. Propublica, 2016. URL https://www.propublii.. httpbb/iii...rggrrreeeeeeeeee org/serres/macciiiee. bias.
[4] Y. Bechavod, K. Ligett, Z. S. Wu, and J. Ziani. Gaming helps! learning from strategic interac- tions in natural dynamics. In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 1234-1242. PMLR, html.
2021. URL http: http://prroceedings .ml..
[5] A. Blum, N. Haghtalab, and A. D. Procaccia. Learning optimal commitment to overcome insecurity. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 1826-1834, 2014. URL https https: http:///ooeeeenn..eeee/e www.ggg..neriipe www.nnurriscoo ctteriis.ccpaaapeee pttp//apppre/////////// cc 0004432277138ff11cc777333333
aaroSeeaf--bbtract..... Abstract
[6] M. Brückner and T. Scheffer. Stackelberg games for adversarial prediction problems. In C. Apté, J. Ghosh, and P. Smyth, editors, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego CA, USA, August 21-24, 2011, pages 547-555. ACM, 2011. doi: 10. 4445/2224408.22044999 URL https://ddi..orrr 10.1145/2020400 2020495.
[7] G. Carroll. Robustness and linear contracts. American Economic Review, 105(2):536-63, February 2015. doi: 1215/ URL https:///wwit httt:::/www.awwee..rrr.... www.eb. wttpseeb.brg/rrttlllesssssse id=10. 1257 /aer. 20131159.
[8] L. E. Celis, L. Huang. V. Keswani, and N. K. Vishnoi. Classification with fairness constraints: A meta-algorithm with provable guarantees. In danah boyd and J. H. Morgenstern, editors, Proceedings of the Conference on Fairness, Accountabiliry, and Transparency, FAT* 2019, Atlanta, GA, USA, January 29-31, 2019, pages 319-328. ACM, 2019. doi: 10. 10.1145/3287560. 3287586. URL htttps://dlt orrg 10. / 3287586.
[9] Y. Chen, C. Podimata, A. D. Procaccia, and N. Shah. Strategyproof linear regression in high dimensions: an overview. SIGecom Exch., 17(1)554-60, 2018. doi: 10. 10.1 10.1145//3310333333100
URL https: //dii. org/ 10. 10.11/1333303/33 3331038.
[10] B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Ann. Oper. Res.,
153(1))235-256, 2007. doi: 10. 00110077/1104990077-117622 URL httpts/////doi http://di..oog/..11000000/// 610479-007-0176-
[11) S. Corbett-Davies and S. Goel. The measure and mismeasure of fairness: A critical review of fair machine learning, CoRR, abs/1 808.00023. 2018 URL http: http::////xxvve//e www.aaiwww.waaaaaaaaaaaaoaeeeeee wtwgg///////////// 00023.
[12] R. Cummings, S. Ioannidis, and K. Ligett. Truthful linear regression. In P. Grünwald, E. Hazan, and S. Kale, editors, Proceedings The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 448- 483. JMLR.org, 2015. URL http: http:/poooeednnn..ec mlr www.ppressvveee
Cummi ingsi.innii..... html.
[13] N. N. Dalvi, P. M. Domingos, Mausam, S. K. Sanghai, and D. Verma. Adversarial classification. In W. Kim, R. Kohavi, J. Gehrke, and W. DuMouchel, editors, Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, Washinglon, USA, Augus! 22-25, 2004, pages 99-108. ACM, 2004. doi: 10. 15111//144405 1014066. URL https: ://ooi org/111// 10. 1145//11100/...... 1014066.
11

---

[14] O. Dekel, F. A. Fischer, and A. D. Procaccia. Incentive compatible regression learning. J. Comput. Syst. Sci., 76(8):759-777, 2010. doi: 10.1016ffjess.2010.....0 URL https: //doi.org//a
1016/j jjcsss 2010.03.00.0.0000000000000...... 003.
[15] J. Dong, A. Roth, Z. Schutzman, B. Waggoner, and Z. S. Wu. Strategic classification from revealed preferences. É. Tardos, E. Elkind, and R. Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, .Y,, USA, June 18-22, 2018, pages 53-70. ACM, 2018. doi: 10. 10.1145/221916632211999 URL pattps://dos org/10../// 1145/ 3219166. 3211199..
[16] M. Donini, L. Oneto, S. Ben-David, J. Shawe-Taylor and M. Pontil. Empirical risk minimization under fairness constraints. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Gameett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages cc/ cc/paper/
2018. URL https: httpt:tt//oceeeeeeeeeee /ttpc//eeoeeeeenss///eeeee/essee neurips. Abstrracf.bbarttt..oaaaaaaaaaa.e html.
[17] Dütting, Roughgarden, and I. Talgam-Cohen. Simple versus optimal contracts. In A. Karlin, N. Immorlica, and R. Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 369-387. ACM, 2019. doi: 10.1145/332852..3333 23.399991... URL https: http//dii.o// org/ 10. 11.1111///30 33285262226666 3329591.
[18] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. S. Zemel. Fairness through awareness.
In S. Goldwasser, editor, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, Jamuary 8- 10, 2012, pages 214 214-226. ACM, 2012. doi: 10.1145/2090236.20900 URL https://doi. org/10. 10. 1145/2090236. 2090255.
[19] A. Frankel and N. Kartik. Improving Information from Manipulable Data. Journal of the
European Economic Association, 06 2021. ISSN 1542-4766. doi: 10.1093/jeea/jyab01,, URL
https://6oi.orrg/00 org/ 1ttp://0000///eeea///aa1111. jvab017.
[20] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimiza- tion, volume 2 of Algorithms and Combinatorics. Springer, 1988. ISBN 977-3-642-998833 doi:
111007/978-33662-978888 1-4. URL https://doi.ciooo org/10 10. 900007797833-666 642-97881-4.
[21] M. Hardt, N. Megiddo, C. H. Papadimitriou, and M. Wootters. Strategic classification. In M. Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical
Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 111-122. ACM, 2016. URL https: .rrila.rg//g// /0/ 1145/28407288.... 28000447707....773.... 2840730.
doi: 10.1 011144447788.84000000
[22] M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learn- ing. In D. D. Lee, M. Sugiyama. U. von Luxburg, I. Guyon, and R. Garnett, ed- itors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3315-3323, 2016. URL. https::///// httttp::/pproceedingg ca2682267 wbw.:3eddeeef1119ef2e.o
petpriis.cc/pppe/2211111 Abstract html.
[23] H. Heidari, V. Nanda, and K. P. Gummadi. On the long-term impact of algorithmic decision policies: Effort unfairness and feature segregation through social learning. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2079, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages mlr. wwwpppperse//eee hwa/0//heidrrii wtw.ddari19a..aaaa html.
PMLR, 2019. URL http: / prtp///eeeeen....
[24] B. Holmstrom and P. Milgrom. Aggregation and linearity in the provision of intertemporal incentives. Econometrica, 55(2):303-328, 1987. ISSN 00129682, 14680262. URL http: / //www. www..jstor..... wtw.jjttoroo//sabbbbla. http:///ttaeeee/1333....
[25] L. Hu and Y. Chen. A short-term intervention for long-term faimess in the labor market. In Champin, F. Gandon, M. Lalmas, and G. Ipeirotis, editors, Proceedings of the 2018 World Wide Web Conference World Wide Web. WWW 2018, Lyon, France, April 23-27, 2018, pages htLptts::/ //doii:://///.// www.oo.///.. 1145/
1399.1398.40 ACM, 2018, doi: 3178876.3186044.
[26] I. Hu, N. Immorlica, and J. W. Vaughan. The disparate effects of strategic manipulation. In danah boyd and H. Morgenstern, editors, Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* 2019, Atlanta, GA, USA, January 29-31, 2019, pages
12

---

259-268 ACM, 2019. doi: 10. 10.11445/228755032227999 URL https://doi. org. /0/ 1145/ 3287560 . 3287597.
[27] Jagtiani and C. Lemieux. The roles of alternative data and machine learning in fintech lending: Evidence from the lendingelub consumer platform. Financial Management, (5(4))1009-1022 2019, doi: https://doi.org/110 doi/abs/ 10. 1111/fima. 12295.
1/fima.12299 URL httptt::://olllllellbbarrrrr wiley com/
[28] A. T. Kalai and S. S. Vempala. Simulated annealing for convex optimizatiinnn Math. Oper. Res., 3 31(2):533 2006. doi: 10.1287/moor. 1060.000.06000091.. URL https://dol: org/10..//.. 1287/
moor 10.10000..00 01944.
[29] Kannan, Roth, and J. Ziani. Downstream effects of affirmative action. In danah boyd and J. H. Morgenstern, editors, Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* 2019, Atlanta, GA, USA, January 29-31, 2019, pages 240-248. ACM, 2019. doi: 10.1145/3287560.33555 33877778. URL https: //tp:::///oiiooo org/oo///// 10. 1145/ 1144//2287666 32875600 3287578.
[30] M. Kleinberg and M. Raghavan. How do classifiers induce agents to invest effort strategically? ACM Trans. Economics and Comput., 8(4):19:1119:23, 2020. doi: 10.1145/3417742. URL
https:/ org/10, ///00.0100 1145/3417744..
[31] J. M. Kleinberg, S. Mullainathan, and M. Raghavan. Inherent trade-offs in the fair determination of risk scores. In C. H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of L/PIcs, pages 43:1-43:23, Schloss Dagstuhl Leibnie--entrrreeeeee für Informatik, 2017. doi: 10.4230/LIPIcs. ITCS 2017.40...43 URL htt.h:tt///eet //dp:.///oii.. org/10. http//...2330//00 4230/LIPIcs. ITCS 2017. .43.
[32] D. Kučak, V. Juričić, and G. Dambić. Machine learning in education a survey of current research trends. Anmals of DAAAM & Proceedings, 29:406-411 410, 2018. doi: 10.2507/29th. daaam. Silam.proceedings0055
[33] J.-J. Laffont and D. Martimort. The Theory of Incentives: The Principal-Agent Model. Princeton University Press, 2009. ISBN 9781 478149092 doi:
URL
https://doi. ot0/ 1515/9781400029453.
[34] L. T. Liu, S. Dean, Rolf, M. Simchowitz, and M. Hardt. Delayed impact of fair machine learning. In S. Kraus, editor, Proceedings of the Twenty-Eights International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 6196-6200. ijcai.org, 2019. doi: (0024963/jjaai.2119/66 URL htl.htts::/eee //doi. orgg /00. 24963/4933333 ijcai. 2019/862.
[35] Miller, S. Milli, and M. Hardt. Strategic classification is causal modeling in disguise. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6917- 6926. PMLR, 2020. URL http: htttp://proceedinggs mlr. wall..pees/vviie catess/vv19/m/iii/ htmm/mmllee22011 html.. html..
[36] S. Milli, J. Miller, A. D. Dragan, and M. Hardt. The social cost of strategic classification. In danah boyd and J. H. Morgenstern, editors, Proceedings of the Conference on Fairness, Accountabiliry, and Transparency, FAT 2019, Atlanta, GA, USA, January 29-31, 2019, pages 3287560 32777766..
230-239. ACM, 2019. doi: 10.1145/32855603223333 URL https://doi. ieriii.org//000 /0. 1145/
[37] H. Mouzannar, M. Ohannessian, and N. Srebro. From fair decision making to social equality. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259-368. ACM, 2019.
[38] C. Perdomo, T. Zrnic, C. Mendler-Dünnee and M. Hardt. Performative prediction. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7599- 7609. PMLR, 2020. URL. http:///// http///pooeeeenn..////// mlr. www........................w.... ppwpss/v19//e/eeeee fteess/v119pperoom22ee peroomo20d.......m html.
[39] A. Roth, J. Ullman, and Z. S. Wu. Watch and learn: Optimizing from revealed preferences feedback. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. STOC 16. page 949-962, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 978 9781450341325. doi: 10. 00.1145/2895518828977777 2897779. 2897518. 2897579.
URL https:://// :tttpp:://di... //ooi./oo...o/ (ecoi.org/// org/10. 1145/
13

---

[40] A. Roth, A. Slivkins. J. Ullman, and Z. S. Wu. Multidimensional dynamic pricing for welfare maximization. ACM Trans. Econ. Comput., 8(1), Apr. 2020. ISSN 2167-8375. doi: 10.1145/
3381527. URL htw.h:ttp:::t/ect //doi. org/10 1145/3381527,
[41] J. Sanchez-Monederoo, L.. Dencik, and L. Edwards. What does it mean to 'solve' the problem of discrimination in hiring?: social, technical and legal perspectives from the UK automated hiring systems. In M. Hildebrandt, C. Castillo, L. E. Celis, S. Ruggieri, L. Taylor, and G. ZannirrFortuuna, editors, FAT* '20: Conference Fairness, Accountability, and Transparency, Barcelona, Spain, January 27-30, 2020, pages 458-468. ACM, 2020. doi: 10. 10.1145/3351095. 3372849. URL https://doo. org/ 10. 1145/3351095..... 3372849
[42] Y. Shavit, B. L.. Edelman, and B. Axelrod. Causal strategie linear regression. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 8676-8686. PMLR, http::////cceeegg...mmm mlr, hatsss//v1//saaviiii html..
2020. URL http: /
[43] L. Sweeney. Discrimination in online ad delivery. Commun. ACM, 56(5):44-54, 2013, doi: 10. 011114444976.24479999999 URL https: / http:///oooorr/./////// 1e1111144410 2447996..4449990.
[44] B. Ustun, A. Spangher, and Y. Liu. Actionable recourse in linear classification. In danah boyd and H. Morgenstern, editors, Proceedings of the Conference on Fairness, Accountability, and Trunsparency, FAT 2019, Atlania, GA, USA, January 29-31, 2019, pages 10-19, ACM, 2019. doi: 10.1145/3287560.3 3328756..... URL https: http///dii.o org/ 1411/332222 44444/220006.. 3287566.
[45] H. Zhang and V. Conitzer. Incentive-aware PAC learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Thing Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 5797-5804. AAAI Press, 2021. URL pattps://oj/ aaai aaai.org/ ////nddxxxx php/ AAAI/ httaa//rrrriieeeee//////...
14


Reviews:
[{"review_id": "pP6c6PrOnlr", "reviewer": "Reviewer_xFkk", "summary": "The paper discusses the problem of stateful strategic regression, where the basic idea is to model the interaction between a principal and a strategic agent over multiple time steps. Specifically, the principal announces a sequence of assessment policies, and the agent invests effort to play a best response to this sequence, defined as the effort policy that maximizes the cumulative score the agent receives. An important aspect of the model is that the agent’s effort accumulates over time through an “internal state”. For example, studying for an exam today can help a student’s performance in the following days.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I really like the motivation and the idea of studying long-term interactions between the principal and the agent. I particularly like the idea of introducing the agent’s internal state which seems like the right way to capture the compounding nature of efforts. The paper is also well-written overall, with a couple of exceptions where I felt that some claims were a bit too informal (I’m providing specific comments below, together with different minor remarks). The main downside for me is that it’s perhaps unclear what the formal difference is between the setup considered in this paper and a one-shot setting where we increase the expressiveness (e.g., dimension) of the scoring functions and the agent efforts. In particular, the setup can still be thought of as consisting of a single time step because all assessment rules are announced at once, and the agent optimizes their response to all these rules at once. So one can think of the sequence of assessment rules as one high-dimensional rule. Similarly, the sequence of efforts can be seen as as one complex action the agent takes. A more interesting setting might be to consider adaptively chosen assessment rules and agents that plan how to invest their efforts non-myopically despite adaptivity. Still, this paper is a good first step toward understanding strategic regression with a longer time horizon.\n\nIt would also be nice to give a bit more intuition for why the membership oracle method due to Lee et al. is the “right” approach. Since the principal’s objective is convex, the most natural approach would be to consider some projected-gradient-descent-like method. The Lee et al. algorithm only assumes an evaluation oracle for the objective, while in this paper the objective is explicit and one can even obtain gradients. So why is the very general and conservative model of Lee et al. the right one? Is it hard to project onto the set of incentivizable effort policies?\n\nThis could be a matter of taste, but I felt that a couple of statements were a bit too informal. I don’t doubt that they are true, it’s just that they are not really mathematical claims, but rather intuitive explanations of the underlying mathematical statement. For example, I would formalize the meaning of “wider range of effort policies” in Proposition 2.2 or “rational agents being motivated to spend their entire effort budget” in Definition 4.5. (Note also that incentivizable effort policies, used in Proposition 2.2, are defined only later.) Proposition 2.2 also comes without a proof which makes it even harder to recover the exact mathematical statement.\n\nSome other minor comments:\n1. Line 199 says “\\sigma_W(s_0) is analogous to o_0 in the single-shot setting”. This only seems to be true if \\sigma_W is linear (which is only assumed later on), that is o_1 = \\sigma_W(s_0 + e_1) = \\sigma_W(s_0) + \\sigma_W(e_1). It seems to me that the definition of o_1 in line 185 is not consistent with this general-t equation in line 199.\n2. In line 213, it’s not stated in which norm B is the budget.\n3. In the equation after line 227, you might want to say that you’re abusing notation by treating e_t as a function. Or you might want to separately define a function that goes from thetas to efforts. Also, I think in the argument it should say theta_1,…,theta_T, not theta_t,…,theta_T?\n4. Line 275 says linear twice, “under settings in which the linear effort conversion function is linear“.\n5. In Proposition 4.2, it’s not entirely obvious what it means for a set of *sequences* of vectors to be convex. You might want to add a definition.\n6. I had trouble understanding the paragraph that starts at line 310. First I was confused what the linear program from Theorem 3.4 even is. It seems to refer to the proof of the theorem, but just from the main body it’s unclear what LP returns T and why. Also there are a few typos in this paragraph - {e_t\\|, and there is an extra if in line 311 (I think it should be “given an effort policy” instead of “if given an effort policy”).\n7. Definition 3.3 (dominated effort policy) should be defined relative to a sequence of thetas, I think this should be clarified.\n8. Line 51, assume -> assumes.\n9. Line 55, proposed *by*.\n10. Line 107 should have a reference ([31]) after Lee et al. (since this is the first time this work is mentioned).\n11. In line 203, I’m not sure if there is a typo, but I find it strange how the equation begins with “=“.\n12. First equation after line 291, should the thetas be thetas* (i.e. the equilibrium thetas)?\n13. The concluding discussion section has a different title capitalization than the other sections (“Discussion” should be “discussion”).\n\n------------------------------------------------------------------------------------------------------------\n\nThank you for your response. After discussing the paper with the other reviewers I still think this paper makes a nice conceptual contribution and I'll keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed limitations and possible improvements of their work in a discussion section. I've included various suggestions as part of the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "hJBMGOvnAD", "reviewer": "Reviewer_bbo6", "summary": "This paper studies a theoretical model of a multi-round assessment game between a principal and an agent. This model is an extension of Kleinberg and Raghavan (2020) to the multi-time-step setting where the efforts of an agent can accumulate benefits from one time step to the next. It studies the equilibrium computation problem under simplifying linearity assumption. Its main finding is that in the multi-step case, the principal can incentivize a wider range of effort profiles than in the single time step case.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality:\nThis is an original extension of the model in Kleinberg and Raghavan (2020). The multi-time step case of the \"incentivizing effort\" problem has yet to be studied, to my knowledge.\n\nThe paper's discussion of related emphasizes that related work mostly consider short-term implications of strategic interactions, and that considering \"multiple rounds of interactions\" is a significant point of novelty/departure. I'm not sure that this is an accurate picture of the literature. For example, this paper does not cite and discuss an earlier work on \"long term strategic interactions between decision-makers and decision subjects\": Liu et al (2020) [\"The Disparate Equilibria of Algorithmic Decision Making when Individuals Invest Rationally.\"]. It also neglects to mention even earlier work in economics (e.g. Coate and Loury 1993, \"Will Affirmative Action Policies Eliminate Negative Stereotypes\") that have very much studied this exact topic. Instead of making an overly broad statement about the paper's novelty, I would suggest focusing on the paper's actual contributions, which is to illustrate the effects of *compounded effort* under a stateful model. I believe this is where the originality of the paper lies, and this should be reflected more accurately to the reader.\n\nQuality:\n\nThe paper is generally technically sound.\n\nHowever, there are some statements that I find misleading. For example, it claims in lines 111 to 114 that \"Crucially, perhaps our most significant finding is that with multiple rounds of assessments at her disposal, the principal is significantly more effective at incentivizing the agent to accumulate effort in her desired direction (as demonstrated in Figure 1 for a simple teacher-student example).\" Does this not depend on whether the desired direction of effort compounds according to the model? Conversely, if the model is such that the student gets better at \"copying answers\" over time, then the principal would find it even harder to incentivize studying.\n\nIn general, there should be more discussion of when this effort compounding might backfire. It's clear to me that there can be no free lunch in this scenario -- increasing the time horizon doesn't automatically lead to better outcomes. This is also not what the theorem statements are saying. Instead of making overly optimistic claims about how this helps the principal in the writing, the paper should be more explicit about the downsides, and about the necessary assumptions for gains.\n\nClarity: \n\nThis is a very well-written paper, in terms of overall clarity and organization.\n\nSignificance:\n\nThe idea of compounded effort is an interesting one. I see this as the main contribution of the paper, and think it is a good point to be made. Other claims about the field's \"restricted focus on short-term interactions and myopic agents\" are quite overstated. Re: myopic agents and statefulness, there are a number of papers on fair ML and MDPs, such as Algorithms for Fairness in Sequential Decision Making by Min et al (2021). The current paper should do some comparison to show how they are improving on previous work. See also the references listed in the Quality section.\n\nThe actual theoretical results are not remarkable, mostly following from Kleinberg and Raghavan (2020) with some additional elementary arguments (such as linear separability), but are stated cleanly, with helpful exposition of the proof ideas.\n\nRe: \"when this effort compounding might backfire\", I think the paper's contributions are ambivalent. Unless there is some intrinsic connection between what actions are desirable and what actions compound, basically, the theory still suggests that anything could happen. This is a fine contribution, just perhaps not as important or impactful as it claims.\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I suggest a more extensive review of related work, and not over-stating the claims (in the writing) that compounding helps the principal incentivize better actions. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "VkgVXuXewq", "reviewer": "Reviewer_rp4a", "summary": "The paper generalizes an existing problem into a multi-step one. The original problem proposed by Kleinberg and Raghavan is formulated as a Stackelberg game played between a principal and an agent. The principal wants the agent to invest efforts in some given acitivities and uses an assessment policy to score the agent's performance. Once the assessment rule is announced, the agent best responds to the rule by choosing the optimal amount of effort to invest on each activity, aiming to maximize the score it receives. The goal of is to find an assessment rule that will incentivize the agent to invest more efforts. In this paper, the agent's effort investment is a multi-step process. Effort investment in a step will have consequences to the scores in subsequent steps. Hence, both the agent and the principal adopt a long-term vision over their strategies. The paper presented an efficient algorithm to compute the best assessment rule for the principal and also analyzed the time it needs to incentivize a desired effort profile.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is built on an existing model, which is a simple and natural one for the studied scenario. The extension to the multi-step setting is also realistic and well-motivated. The paper is mostly clear.\n\nThe paper showcases a novel algorithm for computing the optimal assessment policy for the principal. The algorithm is tailored to the specific problem setting though.\n\nSome detailed comments:\n\n- The assumption that the amount of effort rolls over to the next step is subject to a transformation Omega looks reasonable at first glance, but from the current definition it looks like this transformation is applied only once to each e_i in the entire process, instead of once every step. Is such a formulation more suitable in some applications? And is it crucial for the main results?\n\n- The definition of dominated effort policy (Definition 3.3) reads a bit loose. Is the notion of dominated defined for a pair of effort policies or only for the one that is dominated? And does the condition need to hold for ALL possible assessment policies of the principal, or for some? It looks more correct to me to define this notion as follows: \n\nAn effort policy is dominated if it is worse than some other effort policy no matter what assessment policy the principal uses.\n\nThe way Theorem 3.4 is stated also raises the same question. In addition, I don't understand why in Definition 3.3 you need the requirement that the other policy that dominates this one should not spend full effort. I don't find this sufficiently explained in the paper.\n\n- Maybe it's better to point out that if there is a tie, the agent will choose a best-response that maximizes the principal's objective, as is implicitly defined by the bilevel optimization problem. \n\n- Section 4.1 needs more details. It's unclear why consideration of implementable vectors is restricted to basis vectors. I'd suggest that the authors expand this section. \n\n- At Line 181, Page 5, it says that e_t is a function of the assessment policy. This might be confusing as later it is defined that e_1 is a real-valued vector. \n\n- A typo on Page 7 (Line 311)? {e_t} ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't find any discussion about negative social impacts in the paper. One possible nagative impact the authors could discuss about is that their algorithms might be used by an unethical principal to exploit the agent. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "D93eB-3vEXJ", "reviewer": "Reviewer_TnTg", "summary": "The paper studies the problem of strategic regression when the designer’s goal is to incentivize the agents’ effort in the long term. The model follows the one in [Kleinberg and Raghavan, 2020] but considers multiple time steps during which an agent’s effort can accumulate over time in the form of an internal state. The paper characterizes and computes the Stackelberg equilibrium. They also make the following observations: (1) the class of linear policies is as strong as the larger class of monotonic policies; (2) the multi-step policies are more effective than the one-step policies.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The idea that the designer can use multi-step policies is good, and the observation that multi-step policies can be more effective is interesting. But the technical contribution compared to prior work is not sufficient for NeurIPS. \n\nThe word \"interaction\" used in the statement \"we investigate interactions spanning multiple time steps\" is misleading. If I understand correctly, by the definition of the Stackelberg equilibrium (Proposition 3.1), there’s no real multi-round interaction between the two sides. The designer posts the full sequence of policies at the beginning and cannot decide the policy based on the agent’s observable features in the previous rounds. As a result, the problem is basically a single-step problem with more variables and slightly different budget constraints, which makes the underlying mathematical problem mostly the same as the one in [Kleinberg and Raghavan, 2020]. (If I understand correctly, the only difference is that we have a budget constraint for each of the rounds here.) \n\nThe main technical contribution is Theorem 3.4, which proves that the class of linear policies is as strong as the class of monotonic policies. But the main technique used in the proof is just the duality approach in [Kleinberg and Raghavan, 2020]. Though the problem is not entirely the same, the contribution is not strong enough. Proposition 4.1 does not fully characterize the equilibrium, but only shows that the agent’s best response problem is linearly separable, which is not very insightful. Proposition 4.2 is also quite simple and the proposed algorithm is the standard algorithm for solving convex programs with membership oracles. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is broad agreement among the reviewers on what the paper contributes, but the reviewers evaluate it differently, with one quite strongly in favor and the others more on the fence but not opposed to accepting; part of this is how to value the conceptual aspect of the paper which seems to be its main strength.  I'd recommend a weak accept for this one.  There are some specific comments the authors need to address, and generally we encourage them to be open and transparent, in particular highlighting and explaining the assumption that socially undesirable efforts don't accumulate.
Decision: Accept (Poster)