Policy Learning with Competing Agents

abstractDecision \begingroup \footnote{Draft version: \ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \ \number \year. RS is supported by a NSF GRFP under grant DGE-1656518, Stanford Data Science Fellowship, and by NSF grant SES-2242876. Code available at \url{https://github.com/roshni714/policy-learning-competing-agents}.} \addtocounter{footnote}{-1} \endgroup makers often aim to learn a treatment assignment policy under a capacity constraint on the number of agents that they can treat. When agents can respond strategically to such policies, competition arises, complicating estimation of the optimal policy. In this paper, we study capacity-constrained treatment assignment in the presence of such interference. We consider a dynamic model where the decision maker allocates treatments at each time step and heterogeneous agents myopically best respond to the previous treatment assignment policy. When the number of agents is large but finite, we show that the threshold for receiving treatment under a given policy converges to the policy's mean-field equilibrium threshold. Based on this result, we develop a consistent estimator for the policy gradient. In a semi-synthetic experiment with data from the National Education Longitudinal Study of 1988, we demonstrate that this estimator can be used for learning capacity-constrained policies in the presence of strategic behavior.

section{Introduction} Decision makers often aim to learn policies for assigning treatments to human agents under capacity constraints athey2021policy, bhattacharya2012inferring, kitagawa2018should, manski2004statistical. These policies map an agent's observed characteristics to a treatment assignment. For example, bhattacharya2012inferring learn a policy for allocating anti-malaria bed net subsidies to households in Kenya, where only a fraction of the population can receive the subsidy. To enforce the capacity constraint, they use a selection criterion, such as a machine learning model, to score households and assign the treatment to households that score above a threshold, given by a quantile of the score distribution. When the decision maker has a capacity constraint, an agent's treatment assignment depends on how their score ranks relative to others. In policy learning, practitioners often assume that the data used for treatment choice is exogenous to the treatment assignment policy. Such an assumption is plausible if the treatment assignment policy is unknown to human agents or knowledge of the policy is unlikely to affect the agents' observed characteristics. For example, in the social program studied by bhattacharya2012inferring, characteristics such as household wealth, household size, and whether or not the household has a child under the age of ten, are used to determine allocations; these attributes are unlikely to change even if households have knowledge of how the bed net subsidies are allocated. However, in many other applications, human agents may change their observed characteristics in response to the policy, violating the exogeneity assumption. For example, in college admissions, applicants, with knowledge that high test scores will improve their chances of admission, may enroll in test preparation services to improve their scores bound2009playing. In job hiring, candidates may join intensive bootcamps to improve their career prospects thayer2017barriers. A growing literature focuses on policy learning in the presence of strategic behavior bjorkegren2020manipulation, frankel2019improving, munro2020learning, but these works implicitly assume that the decision maker does not have a capacity constraint, which means an agent's treatment assignment only depends on their own strategic behavior, unaffected by the behavior of others in the population. In contrast, when agents are strategic and treatment assignment is capacity-constrained, an agent's treatment assignment depends on the behavior of others and competition for the treatment arises. In this work, we study the problem of capacity-constrained treatment assignment in the presence of strategic behavior. We frame the problem in a dynamic setting, where the decision maker assigns treatments at each time step. Suppose a decision maker deploys a fixed selection criterion for all time. At time step $t$, agents report their covariates with knowledge of the policy from time step $t-1$, where the policy depends on the fixed criterion and the threshold for receiving treatment at time step $t-1$. Then, the decision maker assigns treatments to agents who score above the appropriate quantile of the score distribution at time step $t$, satisfying the capacity constraint. As a result, the threshold for receiving treatment at time step $t$ depends on agents' strategic behavior. At an equilibrium induced by the criterion, the threshold for receiving treatment is fixed over time. The goal of the decision maker, and the main goal of this work, is to find a selection criterion that obtains high equilibrium policy value, which is the policy value obtained at the equilibrium induced by the selection criterion. The goal of maximizing the equilibrium policy value is motivated by prior works that estimate policy effects or treatment effects at equilibrium heckman1998general, munro2021treatment, wager2021experimenting. heckman1998general estimate the effect of a tuition subsidy program on college enrollment by accounting for the program's impact on the equilibrium college skill price. munro2021treatment estimate the effect of a binary intervention in a marketplace setting by accounting for the impact of the intervention on the resulting supply-demand equilibrium. wager2021experimenting estimate the effect of supply-side payments on a platform's utility in equilibrium. johari2022experimental use a structural model of a marketplace and its associated mean field limit to analyze how marketplace interference affects the performance of different experimental designs and estimators. In Section (ref), we outline a model for capacity-constrained treatment assignment in the presence of strategic behavior. We assume that agents are myopic, so the covariates they report to the decision maker at time step $t$ depend only on the state of the system in time step $t-1$. Also, as in the aggregative games literature acemoglu2010robust, acemoglu2015robust, corchon1994comparative, we assume that agents respond to an aggregate of other agents' actions. In particular, at time step $t$, agents will react to the threshold for receiving treatment from time step $t-1$, which is an aggregate of agents' strategic behavior from time step $t-1$. Finally, as in, e.g., frankel2019improving, frankel2019muddled, we assume that agents are heterogenous in their raw covariates (covariates prior to modification) and in their ability to deviate from their raw covariates in their reported covariates. In Section (ref), we give conditions on our model that guarantee existence and uniqueness of equilibria in the mean-field regime, the limiting regime where at each time step, an infinite number of agents are considered for the treatment. Furthermore, we show that under additional conditions, the mean-field equilibrium arises via fixed-point iteration. In Section (ref), we translate these results to the finite regime, where a finite number of agents, sampled i.i.d. at each time step, are considered for treatment. We show that as the number of agents grows large, the system converges to the equilibrium of the mean-field model in a stochastic version of fixed-point iteration. In Section (ref), we aim to learn the selection criterion that maximizes the equilibrium policy value. Adapting the approach of wager2021experimenting, we estimate the gradient of equilibrium policy value via a local experimentation scheme and apply gradient-based optimization to optimize the equilibrium policy value. In Section (ref), we demonstrate that this approach can be used to learn policies in presence of competition in a semi-synthetic experiment with data from the National Education Longitudinal Study of 1988 ingels1994national. \begin{subsection}{Related Work} The problem of learning optimal treatment assignment policies has received attention in econometrics, statistics, and computer science athey2021policy, bhattacharya2012inferring, kallus2021minimax, kitagawa2018should, manski2004statistical. Most related to our work, bhattacharya2012inferring study optimal capacity-constrained treatment assignment, where the decision maker can only allocate treatments to $1-q$ proportion of the population for $q \in (0, 1)$. They show that the welfare-maximizing assignment policy is a threshold rule on the agents' scores, where agents who score above $q$-th quantile of the score distribution are allocated treatment. Our work differs from bhattacharya2012inferring because we do not assume that the distribution of observed covariates is exogenous to the treatment assignment policy. Recent references that consider learning in the presence of strategic behavior include bjorkegren2020manipulation, frankel2019improving and munro2020learning. bjorkegren2020manipulation propose a structural model for manipulation and use data from a field experiment to estimate the optimal policy. frankel2019improving demonstrate that optimal predictors that account for strategic behavior will underweight manipulable data. munro2020learning studies the optimal unconstrained assignment of binary-valued treatments in the presence of strategic behavior, without parametric assumptions on agent behavior. The main difference between our work and these previous works is that we account for the equilibrium effect of strategic behavior that arises from competition. Our work is also related to strategic classification ahmadi2022classification, bruckner2012static, chen2020learning, Dalvi04adversarialclassification, dong2018strategic, hardt2016strategic, jagadeesan2021alternative, kleinberg2020classifiers, levanon2022generalized and performative prediction miller2021outside, perdomo2020performative. These works model the interaction between a predictor and its environment (strategic agents), and develop methods that are robust to the distribution shift induced by the predictor. However, a key distinction between our work and these references is that we optimize decisions by explicitly considering utility from treatment assignment with strategic agents, rather than optimizing a notion of classification or predictive accuracy. Furthermore, the classification and prediction setups implicitly assume that an agent's label does not depend on the behavior of others in the population, limiting the applicability of these methods to settings with spillovers induced by capacity constraints. To the best of our knowledge, liu2021strategic is the only existing work that studies capacity-constrained allocation in the presence of strategic behavior. liu2021strategic introduces the problem of strategic ranking, where agents' rewards depend on their ranks after investing effort in modifying their covariates. They consider a setting where agents are heterogenous in their raw covariates but homogenous in their ability to modify their covariates. Under these assumptions, the authors find that agents' post-effort ranking preserves their original ranking by raw covariates. However, the assumption of homogeneity in ability to modify covariates may not be credible in some applications; for example, in the context of college admissions, students with high socioeconomic status may be more readily able to improve their test scores by investing in tutoring services than students with low socioeconomic status. Our work differs from liu2021strategic because we allow agents to be heterogenous in both their raw covariates and ability to modify their reported covariates, which fundamentally alters the nature of the resulting policy learning problem. The problem of estimating the effect of an intervention in a marketplace setting is also relevant to our work. Marketplace interventions can impact the resulting supply-demand equilibrium, introducing interference and complicating estimation of the intervention's effect blake2014marketplace, heckman1998general, johari2022experimental. To estimate an intervention's effect without disturbing the market equilibrium, munro2021treatment, wager2021experimenting propose a local experimentation scheme, motivated by mean-field modeling. Methodologically, we adapt their mean-field modeling and estimation strategies to estimate the effect of a policy at its equilibrium threshold. Finally, our model draws on many concepts from game theory. Our assumption that agents are myopic, or will take decisions based on information from short time horizons, is a standard heuristic used in many previous works cournot2020researches, kandori1993learning, monderer1996fictitious. Our assumption that agents account for the behavior of others through an aggregate quantity of their actions is a paradigm borrowed from aggregative games acemoglu2010robust, acemoglu2015robust, corchon1994comparative. Most related to our work, acemoglu2015robust consider a dynamic setting where the market aggregate at time step $t$ is an aggregate function of all the agents' best responses from time step $t$, and an agent's best response at time step $t$ is selected from a constraint set determined by the market aggregate from time step $t-1$. Analogously, in our work, the “market aggregate" is the threshold for receiving treatment. The threshold for receiving treatment is a particular quantile of the agents' score, so we can view it as a function of agents' reported covariates (agents' best responses). Furthermore, the covariates that agents report in time step $t$ depend on the value of the market aggregate, or the threshold for receiving treatment, in time step $t-1$. \end{subsection} \begin{subsection}{Motivating Example} We consider college admissions as a running example. The agents are a population of students who are hetergeneous in their baseline test scores and grades and in their ability to invest effort to change them. The decision maker is a college with a fixed selection criterion for scoring students based on their test scores and grades and a capacity constraint that they can only accept $1-q$ proportion of the applicants where $q \in (0, 1)$. Each year $t$, the college scores students and accepts students who rank above the $q$-th quantile of the score distribution. In year $t$, students have knowledge of the criterion and the acceptance threshold from the previous year $t-1$. Some students may invest effort to improve their chances of admission by enrolling in test preparation services or taking more advanced classes to improve their chances of getting accepted bound2009playing,rosinger2021role. Finally, students report their post-effort test scores and grades to the college. To ensure the capacity constraint is satisfied, the college sets the acceptance threshold in year $t$ to the $q$-th quantile of the score distribution in year $t$. The acceptance threshold may oscillate from year to year until an equilibrium arises and the acceptance threshold is fixed over time. This example aims to capture the phenomenon that college admissions has become increasingly competitive since the 1980s; bound2009playing demonstrates that between 1986-2003, the 75th percentile math SAT score of accepted students at the top 20 public universities, top 20 private colleges, and top 20 liberal arts colleges, steadily trended upward. In our model, the equilibrium acceptance threshold depends on students' strategic behavior and the decision maker's capacity constraint and selection criterion. Different selection criteria may induce different equilibrium thresholds. The equilibrium acceptance threshold affects the value of the policy because it determines which students are accepted or rejected. A selection criterion that induces a high acceptance threshold may not necessarily yield high value for the college. \end{subsection}

section{Model} We define a dynamic model for capacity-constrained treatment assignment in the presence of strategic behavior and define the equilibrium policy value. We propose a model for agent behavior in terms of myopic utility maximization and provide conditions under which the resulting best response functions vary smoothly in problem parameters. \subsection{Dynamic Model} Let $q \in (0, 1).$ A decision maker allocates treatments to $1-q$ proportion of a population of agents $i=1, 2, \dots$ at each time step $t \in \{1, 2, \dots\}.$ Agents' observed covariates are denoted $X_{i}^{t} \in \mathbb{R}^{d}$. At time $t$, the decision maker observes covariates $X_{i}^{t}$ and assigns treatments $W_{i}^{t} \in \{0, 1\}$ using a policy $\pi: \mathbb{R}^{d} \rightarrow \{0, 1\}$. In our motivating example, the decision maker is the college and the agents are students applying to the college. The covariates are students' applications, consisting of test scores and grades, that they submit to the college. The treatment represents admission to the college, which is desirable for the students. We consider linear threshold rules with coefficients $\beta \in \mathcal{B} = \mathbb{S}^{d-1}$ and a threshold $S^{t} \in \mathbb{R}$, i.e. $\pi(X; \beta, S^{t}) = \mathbb{I}(\beta^{T}X > S^{t}).$ The decision maker fixes the selection criterion $\beta$ for all time steps $t$, while the threshold $S^{t}$ varies with $t$ to ensure that the capacity constraint is satisfied at each time step. In time step $t$, agents will respond strategically to the coefficients $\beta$ and the threshold from the previous time step $t-1,$ which is $S^{t-1}$, i.e., $X_{i}^{t} = X_{i}(\beta, S^{t-1})$. The function $X_{i}$ may be stochastic. In the context of college admissions, students, with knowledge of the selection criterion and previous acceptance threshold, can invest effort to change their baseline test scores and grades, to improve their chances of being admitted. Section (ref) provides additional structure for agent behavior. Let $P(\beta, s)(\cdot)$ denote the CDF over scores $\beta^{T}X_{i}(\beta, s)$ that results when agents report covariates in response to a policy with parameters $\beta$ and $s$. The distribution over scores at time step $t$ is given by $P^{t} = P(\beta, S^{t-1})$. Following bhattacharya2012inferring, the threshold $S^{t}$ is set to $q(P^{t})$, which is the $q$-th quantile of $P^{t}$, ensuring that only $1-q$ proportion of agents are treated. In the context of college admissions, the college can only accept $1-q$ fraction of the applicant pool, so they admit students who rank above the $q$-th quantile of the score distribution. Accordingly, we set $S^{t} = q(P^{t})$ and $W_{i}^{t} = \pi(X_{i}^{t}; \beta, S^{t}).$ After treatment assignment, the decision maker observes individual outcomes $Y_{i}^{t}$ for each agent. These outcomes may depend on the treatment received. The outcome $Y_{i}(0)$ is observed if the agent is not assigned to treatment, and the outcome $Y_{i}(1)$ is observed when the agent is assigned to treatment, $Y_{i}^{t} = Y_{i}(W^{t}_{i})$. In the context of college admissions $Y_{i}$ may represent the number of months student $i$ enrolls in the college. Let $V^{t}$ be the value of a policy at time step $t$. We define the policy value to be the mean outcome of the agents after treatments are allocated \begin{align} \begin{split} V^{t}(\beta) &= \EE[]{Y_{i}(W_{i}^{t})} = V(\beta, S^{t-1}, S^{t}),\\ &\where V(\beta, s, r) = \EE[]{Y_{i}(\pi(X_{i}(\beta, s); \beta, r))}. \end{split} \end{align} Note that the previous equation makes the dependence of $V^{t}$ on $S^{t-1}$ and $S^{t}$ explicit. The argument $s$ is the previous threshold, which agents react to in the current time step. The argument $r$ is the current threshold, which enforces the capacity constraint in the current time step. Given a fixed choice of $\beta$, a policy may reach an equilibrium with a stable decision threshold. When such an equilibrium threshold $s(\beta)$ exists and is unique, it is natural for the decision maker to seek to maximize the induced equilibrium policy value $V_{\text{eq}}(\beta)$ as defined below. We provide formal results on existence and uniqueness of equilibrium thresholds in Section (ref). We note that the objective of optimizing equilibrium welfare is motivated by the observation that it may not be feasible for the decision maker to change their selection criterion at each time step. Instead, the decision maker aims to select $\beta$ that performs well when the system is at equilibrium. \begin{defi}[Equilibrium Policy Value] Given a fixed $\beta \in \mathcal{B}$, if there is a unique equilibrium threshold $s(\beta)$, then the equilibrium policy value is $V_{\text{eq}}(\beta) = V(\beta, s(\beta), s(\beta))$, where $V(\cdot)$ is as defined in (ref). \end{defi} \subsection{Agent Behavior} We specify a model for agent behavior. In our model, agents are heterogenous in their raw covariates and ability to modify their covariates, myopic in that they choose their reported covariates based on the previous policy, and imperfect in that their reported covariates are subject to noise. For every agent $i$, unobservables $(Z_{i}, c_{i}, \epsilon_{i}, Y_{i}(0), Y_{i}(1))$ are sampled i.i.d. from a distribution $F$, where $\epsilon_{i}$ is independent from the other unobservables and has distribution $N(0, \sigma^{2}\mathbf{I}_{d}).$ Motivated by frankel2019improving, frankel2019muddled, we assume agents are heterogeneous in their raw covariates $Z_{i}$ and their ability to modify their covariates given by a cost function $c_{i}$. Let $Z_{i} \in \mathcal{X}$, where $\mathcal{X}$ is a convex, compact set in $\mathbb{R}^{d}$. Let $c_{i}(\cdot): \mathbb{R}^{d} \rightarrow \mathbb{R}$ capture agent $i$'s cost deviating from their raw covariates $Z_{i}$. Define $\tilde{X} = \{ x_{1}, x_{2} \in \mathcal{X} \mid x_{1} - x_{2} \}.$ We assume the cost functions $c_{i} \in \mathcal{C} \subset L^{2}(\tilde{\mathcal{X}}, dx)$, where $\mathcal{C}$ is a convex and compact set of functions. The agent is myopic in that they modify their covariates with knowledge of only the criterion $\beta \in \mathcal{B}$ and the previous threshold for receiving treatment $s \in \mathbb{R}$. In addition, we suppose the agent has imperfect control over the realized value of their modified covariates. In the context of college admissions, a student can influence their performance on an exam by changing the number of hours they study but cannot perfectly control their exam score. To capture this stochasticity, the agent's modified covariates are subject to noise $\epsilon_{i}.$ We express the agent's utility function as ${U_{i}(x; \beta, s) = - c_{i}(x - Z_{i}) + \pi(x + \epsilon_{i}; \beta, s).}$ The left term is the cost to the agent of deviating from their raw covariates. The right term is the reward from receiving the treatment. Taking the expectation over the noise yields \begin{equation} \EE[\epsilon]{U_{i}(x; \beta, s)} = -c_{i}(x - Z_{i}) + 1 - \Phi_{\sigma}(s - \beta^{T}x), \end{equation} where we denote the Normal CDF with mean 0 and variance $\sigma^{2}$ as $\Phi_{\sigma}$. For example, the expected utility function with quadratic cost is given by \begin{align} \begin{split} \EE[\epsilon]{U_{i}(x; \beta, s)} &= - (x - Z_{i})^{T}Diag(G_{i}) (x - Z_{i}) \\ &+ 1 - \Phi_{\sigma}(s - \beta^{T}x), \end{split} \end{align} where $G_{i} \in (\mathbb{R}^{+})^{d}$ and $\text{Diag}(g)$ is a diagonal matrix in $\mathbb{R}^{d \times d}$ with diagonal equal to $g.$ The best response mapping yields the covariates $x \in \mathcal{X}$ that maximize the expected utility, and we define it as ${x^{*}_{i}(\beta, s) = \argmax_{x \in \mathcal{X}} \EE[\epsilon]{U_{i}(x; \beta, s)}}.$ The agent's reported covariates are given by $X_{i}(\beta, s) = x^{*}_{i}(\beta,s) + \epsilon_{i}$, which is the agent's best response subject to noise $\epsilon_{i}$. \subsection{Properties of Agent Best Response} We establish conditions on the variance $\sigma^{2}$ of the noise distribution that guarantee continuity and contraction properties of the agent best response. Recall that in the context of college admissions, the noise represents that students have imperfect control over their actions. When the noise is low, a student's efforts translate to their desired grades and test scores. In contrast, when the noise is high, there is more variability in a student's grades and test scores at any level of effort. We require the following assumption to provide structure to the agent's cost function $c_{i}(\cdot).$ \begin{assumption} The cost function $c_{i}: \mathbb{R}^{d} \rightarrow \mathbb{R}$ is twice continuously differentiable, $\alpha_{i}$-strongly convex for $\alpha_{i} > 0$, and minimized at the origin. \end{assumption} In the context of college admissions, Assumption (ref) implies that a student must invest effort to deviate from their baseline test scores and grades. The amount of effort a student must invest to alter their test scores and grades changes smoothly with respect to the difference between modified and raw covariates. There are decreasing returns to deviating from their raw covariates because the cost of modifying their covariates grows at least quadratically. The lowest cost action is to not change their covariates, i.e. to stick with their baseline test scores and grades. The following result summarizes how agents behave in our model. We demonstrate under Assumption (ref) and sufficiently high $\sigma^{2}$, the agent best response exists, is unique, and is continuously differentiable in $(\beta, s)$. With a slightly stronger bound on the variance $\sigma^{2}$, we can additionally verify that the agent's expected score $\omega_{i}(s; \beta):= \beta^{T} x_{i}^{*}(\beta, s)$ is a contraction in $s$, i.e., for any fixed $\beta \in \mathcal{B}$, there is a Lipschitz constant $\kappa \in (0, 1)$, so that $|\omega_{i}(s; \beta) - \omega_{i}(s'; \beta)| \leq \kappa |s - s'|$ for all $s, s' \in \mathbb{R}.$ This agent-level contraction property will be useful for later establishing a mechanism that gives rise to a mean-field (population-level) equilibrium in Section (ref). \begin{prop} Let $\beta \in \mathcal{B}, s \in \mathbb{R}$, $\bar{\kappa} \in (0, 1].$ Under Assumption (ref), the best response $x^{*}_{i}(\beta, s)$ exists. If moreover $\sigma^{2} > \frac{1}{\alpha_{i} \cdot \sqrt{2\pi e}}$, then $x^{*}_{i}(\beta, s)$ is unique and continuously differentiable in $\beta, s$, whenever $x_{i}^{*}(\beta, s) \in \text{Int}(\mathcal{X})$. Finally, if $\sigma^{2} > \frac{1}{\alpha_{i} \cdot \sqrt{2\pi e}} \cdot \frac{\bar{\kappa} + 1}{\bar{\kappa}}$ additionally holds for some $\bar{\kappa} \in (0, 1]$, then the agent's expected score $\omega_{i}(s; \beta):=\beta^{T}x_{i}^{*}(\beta, s)$ is a contraction in $s$ with Lipschitz constant less than $\bar{\kappa}$ for any $\beta \in \mathcal{B}.$ \end{prop} \begin{figure} \caption{We plot $\omega_{i}(s; \beta)$ vs. $s$ at different noise levels and observe its continuity and contraction properties.} \end{figure} We end this section by numerically investigating the role of noise on an agent's best response, and verify that in the absence of sufficient noise, unstable behaviors may occur. Qualitatively, in a zero-noise setting, instability arises because there are two modes of agent behavior. In one mode, the agent defaults to their raw covariates, so $\omega_{i}(s; \beta) \approx \beta^{T}Z_{i}$, either because the threshold is low enough that the agent expects to receive the treatment without modifying their covariates or because the threshold is so high that the agent does not bother modifying their covariates at all. In the other mode, the threshold takes on intermediate values, so the agent will invest the minimum effort to ensure that they receive the treatment under the previous policy, meaning that $\omega_{i}(s; \beta) = s$. When covariate modification is no longer beneficial, the agent defaults to their raw covariates, creating a discontinuity in the best response. The presence of noise increases the agent's uncertainty in whether they will receive the treatment, which causes agents to be less reactive to the previous policy and smooths the agent best response. Under different noise levels $\sigma^{2}$, we analyze the expected score of an agent's best response with a fixed selection criterion $\beta$ while the threshold $s$ varies. We consider agent $i$ with quadratic cost of covariate modification as in (ref), where $Z_{i} = [3., 0.]^{T}$ and $G_{i}=[0.1, 1.]^{T}$. We suppose the decision maker's model is $\beta =[1., 0.]^{T}$. In Figure (ref), we visualize the expected score $\omega_{i}(s; \beta)$, as a function of $s$, the previous threshold for receiving treatment. We plot $\omega_{i}(s; \beta) \text{ vs. } s$ at four different noise levels $\sigma^{2}$. In the left plot of Figure (ref), we consider $\sigma^{2} > \frac{1}{\alpha_{i} \cdot \sqrt{2\pi e}} \cdot \frac{\bar{\kappa} + 1}{\bar{\kappa}}$ where $\bar{\kappa}=1$, so the expected score is a contraction in $s$. In the middle left plot, we have that $\sigma^{2} > \frac{1}{\alpha_{i} \cdot \sqrt{2\pi e}}$, so the expected score is continuous. In the plots on the right of Figure (ref), we have that $\sigma^{2} \leq \frac{1}{\alpha_{i} \cdot \sqrt{2\pi e}}$. In such cases, the best response mapping may be discontinuous and may not necessarily have a fixed point. The lack of a fixed point in the expected score in low-noise regimes (rightmost plot, Figure (ref)) implies that there are distributions over agent unobservables for which there is no equilibrium threshold in low-noise regimes. As a result, when the noise condition for continuity of best response does not hold for all agents, an equilibrium in our model may not exist. When we establish uniqueness and existence of the equilibrium in our model in Section (ref), we assume a noise condition that guarantees continuity of the agents' best response mappings.

section{Mean-Field Results} Recall that the decision maker's objective, as outlined in Section (ref), is to find a selection criterion $\beta$ that maximizes the equilibrium policy value $V_{\text{eq}}(\beta)$. This is a sensible goal in settings where an equilibrium exists and is unique for each selection criterion $\beta$ in consideration. In this section, we characterize the equilibrium in the mean-field regime. In the mean-field regime, an infinite population of agents with unobservables sampled from $F$ is considered for the treatment at each time step $t$. Let $\beta$ be the decision maker's fixed selection criterion. At time step $t$, agents report covariates with knowledge of criterion $\beta$ and previous threshold $S^{t-1}$, inducing a distribution over scores $P^{t}= P(\beta, S^{t-1}).$ Then, at time step $t$, the agents who score above threshold $S^{t} = q(P^{t})$ will receive treatment. The thresholds evolve in a deterministic fixed-point iteration process: \begin{equation} S^{t} = q(P(\beta, S^{t-1})) \quad t = 1, 2, \dots \end{equation} The system is at equilbrium if the threshold for receiving treatment is fixed over time. The equilibrium induced by $\beta$ is characterized by an equilibrium threshold $s(\beta)$, which is the threshold $s \in \mathbb{R}$ that satisfies $s = q(P(\beta, s))$. To study equilibria, we make two further assumptions: \begin{assumption} The $(Z, c)$-marginal of $F$ has finite support. \end{assumption} \begin{assumption} For an agent $i$ with unobservables in the support of $F$, $x^{*}_{i}(\beta, s) \in \text{Int}(\mathcal{X})$. \end{assumption} In the context of college admission, Assumption (ref) requires a finite number of student types. Realistically, this assumption may not hold because there could be an infinite number of types, but this assumption is made for technical convenience and we conjecture that similar results will hold when $F$ has continuous support. Meanwhile, Assumption (ref) excludes the scenario where agent best responses “bunch” at the boundaries of $\mathcal{X}$. In the context of college admissions, we require that the space of possible test scores and grades is large enough that students' post-effort test scores and grades lie in the interior of the set. frankel2019muddled argue that if this assumption is violated, it is possible to expand the covariate space to ensure that best responses lie in the interior, say by making an exam harder. The following result establishes conditions under which a mean-field equilibrium threshold exists, is unique, and can be related to $\beta$ via a differentiable function $s(\beta).$ We use notation $\alpha_{*}(F) = \inf_{i \in \mathbb{N}} \alpha_{i}$, and note that under Assumption (ref) and (ref) $\alpha_{*}(F)$ is positive. We will omit the dependence of $\alpha_{*}(F)$ on $F$ when it is clear that there is only one distribution over unobservables of interest. \begin{theo} Under Assumptions (ref), (ref), and (ref), and if $\sigma^{2} > \frac{1}{\alpha_{*} \cdot \sqrt{2\pi e}}$, then $q(P(\beta, s))$ is continuously differentiable in $\beta, s.$ Furthermore, for any $\beta \in \mathcal{B}$, there is a unique fixed point $s(\beta)$ satisfying $s(\beta) = q(P(\beta, s(\beta))),$ and $s(\beta)$ is continuously differentiable in $\beta$. If moreover $\sigma^{2} > \frac{1}{\alpha_{*} \cdot \sqrt{2\pi e}} \cdot \frac{\bar{\kappa} + 1}{\bar{\kappa}}$ for $\bar{\kappa} \in (0, 1]$, then, for any $\beta \in \mathcal{B}$, $q(P(\beta, s))$ is a contraction in $s$ with Lipschitz constant less than $\bar{\kappa}$ and the fixed-point iteration (ref) converges to $s(\beta)$. \end{theo} The last part of Theorem (ref) gives conditions for the population quantile mapping $q(P(\beta, \cdot))$ to be a contraction with Lipschitz constant less than $\bar{\kappa}$. Importantly, these conditions are sufficient, but not necessary. We find that the derivative of $q(P(\beta, \cdot))$ is a convex combination of the derivatives of the agents' expected scores $\omega_{i}(\cdot; \beta)$. Our conditions imply that these derivatives have magnitude less than $\bar{\kappa}$ for all agents, so $q(P(\beta, \cdot))$ must also have derivative with magnitude less than $\bar{\kappa}$ and thus be a contraction with Lipschitz constant less than $\bar{\kappa}$. Nevertheless, it is possible for $q(P(\beta, \cdot))$ to be a contraction even if $\omega_{i}(s; \beta)$ is not a contraction for every agent $i$.

section{Finite-Sample Approximation} Understanding equilibrium behavior of our model in the finite regime is of interest because our ultimate goal is to learn optimal equilibrium policies in finite samples. In this section, we instantiate the model from Section (ref) in the regime where a finite number of agents are considered for the treatment. A difficulty of the finite regime is that deterministic equilibria do not exist. Instead, we give conditions under which stochastic equilibria arise and show that, in large samples, these stochastic equilibria sharply approximate the mean-field limit derived above. \begin{figure}[t] \caption{We plot iterates an example process (ref). For large $n$, iterates concentrate about the mean-field equilibrium. } \end{figure} Let $\beta$ be the decision maker's fixed selection criterion. At each time step, $n$ new agents with unobservables sampled i.i.d. from $F$ are considered for the treatment. In the context of college admissions, the sampled agents at each time step represent a cohort of students applying for admission each year. At time step $t$, the $n$ agents who are being considered for the treatment report their covariates with knowledge of the criterion $\beta$ and previous threshold $\hat{S}^{t-1}_{n}$. Let $P^{n}(\beta, s)$ be the empirical score distribution when $n$ agents best respond to a policy $\beta$ and threshold $s$. So, the distribution over scores at time step $t$ is given by $P^{n, t} = P^{n}(\beta, \hat{S}^{t-1}_{n}).$ Let $q(P^{n, t})$ denote the $q$-th quantile of $P^{n, t}$. Then, agents who score above $\hat{S}^{t}_{n} = q(P^{n, t-1})$ will receive the treatment. The thresholds evolve in a stochastic fixed-point process \begin{equation} \hat{S}^{t}_{n} = q(P^{n, t}) = q(P^{n}(\beta, \hat{S}^{t-1}_{n})), \quad t=1, 2, \dots \end{equation} Since new agents are sampled at each time step, $q(P^{n}(\beta, \cdot))$ is a random operator. Iterating this operator given some initial threshold $\hat{S}^{0}_{n}$ yields a stochastic process $\{\hat{S}^{t}_{n}\}_{t \geq 0}$. Figure (ref) visualizes an example of this process. We note that for any fixed $\beta$, the random operator $q(P^{n}(\beta, \cdot))$ approximates the deterministic function $q(P(\beta, \cdot))$. The following result gives a finite-sample concentration inequality for the behavior of $q(P^{n}(\beta, s))$. \begin{lemm} Fix $\beta \in \mathcal{B}$. For $\lambda > 0$, define \begin{align} \begin{split} M_{\lambda} = \inf_{s \in \mathbb{R}} \min\{&P(\beta, s)(q(P(\beta, s)) + \lambda) - q,\\ & q - P(\beta, s)(q(P(\beta, s)) - \lambda)\}. \end{split} \end{align} Under Assumption (ref), (ref), (ref), if $\sigma^{2} > \frac{1}{\alpha_{*} \sqrt{2 \pi e}},$ then $M_{\lambda} > 0$, $M_{\lambda}$ is approximately linear in $\lambda$ when $\lambda \rightarrow 0$, and \[ P(|q(P(\beta, s)) - q(P^{n}(\beta, s))| < \lambda) \geq 1 - 4e^{-2nM_{\lambda}^{2}}.\] \end{lemm} Notably, the bound in the concentration inequality does not depend on the particular choice of $s$. We use this lemma to characterize the behavior of the finite system for sufficiently large iterates $t$ and number of agents $n$. Theorem (ref) shows that under the same conditions that enable fixed-point iteration in the mean-field model (ref) to converge to the mean-field equilibrium threshold $s(\beta)$, sufficiently large iterates of the stochastic fixed-point iteration in the finite model (ref) will lie in a small neighborhood about $s(\beta)$ with high probability. We can view these iterates as stochastic equilibria of the finite system. \begin{theo} Fix $\beta \in \mathcal{B}$. Suppose Assumptions (ref), (ref), (ref) hold. Let $\lambda \in (0, 1), \delta \in (0, 1)$, $s(\beta)$ is the mean-field equilibrium threshold induced by $\beta$, and $M_{\lambda}$ is defined by (ref). Let $\kappa$ be the Lipschitz constant of $q(P(\beta, \cdot))$. Let $\lambda_{g} = \frac{\lambda (1 - \kappa)}{2}$ and $C = |\hat{S}^{0}_{n} - s(\beta)|.$ If $\sigma^{2} > \frac{2}{\alpha_{*}\sqrt{2\pi e}},$ then for $n, t$ such that $t \geq \Big\lceil \frac{\log(\frac{\lambda}{2C}) }{\log \kappa} \Big\rceil$ and $n \geq \frac{1}{2M_{\lambda_{g}}^{2}} \log (\frac{4t}{\delta}),$ then $P(|\hat{S}_{n}^{t} - s(\beta)| \geq \lambda ) \leq \delta.$ \end{theo} Under our assumptions, we can apply Theorem (ref) to see that $\kappa$, the Lipschitz constant of the population quantile mapping $q(P(\beta, \cdot))$, is a constant that is less than 1. Since $\lambda_{g}$ depends linearly on $(1- \kappa)$ and $M_{\lambda}$ is approximately linear in $\lambda$ for small $\lambda$, we find that the required sample complexity scales with $\frac{1}{(1 - \kappa)^{2}}.$ \begin{coro} Fix $\beta \in \mathcal{B}$. Let $\{t_{n}\}$ be a sequence such that $t_{n} \uparrow \infty$ as $n \rightarrow \infty$ and $t_{n} \prec \exp(n)$ ($t_{n}$ grows slower than exponentially fast in $n$). Under the conditions of Theorem (ref), $\hat{S}_{n}^{t_{n}} \xrightarrow{p} s(\beta),$ where $s(\beta)$ is the unique fixed point of $q(P(\beta, \cdot)).$ \end{coro}

section{Learning Policies via Gradient-Based Optimization} In this section, we define the policy gradient, the gradient of the equilibrium policy value with respect to the selection criterion, give an estimator of the policy gradient, and use the estimator to learn policies. We use a local unit-level experimentation scheme as in munro2021treatment, wager2021experimenting to estimate the gradient and gradient-based optimization to learn policies. \begin{lemm} Under the conditions of Theorem (ref), $V_{\text{eq}}(\beta)$ from Definition (ref) is continuously differentiable in $\beta$, and \begin{align} \begin{split} \frac{dV_{eq}}{d \beta}(\beta) &=\frac{\partial V}{\partial \beta}(\beta, s(\beta), s(\beta)) \\ &+ \Big(\frac{\partial V}{\partial s}(\beta, s(\beta), s(\beta)) \\ &+ \frac{\partial V}{\partial r}(\beta, s(\beta), s(\beta))\Big) \cdot \frac{\partial s}{\partial \beta}(\beta). \end{split} \end{align} \end{lemm} We decompose the total derivative of $V_{\text{eq}}(\beta)$, or the policy gradient, into two parts. The first term corresponds to the model gradient and the second term corresponds to the equilibrium gradient. \begin{defi}[Model Gradient] The model gradient $\tau_{\text{MG}}$ is $\tau_{\text{MG}}(\beta) = \frac{\partial V}{\partial \beta}(\beta, s(\beta), s(\beta)).$ \end{defi} The selection criterion $\beta$ impacts the policy value because the criterion is used to score the agents and agents modify their covariates in response to the criterion. Optimization of the selection criterion using the model gradient is a policy learning approach that accounts for agents' strategic behavior. Due to the decision maker's capacity constraint, the equilibrium threshold for receiving treatment also depends on the selection criterion. So, we must also account for how policy value changes with respect to the equilibrium threshold and how the equilibrium threshold changes with respect to the selection criterion. Following notation from (ref), we write $\partial V / \partial s$ and $\partial V / \partial r$ for the partial derivatives of $V$ in its second and third arguments respectively. \begin{defi}[Equilibrium Gradient] The equilibrium gradient $\tau_{\text{EG}}$ is $\tau_{\text{EG}}(\beta) =\Big( \frac{\partial V}{\partial s}(\beta, s(\beta), s(\beta)) + \frac{\partial V}{\partial r}(\beta, s(\beta), s(\beta)) \Big) \cdot \frac{\partial s}{\partial \beta}(\beta).$ \end{defi} The previous threshold for receiving treatment $s$ impacts the policy value because agents modify their covariates in response to $s$. This influences the treatments that agents receive and thus the policy value. The current threshold for receiving treatment $r$ impacts the policy value because it determines agents' treatment assignments, which influences the policy value, as well. At equilibrium, we have that $s=r=s(\beta)$, so we can account for both of these effects simultaneously. \begin{defi}[Policy Gradient] The policy gradient $\tau_{\text{PG}}$ is $\tau_{\text{PG}}(\beta) = \tau_{\text{MG}}(\beta) + \tau_{\text{EG}}(\beta).$ \end{defi} This decomposition is related to the decomposition theorem of hu2021average. hu2021average consider a Bernoulli trial, where treatments are allocated according to $W_{i} \sim \text{Bernoulli}(p_{i})$ for $p \in (0, 1)^{n}$, and they demonstrate that the effect of a policy intervention that infinitesimally increases treatment probabilities can be decomposed into the average direct and indirect effects. The average direct effect captures how the outcome $Y_{i}$ of a unit is affected by its own treatment $W_{i}$ on average. The average indirect effect is the term that captures the responsiveness of outcome $Y_{i}$ to the treatment of other units $j\neq i$ on average, measuring the effect of cross-unit interference. When there is no cross-unit interference, the average direct effect matches the usual average treatment effect hu2021average, savje2021average. In our setting, the policy gradient consists of the model gradient, which captures how changes in the selection criterion directly impact the policy value through scoring the agents and agents' strategic behavior, and the equilibrium gradient, which captures how changes in the selection criterion indirectly impact the policy value by modulating the threshold for receiving treatment. In the absence of capacity constraints, the policy gradient is just the model gradient. We derive estimators for the policy gradient through a unit-level randomized experiment in finite samples. In a system consisting of $n$ agents, we apply symmetric, mean-zero perturbations to the parameters of the policy that each agent responds to. Let $R$ represent the distribution of Rademacher random variables and let $R^{d}$ represent a distribution over $d$-dimensional Rademacher random variables. For agent $i$, we apply perturbations of magnitude $b > 0$ to the policy parameters. We set $\beta_{i} = \beta + b\zeta_{i}$ where $\zeta_{i} \sim R^{d}$ and $s_{i} = s + b\xi_{i}$ where $\xi_{i} \sim R.$ In practice, the perturbation to the selection criterion can be implemented by telling agent $i$ that they will be scored according to $\beta_{i}$ instead of $\beta$. The perturbation to the threshold $s$ can be implemented by publicly reporting the previous threshold $s$ but telling agent $i$ that a small shock of size $-b\xi_{i}$ will be added to the agent's score in the next time step. We extend our myopic agent model and assume that an agent $i$ will report covariates in response a policy $\pi(x; \beta_{i}, s_{i})$ as follows: \begin{align} \begin{split} X_{i}(\beta_{i}, s_{i}) &= x_{i}^{*}(\beta_{i}, s_{i}) + \epsilon_{i}, \\ \where x_{i}^{*}(\beta_{i}, s_{i}) &= \argmax_{x \in \mathcal{X}} \EE[\epsilon]{U_{i}(x; \beta_{i}, s_{i})}. \end{split} \end{align} The prescribed perturbations are applied to determine the agents' scores and treatment assignments. For clarity, we contrast the form of a score in the unperturbed setting with the perturbed setting. In the unperturbed setting, an agent with unobservables $(Z_{i}, c_{i})$ who best responds to $\beta, s$ will obtain a score $\beta^{T}X_{i}(\beta, s)$. In the perturbed setting, an agent with unobservables $(Z_{i}, c_{i})$ who best responds to a perturbed version of $\beta, s$ will obtain a score $\beta_{i}^{T}X_{i}(\beta_{i}, s_{i}) - b\xi_{i}.$ Let $P(\beta, s, b)(\cdot)$ denote the distribution over scores in the perturbed setting. The threshold for receiving treatment in the experiment is $r = q(P^{n}(\beta, s, b)).$ The agent-specific threshold for receiving treatment is given by $r_{i} = r + b\xi_{i}.$ So, in the experiment, the treatments are allocated as $W_{i} = \pi(X_{i}(\beta_{i}, s_{i}); \beta_{i}, r_{i})$. As in munro2021treatment, wager2021experimenting, the purpose of applying these perturbations is so that we can recover relevant gradient terms without disturbing the equilibrium behavior of the system. We compute the gradients by running regressions from the perturbations to quantities of interest, which include the observed outcomes and indicators for agents who score above the threshold $r$. To construct the estimators of the model and equilibrium gradients, we rely on gradient estimates of the policy value function $V(\beta, s, r)$ and gradient estimates of the complementary CDF of the score distribution $\Pi(\beta, s)(\cdot)$, which is defined as $\Pi(\beta, s)(\cdot) = 1 - P(\beta, s)(\cdot).$ In this experiment, we suppose that thresholds evolve by the stochastic fixed-point iteration process below. Note that it differs slightly from the process given in (ref). \begin{equation} \hat{S}^{t}_{b, n} = \min(\max(q(P^{n}(\beta, \hat{S}^{t-1}_{b, n}), -D)), D). \end{equation} This process differs from (ref) because it includes perturbations of size $b$ to the selection criterion and threshold and restricts the threshold to a bounded set $\mathcal{S}=[-D, D]$ where $D$ is sufficiently large constant so that $s(\beta) \in \mathcal{S}$. Such a set exists because it can be shown there exists $D > 0$ such that $|q(P(\beta, s))|< D$ for all $s \in \mathbb{R}$. Analyzing the stochastic process $\{\hat{S}^{t}_{b, n}\}_{t \geq 0}$ generated by (ref) presents two technical challenges. First, (ref) truncates the threshold values so that they lie in $\mathcal{S}$, whereas the process analyzed in Section (ref) does not involve truncation. Nevertheless, the truncation is a contraction map to the equilibrium threshold, so the results of Section (ref) also apply to stochastic fixed point iteration with truncation. The other challenge is that the results from Section (ref) and (ref) focus on the setting where all agents best respond to the same policy $\pi(x; \beta, s)$, whereas in (ref), each agent $i$ best responds to a different perturbed policy $\pi(x; \beta_{i}, s_{i})$. To show that results from Section (ref) transfer to the setting with unit-level perturbations, we can define a new distribution over agent unobservables $\tilde{F}$ that are related to the original distribution over agent unobservables $F$. When agents with unobservables sampled from $\tilde{F}$ best respond to $\pi(x; \beta, s)$, the score distribution that results equals $P(\beta, s, b)$. We require the following assumption to guarantee that the transformed unobservables in $\text{supp}(\tilde{F})$ can be defined on the same spaces as the original unobservables in $\text{supp}(F).$ \begin{assumption} For any $Z_{i} \in \text{supp}(F_{Z}),$ $Z_{i} \in \text{Int}(\mathcal{X}).$ In addition, $c_{i'} \in \mathcal{C}$, where $c_{i'}(y) = c_{i}(y) - \phi_{\sigma}(s - r)\beta^{T}y$ for any $c_{i} \in \text{supp}(F_{c}), \beta \in \mathcal{B}, s, r \in \mathcal{S}.$ \end{assumption} In the context of college admissions, Assumption (ref) requires that $\mathcal{X}$ is large enough that agents' raw covariates do not “bunch” at the boundaries of $\mathcal{X}$, and that $\mathcal{C}$ is large enough that it contains cost functions that are linear offsets of the cost functions in $\text{supp}(F_{c})$. This assumption is also plausible in the context of college admissions; e.g., students would likely not get exactly 0 test score even if they do not try, and the set of possible cost functions is rich. Note that if this assumption is not satisfied for a given distribution $F$, we can likely enlarge the space of cost functions $\mathcal{C}$ and covariates $\mathcal{X}$. We define the model gradient estimator. Suppose $n$ agents are considered for the treatment. Let each row of $\mathbf{M}_{\beta} \in \mathbb{R}^{n \times d}$ correspond to $b\zeta_{i}^{T}$, the perturbation applied to the selection criterion $\beta$ observed by the $i$-th agent. Let each entry of $Y \in \mathbb{R}^{n}$ correspond to the observed outcome of the $i$-th agent, so $Y_{i}= Y_{i}(W_{i}).$ The regression coefficient obtained by running OLS of $Y$ on $\mathbf{M}_{\beta}$ is \[ \hat{\Gamma}_{Y, \beta}^{b, n}(\beta, s, r) = b^{-1}\Big(\frac{1}{n} \sum_{i=1}^{n}\zeta_{i}\zeta_{i}^{T}\Big)^{-1}\Big(\frac{1}{n} \sum_{i=1}^{n}\zeta_{i}Y_{i}\Big).\] The model gradient estimator with sample size $n$, perturbation size $b$, and iteration $t$ as \begin{equation} \hat{\tau}_{MG,b, n}^{t}(\beta) = \hat{\Gamma}^{b, n}_{Y , \beta}(\beta, \hat{S}^{t-1}_{b, n}, \hat{S}^{t}_{b, n}), \end{equation} where $\hat{S}^{t}_{b, n}$ is given by (ref). One of the challenges in analyzing this estimator is that $\hat{\Gamma}^{b, n}_{Y, \beta}$ is a stochastic function and its arguments are also stochastic. To demonstrate consistency of the overall estimator, we must establish stochastic equicontinuity for $\hat{\Gamma}^{b, n}_{Y, \beta}$. As a result, we require the following assumption on the outcomes $Y_{i}(w).$ \begin{assumption} Let $m(z, c; w)= \EE[]{Y_{i}(w) \mid Z_{i}=z, c_{i}=c}.$ For $w \in \{0, 1\}$, the potential outcome $Y_{i}(w)$ can be decomposed as $Y_{i}(w) = m(Z_{i}, c_{i}; w) + \rho_{i}$, where $\EE{\rho_{i} \mid Z_{i}, c_{i}} = 0$ and $m$ is continuous with respect to $(z, c) \in \mathcal{X} \times L^{2}(\tilde{\mathcal{X}}, dx)$ and bounded. \end{assumption} This assumption essentially states that agents with the same raw covariates and cost function for covariate modification, on average, have the same potential outcomes upon being accepted or rejected. This is plausible in the context of college admissions if space of raw features and cost functions is rich. In addition, we also require that the conditional mean outcome is continuous with respect to the raw covariates and cost function for covariate modification. \begin{theo} Fix $\beta \in \mathcal{B}.$ Let $\{t_{n}\}$ be a sequence such that $t_{n} \uparrow \infty$ as $n \rightarrow \infty$ and $t_{n} \prec \exp(n).$ Let $\mathcal{S} = [-D, D]$ for a sufficiently large constant $D> 0$, so that the equilibrium threshold $s(\beta) \in \mathcal{S}.$ Under Assumptions (ref), (ref), (ref), (ref), and (ref), if $\sigma^{2} > \frac{2}{\alpha_{*}\sqrt{2\pi e}},$ then there exists a sequence $\{b_{n}\}$ such that $b_{n} \rightarrow 0$ so that $\hat{\tau}_{\text{MG},b_{n}, n}^{t_{n}}(\beta) \xrightarrow{p} \tau_{\text{MG}}(\beta).$ \end{theo} Second, we define the equilibrium gradient estimator. Although the same approach applies, estimating the equilibrium gradient is more complicated than estimating the model gradient. We estimate the equilibrium gradient by estimating the two components of the equilibrium gradient, $\frac{\partial V}{\partial s} + \frac{\partial V}{\partial r}$ and $\frac{\partial s}{\partial \beta}.$ Again, suppose $n$ agents are considered for the treatment. Let each row of $\mathbf{M}_{\beta} \in \mathbb{R}^{n \times d}$ and of $\mathbf{M}_{s} \in \mathbb{R}^{n \times 1}$ correspond to the perturbation applied to the selection criterion $\beta$ and threshold $s$, respectively for the $i$-th agent. Let each entry of $Y, I \in \mathbb{R}^{n}$ correspond to the following quantities for the $i$-th agent \[Y_{i} = Y_{i}(W_{i}), \quad I_{i} = \pi(X_{i}(\beta_{i}, s_{i}); \beta_{i}, r).\] The regression coefficients from running OLS of $Y$ on $\mathbf{M}_{s}$, $I$ on $\mathbf{M}_{\beta}$, and $I$ on $\mathbf{M}_{s}$ are given by \begin{align*} \hat{\Gamma}_{Y, s, r}^{b, n}(\beta, s, r) &= b^{-1}\Big(\frac{1}{n} \sum_{i=1}^{n}\xi_{i}\xi_{i}^{T}\Big)^{-1}\Big(\frac{1}{n} \sum_{i=1}^{n}\xi_{i}Y_{i}\Big), \\ \hat{\Gamma}_{\Pi, \beta}^{b, n}(\beta, s, r) &= b^{-1}\Big(\frac{1}{n} \sum_{i=1}^{n}\zeta_{i}\zeta_{i}^{T}\Big)^{-1}\Big(\frac{1}{n} \sum_{i=1}^{n}\zeta_{i}I_{i}\Big), \\ \hat{\Gamma}_{\Pi, s}^{b, n}(\beta, s, r) &= b^{-1}\Big(\frac{1}{n} \sum_{i=1}^{n}\xi_{i}\xi_{i}^{T}\Big)^{-1}\Big(\frac{1}{n} \sum_{i=1}^{n}\xi_{i}I_{i}\Big). \end{align*} Let $\{h_{n}\}$ be a sequence such that $h_{n} \rightarrow 0$ and $nh_{n} \rightarrow \infty$. Let $p^{n}(\beta, s, b)(r)$ denote a kernel density estimate of $p(\beta, s, b)(r)$ with kernel function $k(z) = \mathbb{I}(z \in [- \frac{1}{2}, \frac{1}{2}))$ and bandwidth $h_{n}.$ We define the equilibrium gradient estimator with sample size $n$ and iteration $t$ as \begin{align} \begin{split} &\hat{\tau}_{EG,b, n}^{t}(\beta) \\ &= \hat{\Gamma}^{b, n}_{Y, s, r}(\beta, \hat{S}^{t-1}_{b, n}, \hat{S}^{t}_{b, n}) \cdot \\ &\Bigg( \frac{1}{p^{n}(\beta, \hat{S}^{t}_{b, n}, b)(\hat{S}^{t}_{b, n}) - \hat{\Gamma}_{\Pi, s}^{b, n}(\beta, \hat{S}^{t}_{b, n}, \hat{S}^{t}_{b, n}) } \cdot \\ &\hat{\Gamma}_{\Pi, \beta}^{b, n}(\beta, \hat{S}^{t}_{b, n}, \hat{S}^{t}_{b, n})\Bigg). \end{split} \end{align} Theorem (ref) shows that this estimator is consistent for the equilibrium gradient. \begin{theo} Fix $\beta \in \mathcal{B}.$ Let $\{t_{n}\}$ be a sequence such that $t_{n} \uparrow \infty$ as $n \rightarrow \infty$ and $t_{n} \prec \exp(n).$ Let $\mathcal{S} = [-D, D]$ for a sufficiently large constant $D> 0$, so that the equilibrium threshold $s(\beta) \in \mathcal{S}.$ Under the conditions of Theorem (ref), there exists a sequence $\{b_{n}\}$ such that $b_{n} \rightarrow 0$ so that $\hat{\tau}_{\text{EG}, b_{n}, n}^{t_{n}}(\beta) \xrightarrow{p} \tau_{\text{EG}}(\beta).$ \end{theo} To estimate the policy gradient, we sum the model and equilibrium gradient estimators. \begin{coro} Fix $\beta \in \mathcal{B}.$ Let $\{t_{n}\}$ be a sequence such that $t_{n} \uparrow \infty$ as $n \rightarrow \infty$ and $t_{n} \prec \exp(n).$ Let $\mathcal{S} = [-D, D]$ for a sufficiently large constant $D> 0$, so that the equilibrium threshold $s(\beta) \in \mathcal{S}.$ We consider the sequence of approximate policy gradients given by \[ \hat{\tau}_{\text{PG},b_{n}, n}^{t_{n}}(\beta) = \hat{\tau}_{\text{MG},b_{n}, n}^{t_{n}}(\beta) + \hat{\tau}_{\text{EG},b_{n}, n}^{t_{n}}(\beta).\] Under the conditions of Theorem (ref), there exists a sequence $\{b_{n}\}$ such that $b_{n} \rightarrow 0$ so that $\hat{\tau}_{\text{PG}, b_{n}, n}^{t_{n}}(\beta) \xrightarrow{p} \tau_{\text{PG}}(\beta).$ \end{coro} These policy gradients can then be used for learning an optimal policy. Following wager2021experimenting,we first learn equilibrium-adjusted gradients of the policy value as discussed above and then update the selection criterion with the gradient to maximize the policy value; see Algorithm (ref) in the appendix for details. In this paper, we will only investigate empirical properties of this approach and refer to wager2021experimenting for formal results for this type of gradient-based learning. The decision maker runs the algorithm for $J$ epochs. In Section (ref), we describe that it may be infeasible for the decision maker to update the selection criterion at each time step. This algorithm requires the decision maker to deploy an updated selection criterion at each epoch $j$. In other words, updates to the selection criterion are necessary but infrequent. We emphasize that deploying different selection criteria is only necessary for the learning procedure, and ultimately, we aim to learn a fixed selection criterion that maximizes the equilibrium policy value. In epoch $j$, the decision maker deploys criterion $\beta^{j}$. By iterating (ref), a stochastic equilibrium induced by $\beta^{j}$ emerges, yielding the equilibrium threshold $s^{j}$. Each agent best responds to their perturbed policy and the decision maker observes their reported covariates. Following the procedure given above, the decision maker can then estimate the policy gradient of $\beta^{j}$ on the equilibrium policy value (Algorithm (ref)). The decision maker can set $\beta^{j+1}$ by taking a gradient step from $\beta^{j}$ using the policy gradient estimator as the gradient. Note that because we aim to maximize the policy value, we update $\beta$ by moving in the direction of the gradient.

section{Numerical Evaluation} We demonstrate that the policy gradient estimator defined in Section (ref) can be used to learn a policy that achieves higher equilibrium policy value compared to approaches that only account for capacity constraints or only account for strategic behavior. In a semi-synthetic experiment using data from the National Education Longitudinal Study of 1988 (NELS) ingels1994national, we also discuss how the learned policy impacts the distribution of accepted students. We evaluate our approach along with two baselines, as described below. The first baseline, capacity-aware policy learning, considers capacity constraints but ignores strategic behavior, and the second baseline, strategy-aware gradient-based optimization, accounts for strategic behavior but ignores capacity constraints. Our proposed method accounts for both strategic behavior and capacity constraints. All methods only use sampled data and do not have access to unobservables. \paragraph{Capacity-Aware Policy Learning} Following bhattacharya2012inferring, the decision maker runs a randomized controlled trial (RCT) to estimate the conditional average treatment effect (CATE) $\tau(x) = \EE[]{Y_{i}(1) - Y_{i}(0) \mid X=x}$ and at deployment, assigns treatment to students with CATE estimate above the $q$-th quantile. Note that students are not strategic in the RCT because treatment assignment is random but will be strategic at deployment. In our implementation, we obtain a CATE estimate of the form $\beta_{1}x + \beta_{0}$ by estimating the conditional mean outcomes via linear regression and subtracting the models. We refer to this method's learned policy as $\beta_{\text{cap}} = \text{Proj}_{\mathcal{B}}(\beta_{1}),$ which is a projection of the parameters of the CATE onto the allowed policy class $\mathcal{B}$. \paragraph{Strategy-Aware Gradient-Based Optimization} The decision maker runs a unit-level experiment each epoch to obtain a consistent estimate the model gradient (Section (ref)). The decision maker then updates the selection criterion $\beta$ via projected gradient descent. Recall that the model gradient accounts for students' strategic behavior but does not account for the equilibrium effect. We refer to this method's learned solution as $\beta_{\text{strat}}$. \paragraph{Competition-Aware Gradient-Based Optimization} In our proposed approach, the decision maker runs a unit-level experiment each epoch to obtain a consistent estimate of the policy gradient (Section (ref)). The decision maker then updates the selection criterion $\beta$ via projected gradient descent. We refer to the learned solution of this method as $\beta_{\text{comp}}.$ We evaluate these methods on a semi-synthetic policy learning experiment for college admissions. Using NELS data, we construct a realistic distribution over agent unobservables. NELS is a nationally representative, longitudinal study that followed eighth graders in 1988 throughout their secondary and postsecondary years. NELS includes socioeconomic status (SES), twelfth grade standardized test scores in reading, math, science, and history and average grades in English, math, science, social studies, and foreign language, and post-secondary outcomes for $n=14915$ students. We construct a simulated distribution over agent unobservables using the NELS data.\footnote{Due to computational constraints of the data generation, we construct a distribution over $K = 8$ representative agent types instead of using the empirical distribution over all $m$ unobservables. Additional details on the dataset generation are provided in Appendix (ref).} We assume a student's $d$-dimensional ($d=9$) best response $x_{i}^{*}$ corresponds to reported test scores and grades from the NELS dataset. We use the subscripts “test scores" and “grades” to specify the covariates that correspond to test scores and grades, respectively. We also assume that students have a quadratic cost of modifying covariates (see (ref)), where the cost of modifying test scores is low and is the same for all students and the cost of modifying grades is high and inversely proportional to SES. So, all students can easily modify their test scores but high SES students can more easily modify their grades compared to low SES students. Under these assumptions, we estimate the students' raw covariates $Z_{i}.$ We consider a decision maker who can only accept 30% of the student population. We consider three different outcome variables. Let $Y_{i, 1}(1)$ be the number of months student $i$ will enrolled in postsecondary school from June 1992 - August 1994 (reported in NELS) if accepted, $Y_{i, 2}(1)$ be a proxy for the raw academic performance of student $i$ given by $\bar{Z}_{i, \text{test scores}}$ if accepted, and $Y_{i, 3}(1)$ is proportional to the inverse of the SES of student $i$ if accepted. Note that $Y_{i, j}(0)=0$ for all $i, j$. We define $V_{\text{eq}, j}(\beta)$ as the equilibrium policy value when the policy value is defined in terms of $Y_{\cdot, j}$ (Definition (ref)). We evaluate how well the methods maximize $V_{\text{eq}, j}(\beta)$ for $j=1,2,3.$ \begin{figure} \caption{We plot the equilibrium policy value obtained from iterates of strategy-aware and competition-aware methods.} \end{figure} \begin{table}[t] \begin{tabular}{c|c|c|c} Method &$\hat{V}_{\text{eq}, 1}(\hat{\beta})$ & $\hat{V}_{\text{eq}, 2}(\hat{\beta})$ & $\hat{V}_{\text{eq}, 3}(\hat{\beta})$ \\ \hline Capacity-Aware $\beta_{\text{cap}}$ & 3.87 $\pm$ 0.03 & 2.51 $\pm$ 0.15 & 1.62 $\pm$ 0.01 \\ Strategy-Aware (Model Gradient) $\beta_{\text{strat}}$ & 5.32 $\pm$ 0.22 & 2.63 $\pm$ 0.04 & 1.70 $\pm$ 0.02 \\ Competition-Aware (Policy Gradient) $\beta_{\text{comp}}$ & 5.87 $\pm$ 0.27 & 2.77 $\pm$ 0.03 & 2.38 $\pm$ 0.35 \end{tabular} \caption{The competition-aware method outperforms strategy-aware and capacity-aware baselines. A one-sided paired $t$ test yields a $p$-value of less than 9e-4 for $j=1, 2, 3$. } \end{table} \begin{figure} \caption{We plot the score distributions that are induced by $\beta_{\text{comp}}$, $\beta_{\text{strat}}$, $\beta_{\text{cap}}$ to maximize $V_{\text{eq}, j}(\beta)$ for $j=1, 2, 3$. We plot a histogram of scores for each agent with a distinct unobservable $(Z_{i}, c_{i})$. Agents are color-coded on according to low (yellow), medium (orange), and high (pink) relative SES. The selection criterion $\beta_{\text{comp}}$ accepts students with varying SES.} \end{figure} We generate a dataset of $n=14915$ students by sampling from our simulated distribution. For the capacity-aware baseline, we consider an RCT where treatments are assigned to $n$ students in order to estimate the CATE. For the gradient-based methods, we randomly initialize the policy and optimize $\beta$ via projected stochastic gradient descent (in our case, ascent because we aim to maximize the policy value) using Algorithm (ref). We assume that $n$ students are observed by the decision maker at each iteration, and we run the algorithm for 50 iterations. We run 10 random trials, where the randomness is over the initialization and sampled students. Across our experiments, the competition-aware policy is the most performant, and the strategy-aware policy is strong baseline (Table (ref)). Figure (ref) visualizes iterates of the gradient-based methods for maximizing $V_{\text{eq},j}(\beta)$ for $j=1, 2, 3.$ We note that the competition-aware method, which relies on the policy gradient estimator, can exhibit higher variance than the strategy-aware method, which relies on the model gradient estimator. While the policy gradient estimator consistently estimates the policy gradient, it targets a more complicated estimand and can have higher variance than the model gradient estimator, which does not consistently estimate the policy gradient. This is analogous to the related literature on estimating treatment effects under interference, where indirect effect estimators often have higher variance than direct effect estimators li2022random. When the objective is $V_{\text{eq}, 2}$, the competition-aware policy only yields a modest improvement over the baselines, despite that the three approaches admit different groups of students (Figure (ref)b). We attribute this to the observation that all students have similar values of $Y_{i, 2}(1)$. Among the students, the range of $Y_{i, 2}(1)$ is $5.56$, while the range of $Y_{i, 1}(1)$ is $23.5$, and the range of $Y_{i, 3}(1)$ is $10$. All three methods obtaining similar policy value when optimizing $V_{\text{eq}, 2}$ is an artefact of the fact that all students have $Y_{i, 2}(1)$ that are close in value. The learned policies for each combination of method and objective are given in Appendix (ref). Qualitatively, we find that when the objective is $V_{\text{eq}, 1}$, the most performant selection criterion favors students with high SES (Figure (ref)a, left). We observe that $Y_{i, 1}(1)$ is positively correlated with SES; the correlation between these variables is $0.44.$ When optimizing $V_{\text{eq}, 1}$, we find that $\beta_{\text{comp}}$ places high weight on most of $X_{i, \text{grades}}$ (except foreign language), which are features that students with high SES can manipulate. In contrast, when the objective is $V_{\text{eq}, 2},$ we find that the most performant selection criterion accepts students with varied socioeconomic background (Figure (ref)b left), and we find that the correlation between the outcome $Y_{i, 2}(1)$ and SES is $0.07$, so they are not strongly correlated. Finally, we find that when the objective is $V_{\text{eq}, 3},$ the most performant selection criterion accepts students with low socioeconomic background (Figure (ref)c, left), and we find that the correlation between $Y_{i, 3}(1)$ and SES is $-0.82,$ a strong negative correlation. The most performant policy for maximizing $V_{\text{eq}, 3}$ places negative or low magnitude weights on $X_{i, \text{grades}}$, which students with high SES can more easily modify. Here, we have illustrated that our policy gradient estimator can be used to optimize different possible objectives, and the distribution of students that are treated under the different policies will vary depending on the correlation between the outcome of interest with the students' unobservable types $(Z_{i}, c_{i})$. An additional insight from our empirical analysis is that the choice of outcome has a large impact on the learned policy.

section{Discussion} While there has been considerable recent interest on learning in the presence of strategic behavior, settings that also include capacity constraints have received less attention to date. The interplay of strategic behavior and capacity constraints can lead to effective competition between agents, thus leading to qualitatively different challenges in policy learning relative to the unconstrained setting. Furthermore, many motivating applications for learning with strategic behavior, such as college admissions and hiring, are precisely settings where the decision maker is capacity-constrained---thus highlighting the need for further work in this area. We adopt a flexible model where agents are heterogenous in their raw covariates and their ability to modify them. Depending on the context, strategic behavior may be harmful, beneficial, or neutral for the decision maker. In some applications, strategic behavior may be a form of “gaming the system,” e.g., cheating on exams in the context of college admissions, and the decision maker may not want to assign treatment to agents who have high ability to modify their covariates. In other applications, the decision maker may want to accept such agents because the agents who would benefit the most from the treatment are those who can invest effort to make themselves look desirable. Lastly, as demonstrated by liu2021strategic, when all agents have identical ability to modify their covariates, the strategic behavior may be neutral for the decision maker because it does not affect which agents are assigned treatment. Our model permits all of these interpretations because we allow for potential outcomes to be flexibly related to the agent's type. A number of questions remain open for further research. First, our model assumes that the decision maker's policy is fixed over time. Considering dynamic treatment rules, i.e., where the policy is time-varying, would extend this work and would likely lead to new types of equilibria. Second, we here considered linear policies because they are relevant to many real-world applications, such as the Chilean college admissions system santelices2019institution; but more flexible policies are possible. Third, we here assumed that agents are myopic. Future work may consider agents who respond to a history of thresholds $\{ s_{j} \}_{j \in [t-k, t]}$ instead of just $s_{t}$. Many models of agent behavior are possible in this case, e.g., an agent could respond to the mean of the thresholds or use the trend of the history to predict the next threshold and respond to the prediction. These different assumptions may yield different dynamics than the ones that we study. On the more technical side, one limitation of our model is that it does not permit an agent's post-effort covariates $X_{i}$ to exactly equal their raw covariates $Z_{i}$. For $X_{i}$ to be exactly equal to $Z_{i},$ the cost of covariate modification must be infinite for any deviation from $Z_{i}$. Our work here only considers cost functions that are twice-differentiable and lie in an $L^{2}$-space, but we expect that a more general proof strategy can relax these requirements. Relatedly, our model heavily relies on some form of noise being present in the system. If agents have a noisy understanding of the policy parameters jagadeesan2021alternative, or agents best respond imperfectly (as in our work), or exogenous noise affects how decisions are made kleinberg2018human, then best responses will be continuous. We expect our results to hold as long as there is sufficient exogenous noise in the system to guarantee that best responses are continuous--the source of the noise itself is not especially crucial. Here, for technical convenience we assume Gaussian noise, but we expect our results to apply to more generic noise distributions, provided they are mean-zero, twice-differentiable, and have bounded second derivative. Possible modifications of our model that could still allow for tractable equilibrium modeling include considering stochastic policies instead of deterministic ones, generic noise distributions, or the noisy response model of jagadeesan2021alternative. On the other hand, if there is no noise in the system, then the agents can strategize perfectly, yielding a discontinuous best response function. In some practical scenarios, such discontinuities are unnatural; see jagadeesan2021alternative for a number of examples. Nevertheless, it may still be interesting to develop procedures that perform well despite these discontinuities. Finally, it would be of considerable interest to study how our proposed approach behaves under misspecification of our model---and to develop simple verifiable heuristics for assessing whether our proposed method will find a solution that obtains significant gains over baselines that are oblivious to competition. While our policy gradient estimator is consistent in the absence of competition and strategic behavior, it may not be the simplest strategy if competition and strategic behavior are not first-order concerns. Thus, rules of thumb for detecting whether agents are strategic and whether competition effects are material to optimal decision making would be useful when considering practical application of the method.