Strategyproof Decision-Making in Panel Data Settings and Beyond

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

82,028 characters · 13 sections · 27 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

\affil[1]{Carnegie Mellon University} \affil[2]{Columbia University} \affil[3]{Massachusetts Institute of Technology} \affil[4]{Archimedes/Athena RC} \affil[ ]{\{keeganh, zstevenwu\}@cmu.edu} \affil[ ]{[email removed], [email removed]}

\pagenumbering{gobble} =

abstractWe consider the problem of decision-making using panel data, in which a decision-maker gets noisy, repeated measurements of multiple units (or agents). We consider the setup used in synthetic control methods, where there is a pre-intervention period when the principal observes the outcomes of each unit, after which the principal uses these observations to assign a treatment to each unit. Unlike this classical setting, we permit the units generating the panel data to be strategic, i.e. units may modify their pre-intervention outcomes in order to receive a more desirable intervention. The principal's goal is to design a strategyproof intervention policy, i.e. a policy that assigns units their \khedit{utility-maximizing} interventions despite their potential strategizing. We first identify a necessary and sufficient condition under which a strategyproof intervention policy exists, and provide a strategyproof mechanism with a simple closed form when one does exist. Along the way, we prove impossibility results for strategic multiclass classification, a natural extension of the well-studied (binary) strategic classification problem to the multiclass setting, which may be of independent interest. When there are two interventions, we establish that there always exists a strategyproof mechanism, and provide an algorithm for learning such a mechanism. For three or more interventions, we provide an algorithm for learning a strategyproof mechanism if there exists a sufficiently large gap in the principal's rewards between different interventions. Finally, we empirically evaluate our model using real-world panel data collected from product sales over 18 months. We find that our methods compare favorably to baselines which do not take strategic interactions into consideration, even in the presence of model misspecification.\looseness-1

\pagenumbering{arabic}

Introduction

In panel data (or longitudinal data) settings, one observes repeated, noisy, measurements of a collection of units over a period of time, during which the units undergo different interventions. For example, units can be individuals, companies, or geographic locations, and interventions can represent discounts, health therapies, or tax regulations. This is a ubiquitous way to collect data, and, as a result, the analysis of panel data has a long history in econometrics and statistics. A common goal in the literature is to analyze how a principal (e.g., business platform, regulatory agency) can do “counterfactual inference”, i.e., estimate what will happen to a unit if it undergoes a variety of possible interventions. The ultimate goal of such counterfactual inference is to enable data-driven decision-making, where one does not just estimate statistical parameters of interest, but actually uses data to make better decisions. In medical domains, for example, the goal typically is not just estimating health outcomes for patients under different health therapies, but also a policy that selects appropriate therapies for new patients. However, the leap from counterfactual inference to data-driven decision-making comes with additional challenges: namely, when units know that they will be assigned disparate interventions based on their reported data, they have incentives to strategize with their reports. Such strategic interactions in panel data settings are observed in practice. For example, caro2010zara observe that Zara store managers strategically misreported store inventory information to higher-ups in order to maximize sales at their local branch.\looseness-1

A running example we will use throughout this paper is that of an e-commerce platform that wishes to give one of several possible discounts (interventions) to a new user to maximize some future metric of interest, say, engagement levels. \khedit{In this example time-steps are days/weeks/months, units are users, and outcomes are engagement levels.\footnote{\khedit{Another motivating example is the incentives of store managers in inventory management, as discussed in caro2010zara. Here, time-steps are days/weeks/months, units are different products at a given store, outcomes are (reported) inventory levels, and interventions are different levels of discount.}}} Suppose the company uses historical data to build a model that estimates the “counterfactual” trajectory of engagement levels of a new user under different discount policies, based on their observed trajectory of engagement levels thus far. If a user knew this were the case, then there is a clear incentive for them to strategically modify their engagement levels to receive a larger discount. Such strategic manipulations in response to data-driven decision-making have been observed in other domains such as lending homonoff2021does and search engine optimization davis2006search. In this paper, we focus on strategyproof intervention policies, i.e., policies that assign the \khedit{utility-maximizing} treatment to the units despite them strategically altering their data. Concretely, we answer two questions:

{\centerline \em {\bf Q1:} Is it possible to design intervention policies that are robust to strategic modification of data by units to receive a more favorable intervention? We call such policies strategyproof.}

{\centerline \em {\bf Q2:} Can we leverage the structure typically present in panel data to derive computationally-efficient algorithms for learning strategyproof intervention policies?}

Towards answering both questions, and in line with the e-commerce example described above, we build upon the framework for counterfactual inference with panel data called synthetic interventions SI, which itself is a generalization of the canonical framework of synthetic control abadie2003economic, abadie2010synthetic. In both settings, there is a notion of a “pre-intervention” time period when all units are under control (i.e., no intervention), followed by a “post-intervention” time period, when each unit undergoes exactly one of many possible interventions (including control). Synthetic control methods can be used to estimate the counterfactual outcome if a unit did not undergo an intervention, i.e., remained under control. Given its simplicity, synthetic control has become a ubiquitous technique in econometrics to estimate counterfactuals under control in high-stakes domains including e-commerce, healthcare, and policy evaluation. Synthetic interventions is a generalization which allows one to estimate counterfactual outcomes not just under control, but also under intervention. Despite being a relatively new development, the synthetic interventions framework has been used by several companies across therapeutics, ride-sharing, and e-commerce, to estimate the best intervention for a given unit. Given the growing popularity of the synthetic control and synthetic interventions frameworks in high-stakes decision-making, an issue that will likely arise is the strategic manipulation of observed outcomes by units. In particular, just as in the e-commerce example, units have an incentive to manipulate their pre-intervention outcomes in order to get a more favorable intervention during the post-intervention period. Indeed, if such strategic manipulations are not taken into account, we establish that the synthetic interventions estimator can perform poorly---see (ref) for a formal example of such a scenario and (ref) for an empirical example based on real-world e-commerce data. The goal of the principal in such strategic settings is to assign the “correct” intervention to each unit---the intervention which maximizes some objective function such as total user engagement---during the post-intervention period, despite possible strategic manipulations to the unit's pre-treatment behavior. As we observe, this can be thought of as designing a mechanism for {\em strategyproof multi-class classification} with panel data. Although many of our results apply more broadly to strategyproof multi-class classification, we focus on panel data (and in particular the setup of synthetic control and synthetic interventions) due to its ubiquity and for concreteness.

Our Contributions

The first contribution of our work is a general framework for decision-making in the presence of strategic agents in the panel data setting. Our model is formally defined in Section (ref), but for the purposes of exposition, we outline it informally here as well. In our setting, a principal originally observes historical data from pre- and post- intervention outcomes of $n$ units. Each of these units $i \in \{1, \ldots, n\}$ is randomly assigned an intervention $d_i$ as in an A/B test (i.e., a randomized control trial), so they do not have incentive to strategize with their pre-intervention outcomes. After observing this historical data, the principal commits to an intervention policy $\pi$, which uses a unit's pre-intervention outcomes to assign its intervention during the post-intervention period. Then $m$ new units arrive and strategically modify their pre-treatment outcomes; units are allowed to move in a ball of radius $\delta$ around their true pre-intervention outcomes, but they are not further constrained. We call this behavior best-responding and formally define it in Definition (ref). Finally, the principal observes the altered pre-intervention outcomes, assigns interventions according to policy $\pi$, and collects the post-intervention rewards. The goal of the principal in this setting is to deploy a policy $\pi$ that is strategyproof, i.e., assigns the \khedit{utility-maximizing} intervention to each unit, despite the fact that they may have strategically modified their pre-intervention outcomes. We call this utility-maximizing intervention the unit's type.

Given that units know the principal's policy $\pi$ and they are allowed to best respond anywhere within $\delta$ of their true pre-intervention outcome, it may seem like {\bf Q1} has a negative answer. However, in Section (ref), we derive the necessary and sufficient conditions for a strategyproof intervention policy to exist. In order to obtain this full characterization, we translate our the principal's problem of assigning interventions to the dual space (i.e., the space of the units' actions), and derive properties that units of the same type must share.

Our next contribution is to specialize our characterization of strategyproof intervention policies to the setting where unit outcomes at each round are determined by a latent factor model. Under a latent factor model (a natural and popular assumption in panel data settings), unit outcomes under different interventions are linearly dependent on a unit latent factor (i.e, their type), as well as a latent vector that is time- and intervention-specific. In this specification, the rewards of the principal are linear in their (expected) pre-intervention outcomes, which implies the units are {\em linearly separable} based on their type. We show that our necessary and sufficient condition for a strategyproof intervention policy to exist is always satisfied when there are two interventions ((ref)), but it is in general not satisfied for three or more interventions ((ref)). The intuition for both results is that in order for an intervention policy to be strategyproof under the latent factor model, the principal has to shift the decision boundaries by some amount in order to account for the fact that units are able to strategize. When the number of interventions is more than two, it may be the case that there are units of different types whose pre-intervention outcomes are “close enough” to each other such that no movement of the boundary can prevent all units from fooling the principal. Importantly, in Section (ref) we show that assigning three or more interventions in a panel data setting with strategic agents can be interpreted as an instance of strategic multiclass classification, a natural generalization of the well-studied strategic (binary) classification problem to the multiclass setting. As such, our impossibility result for strategyproof intervention policies translates to an impossibility result for strategyproof classification with three or more classes. To the best of our knowledge, we are the first to both draw this connection, and discuss strategic multiclass classification altogether.

Having characterized strategyproof intervention policies under a latent factor model, we shift our focus to {\bf Q2}. For the case of two interventions (i.e a single treatment and control), we provide an algorithm for learning a strategyproof intervention policy from historical data ((ref)). The analysis of (ref) relies on two steps: First, we upper-bound the difference between the reward of the learned policy and that of the optimal policy by the estimation error on the rewards of the test units ((ref)). Second, we leverage bounds for estimation from the “error-in-variables” regression literature to derive end-to-end finite sample guarantees ((ref)). We show that under relatively minor algebraic assumptions, our intervention policy is asymptotically optimal in the limit of infinite data. Next, we provide analogous finite sample guarantees for an extension of (ref) to the setting with an arbitrary number of treatments ((ref))---under an additional assumption on the difference in rewards between the optimal and next-best intervention for each type of unit ((ref)). Relaxing this assumption on the reward gap appears challenging; we provide evidence for the necessity of such a condition in (ref).

Finally, we complement our theoretical results with experiments based on panel data from product sales at several stores over the course of 18 months. We find the data is well-approximated by a latent factor model, and that the intervention policy of (ref) outperforms a baseline policy which does not take strategic interactions into consideration---even when the algorithm's estimate of $\delta$ (the unit effort budget) is misspecified.

Related Work

Our work is broadly related to two lines of research in algorithmic game theory and econometrics: algorithmic decision-making under incentives and learning from panel data. \paragraph{Strategic responses to algorithmic decision making} A growing line of work at the intersection of computer science and economics aims to model the effects of using algorithmic assessment tools in high-stakes decision-making settings (e.g., hardt2016strategic,dong2018strategic, chen2020learning, kleinberg2020classifiers, shavit2020causal, munro2020learning, ahmadi2021strategic,bechavod2021gaming,bechavod2022information,ghalme2021strategic,harris2021bayesian,harris2021stateful,harris2022strategic,jagadeesan2021alternative, levanon2021strategic). hardt2016strategic introduce the problem of strategic classification, in which a “jury” (principal) deploys a classifier, and a “contestant” (agent), best-responds by strategically modifying their observable features. Subsequent work has studied online learning settings dong2018strategic,chen2020learning,ahmadi2021strategic, repeated interactions harris2021stateful, social learning settings bechavod2022information, and settings in which the model being used to make decisions is (partially) unknown to the strategic agents ghalme2021strategic, harris2021bayesian, bechavod2022information. Perhaps the line of work most relevant to ours is that of shavit2020causal,munro2020learning, bechavod2021gaming,harris2022strategic, which aims to identify causal relationships between observable features and outcomes in the presence of strategic responses to various linear models. In contrast, we study a panel data setting in which the principal must assign one of several interventions to strategic units based on longitudinal data which may not have any underlying linear structure. In Appendix (ref), we discuss the connections between our panel data setting and that of multiclass strategic classification. In particular, intervening on strategic units which exhibit a latent factor model structure may be viewed as a particular instance of multiclass classification where agents strategically modify their observable features. We are the first to study such a multiclass strategic classification setting, to the best of our knowledge, and we find that new ideas are required to handle the multiclass nature of the decision-making problem at hand.\looseness-1

\paragraph{Panel data methods in econometrics} As stated earlier, this is a setting where one gets repeated measurements of multiple heterogeneous units over time. Prominent frameworks for causal estimation using panel data include difference-in-differences ashenfelter1984using, bertrand2004much, harmless_econometrics and synthetic control methods abadie2003economic, abadie2010synthetic, Hsiao12, imbens16, athey1, LiBell17, xu_2017, rsc, mrsc, Li18, ark, bai2020matrix, asc, Kwok20, chernozhukov2020practical, fernandezval2020lowrank, agarwal2020robustness, agarwal2020principal. In these frameworks, there is a notion of a “pre-intervention” period where all the units are under control (i.e, no intervention), after which a subset of units receive one of many possible interventions. The goal of these works is to estimate what would have happened to a unit that undergoes an intervention (i.e., a “treated” unit) if it had remained under control (i.e., no intervention), in the potential presence of unobserved confounding. That is, they estimate the counterfactual if a treated unit remains under control for all $T$ time-steps. A critical aspect that enables the methods above is the structure between units and time under control. One elegant encoding of this structure is through a latent factor model (also known as an interactive fixed effect model), chamberlain, liang_zeger, arellano, bai03, bai09, pesaran, moon_15, moon_weidner_2017. In such models, it is posited that there exist low-dimensional latent unit and time factors that capture unit- and time-specific heterogeneity, respectively, in the potential outcomes. Since the goal in these works is to estimate outcomes under control, no structure is imposed on the potential outcomes under intervention. In SI, agarwal2021causal, the authors extend this latent factor model to incorporate latent factorization across interventions as well, which allows for identification and estimation of counterfactual mean outcomes under intervention rather than just under control. In essence, we extend these previous works to allow for the pre-intervention outcomes to be strategically manipulated by units to receive a more favorable intervention. What we find noteworthy is that the latent factor model typically assumed in these settings leads to strategyproof estimators that have a simple closed form.\looseness-1

Model: Strategic Interactions in Panel Data Settings

\paragraph{Notation} Subscripts are used to index the unit and time-step, superscripts are reserved for interventions. We use $i$ to index units, $t$ time-steps, and $d$ interventions. For $x \in \mathbb{N}$, we use the shorthand $[\![x]\!] := \{1, 2, \ldots, x\}$ and $[\![x]\!]_0 := \{0, 1, \ldots, x-1\}$. Finally, all proofs which are not in the main body may be found in the Appendix.

\paragraph{Decision making in panel data settings} Consider a setting in which the principal observes the outcomes of $m$ units for $T$ time-steps, where $\pv{y}{d}_{i,t} \in \mathbb{R}$ is the outcome of unit $i$ at time $t$ under intervention $d$. We assume that unit outcomes are generated via a latent factor model, a popular assumption in the panel data setting (e.g., references in (ref)). Most work in panel data with latent factor models assumes there is measurement noise in the outcomes. While we consider settings with measurement noise in (ref), our results in (ref) do not depend on this noise and so we present a simpler setup here without noise for ease of exposition.

assumption[Latent Factor Model] The outcome for unit $i$ at time $t$ under treatment $d \in [\![k]\!]_0$ is \begin{equation*} y_{i,t}^{(d)} = \langle \mathbf{u}_t^{(d)}, \mathbf{v}_i \rangle, \end{equation*} where $\mathbf{u}_t^{(d)} \in \mathbb{R}^s$ is a latent factor which depends only on time $t$ and intervention $d$, and $\mathbf{v}_i \in \mathbb{R}^s$ is a latent factor which only depends on unit $i$. For simplicity, we assume $|\pv{y}{d}_{i,t}| \leq 1$.\looseness-1

Note that (ref) does not require the principal to know $\mathbf{u}_t^{(d)}$ or $\mathbf{v}_i$\khedit{, and that $y_{i,t}^{(d)}$ is observed for only one intervention $d \in [\![k]\!]_0$}. We assume that the latent dimension $s$ is known to the principal for ease of analysis, although several principled heuristics exist for estimating $s$ in practice from data (see, e.g. SI for details).

Consider a pre-intervention period of $T_0$ time-steps, for which each unit is under the same intervention, i.e., under control. After the pre-intervention period, the principal assigns an intervention $d_i \in [\![k]\!]_0$ to each unit $i \in [\![m]\!]$. Without loss of generality, we denote control by $d=0$. Once assigned intervention $d_i$, unit $i$ remains under $d_i$ for the remaining $T-T_0$ time-steps. We use

equation*[equation* omitted — 109 chars of source]

to refer to the set of unit $i$'s pre-treatment {\em observed} outcomes under control, and

equation*[equation* omitted — 122 chars of source]

to refer to the set of unit $i$'s post-intervention {\em potential} outcomes under intervention $d$. We denote the set of possible pre-treatment outcomes by $\mathcal{Y}_{pre}$.

definition[Intervention Policy] An intervention policy $\pi: \mathcal{Y}_{pre} \rightarrow [\![k]\!]_0$ is a (deterministic) mapping from pre-treatment outcomes to interventions.

For a given unit $i$, we denote the intervention assigned to them by intervention policy $\pi$ as $d_i^{\pi}$.\footnote{We sometimes use the shorthand $d_i = d_i^{\pi}$ when the intervention policy is clear from the context.} Given an intervention policy $\pi$, units may have an incentive to strategically modify their pre-treatment outcomes in order to receive a more desirable intervention. In our e-commerce example, this would correspond to users strategically modifying their engagement levels for the pre-intervention period (e.g., by artificially reducing their time spent on the platform), to “trick” the online marketplace into assigning them a higher discount than the one which would maximize the marketplace's revenue in the post-intervention period. More generally, we study a game between a principal and a population of units. The principal moves first by committing to an intervention policy. Each unit then best-responds to the given intervention policy by strategically modifying their pre-intervention outcomes as follows:

definition[Strategic Responses to Intervention Policies] Assume that interventions are ordered in increasing unit preference (i.e., units prefer $d$ to $d'$ for $d > d'$). Given an intervention policy $\pi: \mathcal{Y}_{pre} \rightarrow [\![k]\!]_0$, unit $i$ best-responds to $\pi$ by modifying their pre-treatment outcomes as \begin{equation*} \begin{aligned} \Tilde{\mathbf{y}}_{i,pre} \in \; &\arg\max_{\widehat{\mathbf{y}}_{i,pre} \in \mathcal{Y}_{pre}} \;\; \pi(\widehat{\mathbf{y}}_{i,pre})\\ s.t. \;\; &\| \widehat{\mathbf{y}}_{i,pre} - \mathbf{y}_{i,pre}\|_2 \leq \delta, \end{aligned} \end{equation*} where $\delta \in \mathbb{R}_{>0}$ is the unit effort budget and is known to the principal. We assume that if a unit is indifferent between two modifications, they chose the one which requires the smallest effort investment.

By (ref), the goal of each unit is to obtain the most desirable intervention possible when interventions are assigned according to $\pi$, subject to the constraint that their modification is bounded in $\ell_2$ norm by $\delta$. Such budget assumptions are common in the literature on algorithmic decision making in the presence of strategic agents (e.g., chen2020learning,kleinberg2020classifiers,harris2021stateful, harris2023strategic), and are useful for modeling “hard constraints” in a unit's ability to manipulate. For example, in some settings the manipulation of pre-treatment outcomes may have some associated monetary cost, and units may have a fixed budget which they cannot exceed. In other settings the manipulation of pre-treatment outcomes may take time, and the $\delta$-ball represents the set of all possible pre-treatment outcomes a unit could achieve in the amount of time in the pre-treatment period. Given (ref), the goal of the principal is to design an intervention policy to maximize their reward in the presence of such strategic manipulations.\looseness-1

definition(Principal Reward) The principal's reward for unit $i$ under intervention $d$ is a weighted sum of unit $i$'s outcomes in the post-treatment time period. Specifically \begin{equation*} r_i^{(d)} = \sum_{t = T_0 + 1}^T \omega_t \cdot y_{i,t}^{(d)}, \end{equation*} where $\omega_t \in \mathbb{R}$ for $t > T_0$ are known to the principal.

Linear rewards can capture many settings; e.g. in e-commerce, the online marketplace may wish to maximize the total amount of user engagement on the platform in the post-intervention period (this corresponds to $\omega_{t} = 1$ for $t > T_0$).

definition[Unit Type] We say that unit $i$ is of type $d$ (with respect to the principal's reward) if assigning them intervention $d$ maximizes the principal's reward. Formally, unit $i$ is of type $d$ if \begin{equation*} d \in \arg\max_{d' \in [\![k]\!]_0} \pv{r}{d'}_i, \end{equation*} where $\pv{r}{d'}_i$ is defined as in (ref).

While in general the principal's reward for a unit $i$ may be a function of all of unit $i$'s outcomes (not just those in the post-intervention period), we only consider intervention policies which intervene after a fixed pre-treatment time period (for which all units are under control), in line with the synthetic interventions and synthetic controls literature. As we show, the principal's reward for a given unit may be rewritten as a function of that unit's pre-treatment outcomes when an additional linear span assumption is satisfied.

assumption[Linear Span Inclusion] Consider the latent factor model of (ref). We assume that \begin{equation*} \sum_{t=T_0+1}^T \omega_t \cdot \pv{\mathbf{u}}{d}_t \in \mathrm{span}\{\pv{\mathbf{u}}{0}_1, \ldots, \pv{\mathbf{u}}{0}_{T_0} \}. \end{equation*}

(ref) can be viewed as a form of “causal transportability” over time which allows the principal to learn something about potential outcomes in the post-intervention time period from the pre-intervention time period. Such assumptions are fairly common in the literature on learning from panel data (e.g. amjad2018robust,SI).

Next we show that under (ref) and (ref), the principal's reward can be written as a function of their pre-intervention outcomes under control. This will be a useful structural condition for later results.

lemma[Reward Reformulation] Under (ref), $r_i^{(d)}$ may be rewritten as \begin{equation*} r_i^{(d)} = \langle \pv{\boldsymbol{\beta}}{d}, \mathbf{y}_{i,pre} \rangle, \end{equation*} for some $\pv{\boldsymbol{\beta}}{d} \in \mathbb{R}^{T_0}$, where $\mathbf{y}_{i,pre}$ are the (unmodified) pre-intervention outcomes for unit $i$.

proofFrom (ref) and (ref), \begin{equation*} \begin{aligned} r_i^{(d)} = \left \langle \sum_{t = T_0 + 1}^T \omega_t \cdot \mathbf{u}_t^{(d)}, \mathbf{v}_i \right \rangle. \end{aligned} \end{equation*} Applying $\sum_{t=T_0+1}^T \omega_t \cdot \pv{\mathbf{u}}{d}_t \in \mathrm{span}(\{\pv{\mathbf{u}}{0}_1, \ldots, \pv{\mathbf{u}}{0}_{T_0} \})$, we may rewrite $r_i^{(d)}$ as \begin{equation*} \begin{aligned} r_i^{(d)} = \left \langle \sum_{t = 1}^{T_0} \pv{\beta}{d}_t \cdot \mathbf{u}_t^{(0)}, \mathbf{v}_i \right \rangle \end{aligned} \end{equation*} for some $\pv{\boldsymbol{\beta}}{d} = [\pv{\beta}{d}_1, \ldots, \pv{\beta}{d}_{T_0}]^\top \in \mathbb{R}^{T_0}$.

Observe that any strategic modification by a unit in the pre-intervention period does not change their latent factor $\mathbf{v}$ (or therefore, their post-intervention outcomes). Given knowledge of a unit's latent factor, it would be trivial for the principal to assign them their \khedit{utility-maximizing} intervention. However, this knowledge is usually not available; instead it must be estimated from the unit's (strategically modified) pre-treatment behavior. Therefore, we are interested in characterizing and learning intervention policies which assign the \khedit{utility-maximizing} intervention to each unit in the presence of strategic manipulations. Borrowing language from the game theory literature, we refer to such intervention policies as strategyproof.\looseness-1

definition[Strategyproof Intervention Policy] An intervention policy $\pi$ is strategyproof if \begin{equation*} \pi(\Tilde{\mathbf{y}}_{i,pre}) = \arg \max_{d \in [\![k]\!]_0} \pv{r}{d}_i \end{equation*} for every unit $i$, where $\Tilde{\mathbf{y}}_{i,pre} \in \mathbb{R}^{T_0}$ are unit $i$'s strategically-modified pre-treatment outcomes according to (ref).

See (ref) for a summary of the setting we consider.

figure[figure omitted — 1,242 chars of source]

Background on Principal Component Regression (PCR)

Several of our results in (ref) leverage principal component regression (PCR) jolliffe1982note to obtain end-to-end finite sample guarantees. At a high level, PCR learns a linear relationship between covariates and outcomes by first “de-noising” the covariates via hard singular value thresholding, then learning a linear relationship between the de-noised covariates and the outcome of interest. Formally, let $$\pv{Y}{d}_{pre} := [\mathbf{y}_{i,pre}^\top : i \in \pv{\mathcal{N}}{d}] \in \mathbb{R}^{\pv{n}{d} \times T_0}$$ and denote the singular value decomposition of $\pv{Y}{d}_{pre}$ as $$\pv{Y}{d}_{pre} = \sum_{l=1}^{\pv{n}{d} \wedge T_0} \pv{s}{d}_l \pv{\widehat{\mathbf{u}}}{d}_l (\pv{\widehat{\mathbf{v}}}{d}_l)^\top,$$ where $\pv{s}{d}_l \in \mathbb{R}$ is the $l$-th singular value, $\pv{\widehat{\mathbf{u}}}{d}_l \in \mathbb{R}^{\pv{n}{d}}$ is the $l$-th left singular vector, and $\pv{\widehat{\mathbf{v}}}{d}_l \in \mathbb{R}^{T_0}$ is the $l$-th right singular vector. Denote the vector of observed principal rewards under intervention $d$ as $$\pv{\mathbf{r}}{d} := [\pv{r}{d}_i: i \in \pv{\mathcal{N}}{d}]^\top \in \mathbb{R}^{\pv{n}{d}}.$$ For a given hyperparameter $p \leq \pv{n}{d} \wedge T_0$, we can use PCR to estimate $\pv{\boldsymbol{\beta}}{d}$ as

equation*[equation* omitted — 546 chars of source]

Characterizing Strategyproof Intervention Policies

We now turn our attention to the problem of characterizing strategyproof intervention policies. In other words, we are interested in (1) deriving conditions under which strategyproof intervention policies do or do not exist, and (2) characterizing the form of strategyproof intervention policies whenever they do exist. In (ref), we focus on the problem of learning strategyproof intervention policies from historical data.

We begin by deriving a necessary and sufficient condition for a strategyproof intervention policy to exist. In order to characterize this condition, we need to first introduce the notion of a best-response ball.

definition[Best-Response Ball] The best-response ball of a set of units $\mathcal{U}$ is the set of all pre-intervention outcomes $\Tilde{\mathcal{Y}}_{pre}(\mathcal{U})$ such that \begin{equation*} \Tilde{\mathbf{y}}_{pre} \in \Tilde{\mathcal{Y}}_{pre}(\mathcal{U}) \; if \; \left\| \Tilde{\mathbf{y}}_{pre} - \mathbf{y}_{i, pre} \right\|_2 \leq \delta for any unit i \in \mathcal{U}, \end{equation*} where $\mathbf{y}_{i,pre} \in \mathcal{Y}_{pre}$ denotes the unmodified pre-intervention outcomes associated with unit $i$.

The best-response ball for an individual unit is its set of feasible modifications according to (ref). The best-response ball for a set of units is the union of the best-response balls of all units contained within the set. Equipped with this definition, we are now ready to introduce our sufficient and necessary condition, which we call separation of types.\looseness-1

condition[Separation of Types] For a given problem instance, let $\pv{\mathcal{U}}{d}$ denote the set of all units of type $d$ (recall (ref)). Separation of types is satisfied if\looseness-1 \begin{equation*} \forall d \in [\![k]\!]_0, \; \not \exists \; i \in \pv{\mathcal{U}}{d} s.t. \Tilde{\mathcal{Y}}_{pre}(i) \subseteq \bigcup_{d' = 0}^{d-1} \Tilde{\mathcal{Y}}_{pre}(\pv{\mathcal{U}}{d'}). \end{equation*}

In other words, separation of types is satisfied if for all interventions $d \in [\![k]\!]_0$, there does not exist any unit $i$ of type $d$ whose best-response ball $\Tilde{\mathcal{Y}}_{pre}(i)$ is a complete subset of the union of best-response balls of units with types less than $d$.

theoremSeparation of types ((ref)) is both necessary and sufficient for a strategyproof intervention policy (as defined in (ref)) to exist.

\khedit{As the effort budget $\delta$ grows, both $\Tilde{\mathcal{Y}}_{pre}(i)$ and $\bigcup_{d' = 0}^{d-1} \Tilde{\mathcal{Y}}_{pre}(\pv{\mathcal{U}}{d'})$ become larger, which makes (ref) harder to satisfy.} Necessity follows from leveraging (ref) to show that if (ref) does not hold, there will always be at least one unit who can strategize to receive a better intervention. We show sufficiency by giving a strategyproof intervention policy when (ref) holds. The following two lemmas cover the necessity and sufficiency cases and immediately imply (ref).

lemma[Necessity] Suppose separation of types ((ref)) does not hold. Then there exists no mapping $\pi: \mathcal{Y}_{pre} \rightarrow [\![k]\!]_0$ which can intervene perfectly on all unit types.

Intuitively, separation of types is necessary because if it does not hold, then there always exists at least one unit of a lower type that can always “pretend” to be of higher type, thus leading the principal to intervene incorrectly on some subset of the population.

proofAssume that separation of types ((ref)) is violated for some unit $i$ of type $d$. Since $\mathcal{Y}_{pre}(i) \subseteq \bigcup_{d' = 0}^{d-1} \mathcal{Y}_{pre}(\pv{\mathcal{U}}{d'})$, any valid modified pre-treatment behavior of unit $i$ can also be obtained by some other unit $i' \in \bigcup_{d' = 0}^{d-1} \pv{\mathcal{U}}{d'}$ by (ref). Therefore, no policy which assigns interventions according to a unit's observed pre-treatment outcomes can perfectly intervene on both $\pv{\mathcal{U}}{d}$ and $\{\pv{\mathcal{U}}{d'}\}_{d'=1}^{d-1}$.

Next we show that separation of types is sufficient for a strategyproof intervention policy to exist, by providing a strategyproof intervention policy whenever separation of types holds. Recall that strategyproofness is defined with respect to whether the intervention assigned to a unit matches its type and not with respect to whether modification of the pre-treatment outcomes takes place.

lemma[Sufficiency] Suppose separation of types ((ref)) holds. Then the following intervention policy is strategyproof:\looseness-1 Assign intervention $d_i$ to unit $i$, where \begin{equation} d_i = \min\{d \in [\![k]\!]_0 \; : \; \Tilde{\mathbf{y}}_{i,pre} \in \mathcal{Y}_{pre}(\pv{\mathcal{U}}{d}) \} \end{equation}

proofNo unit of type $d' < d$ can receive intervention $d$ by construction, since their pre-treatment outcomes will be in $\mathcal{Y}_{pre}(\pv{\mathcal{U}}{d'})$ by definition. Therefore, it suffices to show that any unit of type $d$ can receive intervention $d$. Consider a unit $i$ of type $d$. Since (ref) holds, we know that there exists a vector of pre-treatment outcomes $\Tilde{\mathbf{y}}_{pre} \in \mathcal{Y}_{pre}(i)$ such that $\Tilde{\mathbf{y}}_{pre} \not \in \bigcup_{d' = 0}^{d-1} \mathcal{Y}_{pre}(\pv{\mathcal{U}}{d'})$. \looseness-1 Since $\mathcal{Y}_{pre}(i) \subseteq \mathcal{Y}_{pre}(\pv{\mathcal{U}}{d})$, unit $i$ can receive intervention $d$ by strategically modifying their pre-treatment outcomes to $\Tilde{\mathbf{y}}_{pre}$.

We will revisit the computational complexity of evaluating this policy later in the section. In the remainder of the section, we aim to shed some light on the significance of (ref) by describing situations in which it does/does not hold in our panel data setting of interest. We begin by showing that (ref) always holds in the important special case when there is only a single treatment and control.

theoremIf $d \in \{0, 1\}$, separation of types ((ref)) always holds under (ref) and (ref). Moreover, the following closed-form intervention policy is strategyproof: Assign intervention $d_i$ to unit $i$, where \begin{equation} \begin{aligned} d_i &= \begin{cases} 1 \;\; if \;\; \langle \pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0}, \Tilde{\mathbf{y}}_{i,pre} \rangle - \delta \| \pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0} \|_2 > 0\\ 0 \;\; otherwise \end{cases} \end{aligned} \end{equation} We call $\langle \pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0}, \Tilde{\mathbf{y}}_{i,pre} \rangle - \delta \| \pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0} \|_2 = 0$ the decision boundary between interventions $0$ and $1$.\looseness-1

proofIf $d \in \{0, 1\}$,we can simplify (ref) to \begin{equation*} \not \exists \; i \in \pv{\mathcal{U}}{1} s.t. \mathcal{Y}_{pre}(i) \subseteq \mathcal{Y}_{pre}(\pv{\mathcal{U}}{0}). \end{equation*} By the reward reformulation ((ref)), $\pv{\mathcal{U}}{0}$ and $\pv{\mathcal{U}}{1}$ are separated by a single hyperplane: $\langle \pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0}, \Tilde{\mathbf{y}}_{pre} \rangle = 0$. Therefore, by the definition of best-response ball ((ref)), this simplified version of separation of types must always hold, and a strategyproof intervention policy may be obtained by shifting the hyperplane $\langle \pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0}, \Tilde{\mathbf{y}}_{pre} \rangle = 0$ by $\delta$ (the unit effort budget) in the direction of $\pv{\boldsymbol{\beta}}{0} - \pv{\boldsymbol{\beta}}{1}$. Note that such an intervention policy is strategyproof since there exists at least one valid modification of pre-treatment outcomes for all units of type $1$ to receive treatment (namely, $\Tilde{\mathbf{y}}_{pre} = \mathbf{y}_{pre} + \delta \cdot (\pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0}) / \|\pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0}\|_2$), and there exists no valid modification of pre-treatment outcomes for any unit of type $0$ to receive treatment (due to (ref)).

figure[figure omitted — 805 chars of source]

See (ref) for an illustration of a strategyproof intervention policy in the binary intervention setting. Intuitively, the idea of (ref) is to shift the true decision boundary in such a way to account for potential manipulations. While this shift prevents units from “gaming” the policy to receive the intervention when it is not in the principal's best interest, it may require some units who should receive the intervention to strategize in order to do so. Perhaps somewhat surprisingly, this line of reasoning does not carry over to the setting where there are more than two treatments.

theoremThere exists an instance with three interventions such that (ref) is not satisfied.

figure[figure omitted — 493 chars of source]

See (ref) for a visualization of one such setting. At a high level, (ref) cannot hold in this example since the decision boundaries $\langle \pv{\boldsymbol{\beta}}{2} - \pv{\boldsymbol{\beta}}{0}, \Tilde{\mathbf{y}}_{i,pre} \rangle = 0$ and $\langle \pv{\boldsymbol{\beta}}{1} - \pv{\boldsymbol{\beta}}{0}, \Tilde{\mathbf{y}}_{i,pre} \rangle = 0$ must both be shifted by $\delta$ in order to prevent some units from strategizing to receive intervention $2$. However, this prevents other units who should receive intervention $2$ from receiving it, since the amount that they would need to modify their pre-intervention outcomes under these shifts is strictly greater than $\delta$. We conclude this section by providing a strategyproof intervention policy for an arbitrary number of interventions whenever separation of types is satisfied.

theoremWhen (ref) is satisfied, the following intervention policy is strategyproof and can be evaluated in time polynomial in $T_0$ and $k$ under (ref) and (ref): Assign intervention $d_i$ to unit $i$, where \begin{equation*} d_i = \min\{d \in [\![k]\!]_0 \; : \; \Tilde{\mathbf{y}}_{i,pre} \in \Tilde{\mathcal{Y}}_{pre}(\pv{\mathcal{U}}{d}) \}. \end{equation*}

proof[Proof sketch] The form of the above intervention policy follows from the proof of sufficiency in (ref). We show that membership to the set $\Tilde{\mathcal{Y}}_{pre}(\pv{\mathcal{U}}{d})$ can be checked by solving a (convex) quadratic program (QP) with polynomial size, which implies that $d_i$ can be computed by solving at most $k$ such QPs.

proofObserve that by using the reward reformulation ((ref)), the definition of a best-response ball ((ref)) may be rewritten as \begin{equation*} \begin{aligned} \Tilde{\mathbf{y}}_{pre} \in \mathcal{Y}_{pre}(\mathcal{U}) \; if \; &\left\| \Tilde{\mathbf{y}}_{pre} - \mathbf{y}_{pre} \right\|_2 \leq \delta\\ for any \mathbf{y}_{pre} \in \mathcal{Y}_{pre} such that \; \langle &\pv{\boldsymbol{\beta}}{d} - \pv{\boldsymbol{\beta}}{d'}, \mathbf{y}_{pre} \rangle \geq 0 \; for all \; d' \in [\![k]\!]_0. \end{aligned} \end{equation*} Therefore, $\Tilde{\mathbf{y}}_{pre} \in \mathcal{Y}_{pre}(\mathcal{U})$ if and only if $\pv{OPT}{d}$ is at most $\delta$, where \begin{equation} \begin{aligned} \pv{OPT}{d} := \min_{\widehat \mathbf{y}_{pre}} \;\; &\| \widehat \mathbf{y}_{pre} - \Tilde{\mathbf{y}}_{pre} \|_2 \\ s.t. \;\; \langle &\pv{\boldsymbol{\beta}}{d} - \pv{\boldsymbol{\beta}}{d'}, \widehat \mathbf{y}_{pre} \rangle \geq 0 \; for all \; d' \in [\![k]\!]_0. \end{aligned} \end{equation}

Implications for Strategic Multiclass Classification

We now highlight an impossibility result for the problem of strategic multiclass classification, which readily follows from (ref) and may be of independent interest. For the reader who is uninterested in strategic classification, this subsection may be skipped without any loss in continuity.

\paragraph{Background on strategic classification} When subjugated to algorithmic decision making, decision subjects (agents) have an incentive to strategically modify their input to the algorithm in order to receive a more desirable prediction. In the context of machine learning models, such settings have been formalized in the literature under the name of strategic classification (see, e.g., hardt2016strategic, dong2018strategic, chen2020learning). In the strategic (binary) classification setting, the principal commits to an assessment rule (usually a linear model), which maps from observable features to binary predictions. Using knowledge of the assessment rule, strategic agents may modify their observable features in order to maximize their chances of receiving a desirable classification, subject to some constraint on the amount of modification which is possible (e.g., a best-response analogous to our (ref)). Given an agent's modified features, the principal uses their assessment rule to make a prediction about the agent. After the prediction is made, the principal receives some feedback about how accurate the assessment rule's prediction was. Under such a setting, the goal of the principal is to deploy an assessment rule with high accuracy on strategic agents.\looseness-1

\paragraph{Impossibility result} Using ideas similar to those used in (ref), we show that an impossibility result holds for the multiclass generalization of the strategic (binary) classification setting, where each strategic agent now belongs to one of $k \geq 3$ classes (as opposed to the binary setting, where $k=2$). We consider a setting in which a principal interacts with $m$ strategic agents. Each agent $i$ has a set of initial observable features $\mathbf{y}_{i} \in \mathcal{Y}$\footnote{Our notation is different than the standard one adopted in the strategic classification literature in order to best match the notation from the rest of the paper.}. These features are privately observable by the agents and they are not revealed to the principal. Instead, the agents report features $\Tilde{\mathbf{y}}_{i} \in \mathcal{Y}$ to the principal, which may be strategically modified. Given observed features $\Tilde{\mathbf{y}}_{i}$, the principal makes a prediction $d_{i}$ from some set of possible classes $[\![k]\!]_0$. We assume that each agent has some true label $d_{i}^*$, and the principal receives reward $1$ if $d_{i} = d_{i}^*$ and reward $0$ otherwise. In contrast to the principal's reward, we assume that each agent's reward $r^A_{i}(d)$ is a function of the prediction alone, i.e., $r^A_{i}(d) = r^A(d), \forall i \in [\![m]\!]$, and is known to the principal.\footnote{This generalizes the typical assumption made in strategic binary classification, where it is assumed that agents prefer the positive label to the negative one.}

The principal's assessment rule $\pi: \mathcal{Y} \rightarrow [\![k]\!]_0$ is a mapping from observable features to predictions. In particular, given a set of training data consisting of $\{(\mathbf{y}_i, d_i)\}_{i=1}^n$ pairs from $n$ non-strategic agents, the goal of the principal is to deploy an assessment rule which minimizes the out-of-sample error on $m$ strategic units.

figure[figure omitted — 1,085 chars of source]

definition[Out-of-sample error] The out-of-sample error of a policy $\pi$ is defined as the empirical probability that $\pi$ makes an incorrect prediction on the $m$ test agents. Formally, \begin{equation*} \frac{1}{m} \sum_{i=n+1}^{n+m} \mathbbm{1}\{d_{i} \neq d_{i}^*\} \end{equation*}

Given a principal policy $\pi$, it is natural for an agent to modify their observable features in a way which maximizes their reward. Specifically, we assume that agent $i$ strategically modifies their observable features based on the principal's policy, subject to a constraint on the amount of modification which is possible. In addition to being a common assumption in the strategic classification literature, this budget constraint on the amount an agent can modify their features reflects the fact that agents have inherent constraints on the amount of time and resources they can spend on modification.

assumption[Agent Best Response] We assume that agent $i$ best-responds to the principal's policy $\pi$ in order to maximize their expected reward, subject to the constraint that their modified observable features $\Tilde{\mathbf{y}}_{i}$ are within an $\ell_2$ ball of radius $\delta$ of their initial observable features $\mathbf{y}_{i}$. Formally, we assume that agent $i$ solves the following optimization to determine their modified observable features: \begin{equation*} \begin{aligned} \Tilde{\mathbf{y}}_{i} \in &\arg \max_{\widehat{\mathbf{y}}_{i} \in \mathcal{Y}} \; r^A(\pi(\widehat{\mathbf{y}}_{i}))\\ s.t. \; &\|\widehat{\mathbf{y}}_{i} - \mathbf{y}_{i} \|_2 \leq \delta \end{aligned} \end{equation*}

Furthermore, we assume that if an agent is indifferent between modifying their observable features and not modifying, they choose not to modify. This assumption is analogous to how we define the unit best response in (ref). See Figure (ref) for a summary of the setting we consider. We are now ready to present our main result for strategic multiclass classification, which follows straightforwardly from (ref) and is visualized in (ref).

corollarySuppose $\mathcal{Y} = \mathbb{R}^2$, $k = 3$, and $r^A(2) > r^A(1) = r^A(0)$. For the following labeling over $\mathcal{Y}$, there exists a distribution over agents such that no policy can achieve perfect classification if agents strategically modify according to (ref): \begin{equation*} d_{i}^* = \begin{cases} 0 \;\; &if \langle \boldsymbol{\beta}_{10}, \mathbf{y}_{i} \rangle < 0 and \langle \boldsymbol{\beta}_{20}, \mathbf{y}_{i} \rangle < 0\\ 1 \;\; &if \langle \boldsymbol{\beta}_{21}, \mathbf{y}_{i} \rangle < 0 and \langle \boldsymbol{\beta}_{10}, \mathbf{y}_{i} \rangle \geq 0\\ 2 \;\; &if \langle \boldsymbol{\beta}_{21}, \mathbf{y}_{i} \rangle \geq 0 and \langle \boldsymbol{\beta}_{20}, \mathbf{y}_{i} \rangle \geq 0\\ \end{cases} \end{equation*} where $\boldsymbol{\beta}_{20} = [1 \; 0.5]^\top$, $\boldsymbol{\beta}_{21} = [-1 \; 0.5]^\top$, and $\boldsymbol{\beta}_{10} = [2 \; 0]^\top$.

Learning Strategyproof Intervention Policies

algorithm[algorithm omitted — 1,210 chars of source]

We now shift our focus from characterizing strategyproof intervention policies to learning them from historical data. We assume that the historical data has not been strategically modified, as is the case when, e.g., interventions are assigned according to a randomized control trial (since in such settings, units do not have an incentive to strategize). While (ref) provides a characterization of a strategyproof intervention policy when one exists, deploying such an intervention policy requires knowledge of the underlying relationships between pre-treatment outcomes and principal rewards, which may not be known a priori. Additionally, it may be unreasonable to assume that the latent factor model holds exactly, due to measurement error or randomness in the outcomes of each unit.\footnote{In our e-commerce example, noise may be due to randomness in day-to-day engagement with the platform.\looseness-1} With this in mind, we overload the notation of $\pv{y}{d}_{i,t}$ and consider the following relaxation of (ref) throughout the sequel.

assumption[Latent Factor Model; revisited] Suppose the outcome for unit $i$ at time $t$ under treatment $d \in [\![k]\!]_0$ takes the following factorized form: \begin{equation*} \begin{aligned} \mathbb E[y_{i,t}^{(d)}] &= \langle \mathbf{u}_t^{(d)}, \mathbf{v}_i \rangle\\ and \;\; \pv{y}{d}_{i,t} &= \mathbb E[y_{i,t}^{(d)}] + \varepsilon_{i,t}, \end{aligned} \end{equation*} where $\mathbf{u}_t^{(d)} \in \mathbb{R}^s$ and $\mathbf{v}_i \in \mathbb{R}^s$ are defined as in (ref), and $\varepsilon_{i,t}$ is zero-mean sub-Gaussian random noise with variance at most $\sigma^2$. For simplicity, we assume that $|\mathbb E[y_{i,t}^{(d)}]| \leq 1$.

Note that under (ref), the reward reformulation ((ref)) now holds in expectation. Inspired by the linear form of the strategyproof intervention policy of (ref) for two interventions, we begin by deriving performance guarantees for a “plug-in” version of this intervention policy. Our algorithm proceeds as follows: Given historical trajectories of the form $\{(\mathbf{y}_{i,pre}, \mathbf{y}_{i,post}^{(d)})\}_{i \in \pv{\mathcal{N}}{d}}$ for each $d \in \{0,1\}$, we can calculate the principal reward for assigning intervention $d_i$ to unit $i$ as

equation*[equation* omitted — 122 chars of source]

where $\pv{\mathcal{N}}{d}$ denotes the set of historical (non-strategic) units who received intervention $d$. Given the $(\mathbf{y}_{i,pre}, \pv{r}{d}_i)$ pairs as training data, (ref) uses an error-in-variables regression method (e.g., principal component regression pcr_jolliffe, pcr_tibshirani) to estimate $\pv{\boldsymbol{\beta}}{0}, \pv{\boldsymbol{\beta}}{1}$. The last step is to use the estimated linear coefficients to construct a “plug-in” estimator of intervention policy ((ref)) to use when assigning interventions to the $m$ (strategic) out-of-sample units.

theoremSuppose $d \in \{0, 1\}$, $d_i^A$ is the intervention assigned to unit $i$ by (ref), $d_i^*$ is the optimal intervention to assign to unit $i$, and \begin{equation*} \pv{\widehat{r}}{d}_{i} := \langle \pv{\widehat{\boldsymbol{\beta}}}{d}, \mathbf{y}_{i,pre} \rangle \end{equation*} is the estimated principal reward under intervention $d$. Then for any test unit $n+i$, \begin{equation} \mathbb E [\pv{r}{d_{n+i}^A}_{n+i}] - \mathbb E [\pv{r}{d_{n+i}^*}_{n+i} ] \leq |\pv{\widehat{r}}{0}_{n+i} - \mathbb E [\pv{r}{0}_{n+i}]| + |\pv{\widehat{r}}{1}_{n+i} - \mathbb E [\pv{r}{1}_{n+i}]| \end{equation}

(ref) shows that the difference in performance of (ref) and a strategyproof intervention policy that assigns interventions optimally can be bounded by the difference between the actual and estimated rewards under each intervention. Therefore, if $\pv{\widehat{\boldsymbol{\beta}}}{0}, \pv{\widehat{\boldsymbol{\beta}}}{1}$ are good estimates $\pv{\boldsymbol{\beta}}{0}, \pv{\boldsymbol{\beta}}{1}$, (ref) will perform well. In (ref), we leverage principal component regression to estimate $\boldsymbol{\beta}^{(0)}$ and $\boldsymbol{\beta}^{(1)}$ and obtain high-probability finite sample guarantees. Since we are dealing with strategically manipulated data, we are unable to apply prior results for learning from panel data in a black-box way. Our key insight which enables us to obtain performance guarantees for Algorithm (ref) is that its performance is matched by another intervention policy which makes decisions on units which are not strategic (intervention policy (ref) in the Appendix). Given this observation, the bound follows readily from algebraic manipulation.\looseness-1

Next we show that analogous performance guarantees can be obtained for the extension of (ref) to the setting where there are more than two interventions, when there is a sufficiently large gap in the principal's expected rewards for each unit type. This property is natural in many settings of interest; in our e-commerce running example, it corresponds to the principal deriving very different rewards from offering a discount that is not optimal for each group. We now present performance guarantees for (ref), which is an extension of (ref) to settings with more than two interventions.\looseness-1

corollary[Informal; detailed version in Corollary (ref)] For $\alpha > 0$, suppose the principal's expected rewards satisfy a sufficiently large reward gap $g(\alpha)$ ((ref)). Then,\looseness-1 \begin{equation*} \mathbb E[\pv{r}{d_{n+i}^A}_{n+i}] - \mathbb E[\pv{r}{d_{n+i}^*}_{n+i}] \leq \sum_{d=0}^{k-1} |\pv{\widehat{r}}{d}_{n+i} - \mathbb E[\pv{r}{d}_{n+i}]| \end{equation*} with probability at least $1 - \alpha$ for any test unit $n + i$, where $d_{n+i}^A$ is the intervention assigned to unit $n+i$ by (ref), and $d_{n+i}^*$ and $\pv{\widehat{r}}{d}_{n+i}$ are defined as in (ref).\looseness-1

algorithm[algorithm omitted — 1,507 chars of source]

Intuitively, a gap assumption is not needed in the single treatment regime since a unit will only modify their pre-treatment behavior in order to receive the (single) treatment. This is in contrast to the multi-treatment setting, where a unit's best response may be in one of several directions depending on which treatment(s) they are capable of receiving under a particular intervention policy. Obtaining performance guarantees for learning algorithms which do not require a gap assumption appears challenging for the general case, as the unit best response is not guaranteed to converge smoothly as $\{\pv{\widehat{\boldsymbol{\beta}}}{d}\}_{d=0}^{k-1}$ approaches $\{\pv{\boldsymbol{\beta}}{d}\}_{d=0}^{k-1}$.

Evidence Towards the Necessity of a Gap

To build intuition as to why such a gap may be necessary, consider the following example.\looseness-1

figure[figure omitted — 580 chars of source]

exampleConsider the one-dimensional setting in (ref), where the unit can manipulate by $\delta$ in either direction. Specifically, let $\mathcal{Y}_{pre} \in \mathbb{R}$, $d \in \{0, 1, 2\}$, and let the optimal intervention policy\footnote{We do not specify the principal's reward function so as to simplify the exposition.} be:\looseness-1 \begin{equation} d_i^* = \begin{cases} 1 \; if \; \Tilde{y}_{i,pre} \leq \pv{\theta}{1}\\ 2 \; if \; \Tilde{y}_{i,pre} \geq \pv{\theta}{2}\\ 0 \; o.w. \end{cases} \end{equation} for some $\pv{\theta}{1} \in \mathbb{R}$, $\pv{\theta}{2} \in \mathbb{R}$, and $\pv{\theta}{1} < \pv{\theta}{2}$. Suppose the principal deploys the following “plug-in” estimate of intervention policy ((ref)): \begin{equation*} d_i^P = \begin{cases} 1 \; if \; \Tilde{y}_{i,pre} \leq \pv{\widehat{\theta}}{1}\\ 2 \; if \; \Tilde{y}_{i,pre} \geq \pv{\widehat{\theta}}{2}\\ 0 \; o.w. \end{cases} \end{equation*} for $\pv{\widehat{\theta}}{1} \in \mathbb{R}$ and $\pv{\widehat{\theta}}{2} \in \mathbb{R}$. Moreover, suppose that the principal has perfect knowledge of $\pv{\theta}{1}$ (i.e., $\pv{\widehat{\theta}}{1} = \pv{\theta}{1}$) and after observing data from $n$ non-strategic units, $|\pv{\widehat{\theta}}{2}(n) - \pv{\theta}{2}| = c/n$ for some $c > 0$. Now consider a strategic unit $n+1$ with $y_{n+1,pre} = y$ such that $y - \pv{\theta}{1} < \delta$ and $\pv{\theta}{2} - y = \delta + \alpha$, for some $\alpha > 0$. If the principal had perfect knowledge of $\pv{\theta}{2}$, unit $n+1$'s best-response would be to modify their pre-treatment outcome to $\pv{\theta}{1}$ and receive intervention $1$. However, given the expression for $\pv{\widehat{\theta}}{2}$, we can write the best-response of unit $n+1$ as \begin{equation*} \Tilde{y}_{n+1,pre} = \begin{cases} \pv{\theta}{1} \; &\text{ if } \; \pv{\widehat{\theta}}{2} = \pv{\theta}{2} + \frac{c}{n}\\ \pv{\widehat{\theta}}{2} (= y + \delta + \alpha - \frac{c}{n}) \; &\text{ if } \; \pv{\widehat{\theta}}{2} = \pv{\theta}{2} - \frac{c}{n}\\ \end{cases} \end{equation*} as long as the number of non-strategic units $n < \frac{c}{\alpha}$. Therefore under this setting, if the $(n+1)$-st unit has pre-intervention outcome $y$, then their best-response may be highly discontinuous as long as $n < \frac{c}{\alpha}$ (recall that $\alpha$ can be chosen to be arbitrarily small), despite the fact that $\pv{\theta}{1}$ is perfectly known to the principal and $\pv{\widehat{\theta}}{2}$ converges to $\pv{\theta}{2}$ at the “fast” rate of $\mathcal{O}(1/n)$.

Application of PCR to Obtain End-to-End Guarantees

In order to leverage the out-of-sample guarantees for PCR, we make the following assumptions on the latent factors.

assumption[Well-balancing assumptions] The following hold: (a) $\sigma_i(\mathbb E[Y_{pre}^{(d)}]) = \Theta\left(\sqrt{\frac{c_n(d)T_0}{r}}\right)$ for all $i \in [r]$, (b) $c_n(d) = \Theta(c_n(d'))$ for all $d, d' \in [\![k]\!]_0$, and (c) $k = O(s)$.

(ref) says that (a) the non-zero singular values of the expected pre-intervention outcomes for the set of units who received each intervention are roughly equal, (b) each intervention is assigned roughly the same number of times, and (c) the number of interventions is on the order of the dimension of the latent subspace. (Part (c) is trivially satisfied whenever there is a single treatment and control.) We are now ready to state our formal result for the convergence rates of (ref) using PCR. An analogous bound may be obtained for (ref).

corollaryLet $\delta \in (0, 1)$ be an arbitrary confidence parameter and regularization parameter $\rho > 0$ be chosen to be sufficiently small, as detailed in agarwal2023adaptive. Further, assume that Assumptions (ref) (latent factor model), (ref) (expected reward gap), and (ref) (subspace inclusion) are satisfied, and rank$(\mathbb{E}[Y_{pre}^{(d)}]) = s$ for all $d \in [\![k]\!]_0$. If $T_0 \leq \frac{1}{2} T$, then under (ref) (balanced spectra) with probability at least $1 - \mathcal{O}(\delta)$, \begin{equation*} \begin{aligned} &\mathbb E[\pv{r}{d_{n+i}^A}_{n+i}] - \mathbb E[\pv{r}{d_{n+i}^*}_{n+i}] \leq \Tilde{\mathcal{O}} \left( \frac{r^2}{T_0 \wedge n} + \frac{r}{\sqrt{T_0 \wedge n}} + \frac{\sqrt{T_0}}{\sqrt{T-T_0}}\right) \end{aligned} \end{equation*} for any test unit $n+i$.

(ref) follows immediately from applying agarwal2023adaptive to (ref).

Experiments

We empirically evaluate the performance of (ref) on panel data constructed using time-series measurements of product sales at several stores. Our goal is to evaluate the performance of our methods when (1) data is not generated using a latent factor model and (2) the principal has imperfect knowledge about the units' ability to modify their pre-intervention outcomes.

\paragraph{Setup} Our initial dataset consists of weekly sales data from three products at nine different stores over the course of 18 months.\footnote{The dataset we use can be found at \href{https://raw.githubusercontent.com/susanli2016/Machine-Learning-with-Python/master/data/Sales_Product_Price_by_Store.csv}{https://raw.githubusercontent.com/susanli2016/}\\ \href{https://raw.githubusercontent.com/susanli2016/Machine-Learning-with-Python/master/data/Sales_Product_Price_by_Store.csv}{Machine-Learning-with-Python/master/data/Sales_Product_Price_by_Store.csv}.} We consider two interventions: discount (the product is on sale) and no discount (the product is not on sale). We define a unit to be a (store, product) pair which was under no discount for five consecutive weeks, followed by either discount or \texttt{no discount} for three consecutive weeks. \khedit{Since we only have access to historical data, we only get to see post-intervention outcomes under only one of \texttt{discount} or \texttt{no discount} for any given unit. Therefore we use these (unit, intervention, outcome) tuples to} run a synthetic interventions procedure to generate counterfactual outcomes for all units under both \texttt{discount} and \texttt{no discount}. We use the resulting trajectories as the ground-truth rewards for each unit under both interventions.

In order to train our model, we randomly assign interventions to $50\%$ of the units (135 trajectories), and we use the remaining $50\%$ to test the performance. Under such a setting, strategic behavior may arise when, for example, a local store manager wishes to maximize the number of products sold at their specific location, while the owner of the store chain ultimately wants to maximize revenue. In this case, the local store manager could conceivably have an incentive to strategically misreport their weekly revenue during the pre-treatment time period so that their products are given a discount and their sales increase (as was the case for Zara, previously mentioned in (ref)).

table[table omitted — 955 chars of source]

\paragraph{Results} See (ref) for a summary of our results. For an intervention policy $\pi$, we are interested in the increase in revenue from assigning interventions according to $\pi$, as opposed to the alternative. We normalize with respect to the optimal improvement in revenue, i.e. the best possible improvement if the principal were able to observe both counterfactual trajectories before assigning an intervention. Denote the intervention assigned by policy $\pi$ to unit $n+i$ as $d_{n+i}^{\pi}$ and the intervention not assigned by $\pi$ to unit $n+i$ as $\neg d_{n+i}^{\pi}$. Formally,

equation*[equation* omitted — 270 chars of source]

Note that Normalized $\Delta$ Revenue is at most $1$. Since the unit effort budget $\delta$ may be unknown in practice, we also examine the performance of (ref) when the principal's estimate of $\delta$ (the unit's effort budget; defined in (ref)) is misspecified as $\widehat \delta$. We find that the intervention policy of (ref) is able to achieve near-optimal improvement in revenue, in contrast to the relatively poor performance of the naive policy which does not consider incentives. Additionally, we observe that, under the experimental setup we consider, the performance of (ref) degrades gracefully as a function of model misspecification (as quantified by $\widehat \delta / \delta$). \khedit{Our empirical results suggest that if $\delta$ is unknown to the principal, it may be better for them to use an overestimate instead of an underestimate.}

Conclusions and Future Work

We introduce a framework for strategy-aware decision-making in panel data settings. In settings captured by our framework, we provide a sufficient and necessary condition for a strategyproof intervention policy to exist. Next we specialize our results to the canonical setting where unit outcomes are generated via a latent factor model, and the principal's reward is a linear combination of post-intervention outcomes. Under this setting, we show that the strategyproof intervention policy takes a simple closed form, when one exists. Additionally when there is only a single treatment and control, we show that a strategyproof intervention policy always exists, and we provide an algorithm for learning such an intervention policy from historical data. We also show that analogous performance guarantees can be obtained in the general setting under a gap assumption on the principal's rewards. Finally, we provide concrete rates of convergence for learning a strategyproof intervention policy when the parameters of interest are estimated via principal component regression. Along the way, we prove impossibility results for strategic multiclass classification which may be of independent interest. There are several exciting directions for future work.\looseness-1 \paragraph{Gap-free learning with multiple treatments} In order to obtain convergence rates for the intervention policy of (ref), our analysis relies on a gap assumption between the rewards of different interventions. It would be interesting to further explore if such a gap is indeed necessary, or if a tighter analysis or different algorithm could be used to weaken or remove this assumption.\looseness-1 \paragraph{Heterogeneous unit preferences and effort.} Our model of homogeneous unit preferences and effort budgets captures a variety of settings (e.g., patients may prefer an effective-but-costly medical treatment to a less-effective-but-cheaper alternative, customers generally prefer higher discounts to lower ones). However, it would be interesting to study more general games between the principal and strategic units which allow for, e.g., heterogeneous effort budgets and unit preferences over interventions.

\paragraph{Truthful mechanisms} Recall that our strategyproof mechanisms may require some units to strategize in order to be assigned the intervention that matches their true type. It would be interesting to explore the feasibility of designing mechanisms for incentivizing truthful behavior in panel data settings, i.e., incentivizing the agents to not alter their data at all when reporting their pre-intervention outcomes. While we provide such a truthful mechanism in (ref) under a gap assumption on principal rewards, deriving a truthful mechanism without any gap assumption appears challenging, as intervening based on a unit's pre-intervention outcomes provides an incentive for units to behave non-truthfully. \khedit{ \paragraph{Robustness to assumptions and unknown parameters} While our empirical results in (ref) suggest that our methods are fairly robust to data which is not generated by a latent factor model as well as overestimates of the unit effort budget $\delta$, a more thorough theoretical robustness analysis is an important step towards deploying our methods in real-world panel data settings. }

Acknowledgements

KH is supported in part by an NDSEG Fellowship. ZSW is supported in part by the NSF FAI Award \#1939606. The authors would like to thank the anonymous reviewers for valuable feedback and Hoda Heidari for helpful comments and suggestions in early stages of the project.