\documentclass{beamer}
\usepackage{appendixnumberbeamer}
\graphicspath{{figures/}}
%
% Choose how your presentation looks.
%
% For more themes, color themes and font themes, see:
% http://deic.uab.es/~iblanes/beamer_gallery/index_by_theme.html
%
\mode<presentation>
{
  \usetheme{Warsaw}      % or try Darmstadt, Madrid, Warsaw, ...
  \usecolortheme{beaver} % or try albatross, beaver, crane, ...
  \usefonttheme{default}  % or try serif, structurebold, ...
  \setbeamertemplate{navigation symbols}{}
  \setbeamertemplate{caption}[numbered]
  \setbeamertemplate{footline}[frame number]
  \setbeamertemplate{headline}{}
} 



\usepackage{graphicx} 
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{subcaption} 
\usepackage{amsmath,amssymb,bm,bbm} 
\usepackage{graphicx} 
\usepackage[]{natbib}
\bibliographystyle{aer}
\usepackage{hyperref}
\hypersetup{colorlinks,citecolor=blue,urlcolor=blue,linkcolor=blue}

\DeclareMathOperator*{\argmin}{arg\,min}


\title[]{Policy Targeting with Strategic Agents } 

\author{Evan Munro (Stanford GSB)}
\date{Econometrics Lunch \\ October 18, 2021 } 
\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Introduction} 
\begin{frame}{Personalized Policy}
    \textbf{Motivation} 
    \begin{itemize}
  \item If individual treatment effects are heterogeneous, a planner might improve outcomes by treating individuals heterogeneously rather than uniformly 
  \item With more individual-level data available, personalized policy is increasingly common (ex. airfare shown to customer depends on browsing history) 
  \item Problem: Treating individuals heterogeneously based on observed characteristics introduces incentives for individuals to change their behavior to receive a better treatment. 
    \end{itemize}
  \textbf{Research Question}  \begin{itemize} 

   \item How to estimate the optimal treatment rule when agents are strategic ?
   \item Treatment rule: A method of allocating treatments heterogeneously on the basis of observed covariates. 
\end{itemize} 
       \end{frame} 


\begin{frame}{Examples } 
 \begin{enumerate}
 \item Heterogeneous pricing of consumer products based on device usage patterns. 

\item Fraud detection based on spending patterns. 
\item Credit decisions based on non-traditional consumer metrics, such as cellphone data. 
    
   \end{enumerate}
   \vspace{0.5in} 
   \textbf{Personalized Policy Introduces Incentives to Misreport} 
   \begin{itemize}
       \item Incentives in all three of these settings for individuals to change characteristics to receive a better treatment (lower price, better prediction, or more credit) 
   \end{itemize}
      
\end{frame} 

\begin{frame}{Related Literature} 
\begin{itemize} 
\item CS/econ theory literature on strategic classification and manipulation:  \cite{dong2018strategic}, \cite{hardt2016strategic}, \cite{ball2020scoring}, \cite{frankel2019improving}, \cite{bjorkegren2020manipulation} 
    \begin{itemize}
        \item This paper applies to more general problems than existing approaches. 
    \end{itemize}
\item Causal inference and experiment design: 
 \cite{angrist2000interpretation}, \cite{athey2020policy}, \cite{wager2019experimenting}
 \begin{itemize}
     \item Existing literature treats observed characteristics as i.i.d. 
 \end{itemize}
 
     \item Bandit literature: \cite{flaxman2004online}, \cite{duchi2015optimal}
     \begin{itemize}
         \item Existing literature on zero-th order optimization of black box functions does not usually exploit cross-sectional variation. 
     \end{itemize}
      \item Robustness: \cite{bergemann2013robust}
      \begin{itemize}
          \item The procedure is robust to different distributions of types and different actions of individuals. 
      \end{itemize}
    \end{itemize}
\end{frame} 

\begin{frame}{Overview} 
\begin{itemize} 
\item Formalize the problem of strategic behavior in a treatment targeting setting as a Stackelberg Game.
\item Show that existing approaches for estimating treatment rules are sub-optimal in this setting.
\item Show that new results from zero-th order optimization literature (\textcolor{blue}{Chen, Lai, Li and Zhang, 2021}) can be used to design a sequential experiment that performs estimation and inference on the optimal rule. 
\end{itemize} 
\end{frame} 


\begin{frame}{Treatment Targeting as a Stackelberg Game} 

\begin{enumerate} 
\item Planner chooses a targeting rule, which maps covariates $X_i \in \mathcal X$ to treatments $W_i \in \mathcal \{0, 1\}\footnote{Extension to continuous treatments also possible}$. 
\[ \delta: \mathcal X \rightarrow [0, 1] \] 
$\delta(x) = Pr(W_i = 1 | X_i =x)$. 
\item For $ i \in [n]$, player $i$ reports covariates $X_i \in \mathcal X$: 
\[ X_i(\delta) = \arg \max_{x}  \delta(x) U_i(x, 1) + (1 - \delta(x)) U_i(x, 0)  \] 
$X_i$ maximizes expected utility, where the distribution of $W_i$ conditional on $x$ is determined by $\delta(x)$. 

\item For $i \in [n]$, $W_i$ is sampled from $\delta(X_i)$. 
\item The outcome $Y_i = Y_i(W_i)$ is observed 

\end{enumerate}
\end{frame} 

\begin{frame}{Planner's Objective} 
Let $Y_i(\cdot)$ and $U_i(\cdot)$ be drawn i.i.d. from some distribution $\theta$. 
The planner would like to minimize the average risk: 

\[ R(\delta) =  \mathbb E\Big[r(\delta(X_i), Y_i)\Big]\] 

Example Loss Functions: 
\begin{enumerate} 
\item Outcome maximization:
\[ r(\delta(X_i), Y_i) = -Y_i \] 
\item Binary classification:
\[ r(\delta(X_i), Y_i) = - \log(\delta(X_i)) Y_i - \log((1- \delta(X_i)) ( 1- Y_i) \]  
\end{enumerate}

\end{frame} 

\begin{frame}{Outcome Maximization} 
\begin{itemize}
\item Examine more closely maximizing $\mathbb E[Y_i(W_i)]$. 
\item With exogenous $X_i$, existing literature suggest a cutoff rule is optimal for average risk (e.g. Hirano and Porter, 2009). 
\end{itemize}
\bigskip
\begin{equation*} 
\begin{split}
&\tau(x) = \mathbb E[ Y_i(1) - Y_i(0) | X_i = x] \\
& \delta(x) = \mathbbm{1} (\tau(x) >0 ) 
\end{split} 
\end{equation*}


\textbf{Question: } Is it still optimal when observed covariates are generated by strategic behavior?


\end{frame} 


\begin{frame}{Example} 
Examine this question in a simple model. $n$ individuals have unobserved $Z_i \sim \mbox{Bernoulli}(0.5)$ and $C_i = 0.75$. 

\[ X_i(\delta) = Z_i + (1 - Z_i) \mathbbm{1}(\delta(1) - \delta(0) > C_i)  \] 
\[ Y_i(W_i) = Z_i W_i + (1- W_i) ( 1- Z_i) \] 

Under randomized treatment assignment, so that $\delta^{0}(x) = \frac{1}{2}$:
 
 \centering
 \includegraphics[width= 0.7\textwidth]{../figures/separated.png} 

Objective value $R(\delta^0) = 0.5 $ 

\end{frame} 

\begin{frame} {Targeted Treatments(1) } 
From the randomized experiment, we can estimate CATEs: 
\[ \hat \tau^0 (x) =  \frac{ \sum \limits_{i=1}^n Y_i \mathbbm 1(X_i = x, W_i =1 ) }{ \sum \limits_{i=1}^n \mathbbm 1(X_i = x, W_i =1)} - \frac{ \sum \limits_{i=1}^n Y_i \mathbbm 1(X_i=x, W_i = 0 )}{ \sum \limits_{i=1}^n \mathbbm 1(X_i = x, W_i =0 ) } \] 

\begin{itemize} 
\item Under randomized assignment, then $\hat \tau^0(1) = 1$ and $\hat \tau^0(0) = -1$. 
\item We might try to improve outcomes by implementing Manski (2004) CES rule: $\delta^c(1) = 1$ and $\delta^c(0) = 0$. 
\end{itemize} 

\end{frame}

\begin{frame}{Targeted Treatments (2) } 

Under $\delta^c(x)$, those with $Z_i = 0$ report $X_i= 1$ in order to receive the treatment which is valuable to them but results in worse outcomes for the planner. 


 \centering
 \includegraphics[width= 0.7\textwidth]{../figures/pooled.png} 

Objective value $R(\delta^c) = 0.5$

\end{frame}  

\begin{frame}{}

\textbf{Problem}: The distribution of $Y_i(\cdot)$ conditional on $x$ now depends on the choice of $\delta(x)$. Correct the notation of the cutoff rule: 

\begin{equation*}
\begin{split}
&\tau^{\delta}(x) = \mathbb E[ Y_i(1) - Y_i(0) | X_i = x, \delta(x)] \\
& \delta^c(x) = \mathbbm{1} (\tau^{\delta^c} (x) >0 ) 
\end{split} 
\end{equation*}

\textbf{Question: } Does the optimal targeting rule have this form? 
\end{frame} 

\begin{frame}{An Optimal Rule } 
 
 \begin{itemize} 
 \item $\delta^*(1)  = 0.75$ and $\delta^*(0) = 0$ is optimal 
 \item Under this rule, everyone with $X_i = 1$ has a positive CATE, but the planner does not treat them with probability 1 in order to maintain a distribution that is more amenable to targeting. 
 \end{itemize} 
 
  \centering
 \includegraphics[width= 0.7\textwidth]{../figures/separated.png} 
 
 Objective value $R(\delta^c) = 0.75$

\end{frame} 

\begin{frame} {Finding an Optimal Rule}  
\begin{itemize} 
\item With exogenous $X_i$, we can randomize $W_i$, estimate CATEs, and treat those with $\tau(x) > 0$. This is no longer possible. 
\item How can we estimate the optimal $\delta^*(x)$? 
\pause
\item Restrict our attention to treatment rules that are parametrized by $\beta \in \mathbb R^d$ 
\item We can write the planner objective as
\[ R(\beta) = \mathbb E[r(Y_i, W_i, \beta)] \] 

when $Pr(W_i = 1) = \delta(X_i; \beta)$. 
\item Goal: design an experiment that performs estimation and inference on 
\[ \beta^* = \arg \max_{\beta} R(\beta) \] 
\end{itemize} 
\end{frame} 

\begin{frame}{Experiment Design}

\begin{itemize} 
\item We allow the planner to randomize the targeting rule at the individual level
\item With some smoothness assumptions on $R(\beta)$ the simplest experiment would use grid-randomization to find an $\epsilon$-critical point. 

\item For some set of candidate $\{ \beta^k \}$ for $k \in [K]$, randomly assign a batch of individuals to each $\beta^k$ and observe the loss for each of them: 

\[ \hat R(\beta^k) = \sum \limits_{i=1}^n \mathbbm{1}(\beta_i = \beta^k) r(Y_i, W_i, \beta_i) \] 
\item Choose the $\beta^k$ that has the smallest $\hat R(\beta^k)$ 
\item But this requires a sample size that grows exponentially in the dimension of the parameters $d$ 
\end{itemize}

\end{frame} 

\begin{frame}{Gradient-based Methods} 

Let $R_i(W_i) = r(Y_i(W_i), W_i)$. For a continuous covariate, the gradient is as follows: 
\footnotesize
\[ \nabla R(\beta) = \mathbb E \left [ \Big (\frac{\partial R_i(W_i) }{ \partial y }[\textcolor{blue}{Y_i (1) - Y_i(0)}] + \textcolor{blue}{ R_i(1) - R_i(0) }\Big) \Big(\frac{\partial \delta(X_i)}{\partial \beta} + \frac{\partial \delta (X_i)}{\partial x}  \textcolor{red}{\frac{\partial X_i}{\partial \beta}} \Big )\right]  \] 

\normalsize
\begin{itemize} 
\item \textcolor{blue}{Blue} - estimable via a randomized experiment; Black - known in advance by the researcher; \textcolor{red}{Red} - Unknown 
\break
\pause
\item Can find local minimum by finding $\beta^*: \nabla R(\beta^*) = 0$ 
\item Naive risk minimization solves for optimum assuming that $\frac{\partial X_i}{\partial \beta} = 0$ 
\item Existing literature tends to specify some parametric assumptions on agent behavior so that $ \frac{\partial X_i}{\partial \beta}$ comes from a model (e.g. agents have a quadratic cost of changing their behavior).
\item For general treatment targeting problem, want to be robust to many forms of strategic behavior. 
\end{itemize} 
\end{frame} 

\begin{frame}{Sequential Experiment} 


\begin{itemize}
\item For $t = 1, \ldots, T$ periods, a batch of $n$ agents arrive 
\item Can be some temporal dependence in agents, but each agent's decision problem is static
\item Start with a naive estimate of $\hat \beta_0$
\item Draw $n$ perturbations $\bm u_i$ from the unit sphere in $\mathbb R^d$ 
\end{itemize} 


\begin{itemize} 
\item Let $R_i(\beta) = r(Y_i, W_i, \beta)$.  Update $\hat \beta$ over time using gradient-free stochastic optimization.  
\end{itemize}

\[ \hat \beta_t = \hat \beta_{t-1} - \eta_t \hat \nabla R(\hat \beta_{t-1}), \] 

where 
\[ \hat \nabla R(\beta_{t-1}) = \frac{d}{2n \mu_t} \sum \limits_{i=1}^n R_i(\hat \beta_{t-1} + \mu_t \bm u_i)\bm u_i.  \] 

\end{frame} 

\begin{frame}{Required Assumptions} 

The minimum of $R(\beta)$ is achieved at $\beta^*$. Let $H$ and $S$ be the Hessian and Score matrix at $\beta^*$. 

\begin{enumerate}
\item \textbf{Smooth} and \textbf{Strongly Convex}: $R(\beta)$ is twice continuously differentiable and $\lambda I_d \leq \nabla^2 R(\beta) \leq LI_d $ for any $\bm \beta \in \mathbb R^d$ and some $L > \lambda > 0$. 

\item $\textbf{Not too large}$: For $0 \leq \delta \leq 2$, $\mathbb E ||\nabla R_i(\beta) - \nabla R(\beta) ||^{2 + \delta} \leq M (|| \beta||^{2 + \delta} + 1)$. 
\item $\textbf{Hessian Lipschitz continuous}$:  For any $x, y \in \mathbb R^d$, 

\[ \mathbb E || \nabla^2 R_i(\bm x) - \nabla^2 R_i(\bm y) ||^2 \leq L_h || \bm x - \bm y||^2 \] 
\end{enumerate} 

\end{frame} 

\begin{frame}{Conjecture: Convergence Guarantees} 
Lemma 1 from Chen et al, 2021: 


\begin{lemma}
Set the step size as $\eta_t = \eta t^{-\alpha}$ for $n, \alpha > 0$. Let $\mu_t \leq \mu \eta_t$. For all $\frac{1}{2} < \alpha < 1$, then : 

\[ \mathbb E || \hat \beta_t - \beta^* ||^2 \leq Ct^{-\alpha} \] 
\end{lemma}
\end{frame} 

\begin{frame}{Conjecture: Asymptotic Normality} 

Letting $\bar \beta_t = \frac{1}{t} \sum \limits_{i=1}^t \hat \beta_t$, then : 

\begin{theorem} 
The average random gradient estimator is asymptotically normal
\[ \sqrt t( \bar \beta_t - \beta^*) \rightarrow_d N(0, H^{-1} Q H^{-1}),  \] 
where $Q = \frac{d}{n (d+2)} (2S + \mbox{tr}(S) I_d) + \frac{n-1}{n} S$ 

\end{theorem} 

For large $n$, then $Q \approx S$ and then the limiting covariance matrix achieves the Cramer-Rao lower bound. For finite $n$, gradient-free optimization compared to SGD has a higher limiting covariance matrix (\textcolor{blue}{Polyak and Juditsky, 1992}). 

\end{frame} 


\begin{frame}{Gradient Free Inference} 

Through a slightly more complex randomization scheme, it is possible to come up with an estimator for the Hessian based on zero-th order approximations to second derivatives that are averaged over the iterates. This estimator is $\hat H_t$. 
\break 
For the score matrix, 

\[ \hat Q_t = \frac{1}{t} \sum \limits_{i=1}^t \hat \nabla R(\beta_{s-1}) \hat \nabla R(\beta_{s-1})^{\top} \] 

In the Chen et al paper: 

\[ \mathbb E || \hat H_t^{-1} \hat Q_t \hat H_t^{-1} - H^{-1} Q H^{-1} || \leq C t^{-\alpha/2}\] 

\end{frame} 


       \begin{frame}{Simulation: Price Discrimination}
\begin{itemize}
    \item Revenue-maximizing planner selling insurance coverage
  \item $\beta = [\delta_0, \delta_1]$, so the price shown to individual $i$ is: 
          \[ W_i = \delta(x_i; \beta_i) = \delta_0 + \delta_1x_i \] 
\end{itemize} 
Individual Outcomes: 
  \begin{itemize}
      \item  Individual type $\theta_i$ 
      \item $Y_i$ is demand for coverage as a function of price  \[Y_i = y(W_i,\theta_i) \] 
      \item Pre-treatment features $X_i \in \mathbb R^{d_x}$ might be susceptible to manipulation (ex. self-reported miles driven, self-reported income, browsing history)
      
      \[ X_i = x(\beta_i, \theta_i) \] 
      \end{itemize} 
Planner maximizes revenue:  
          \[  \beta^* = \arg\max_{\beta} R(\beta) =  E[W_iY_i ] \] 
       \end{frame} 
\begin{frame}{Simulation (2)} 

    \begin{itemize} 
    \item Goal: Find profit-maximizing linear pricing rule when agents are strategic
    \item Make some assumptions on DGP so $y$ and $x$ are simple and $x_i$ is correlated with demand for good 
    \item Estimate $\beta$ using four different approaches:  
    \begin{enumerate} 
    \item Full information: Solve for $\beta^*$ directly 
    \item Naive Risk Minimization: Assume $x_i$ is i.i.d. and estimate $\hat \beta$ based on sample of data with no manipulation. 
    \item Repeated Naive Risk Minimization: Find $\beta$ that is optimal based on latest batch of data, assuming $x_i$ is i.i.d each time.  
    \item Dynamic Experiment
    \end{enumerate} 
    \item Plot estimated amount of price discrimination  of each approach at each of $t=1, \ldots, 500$ steps when batch of $n=1000$ agents arrive at each step 
    \end{itemize} 
\end{frame} 

\begin{frame}{Simulation: Finding Optimal $p_1$} 
\begin{figure}
    \centering
    \includegraphics[width=1\textwidth]{../figures/price_disc.pdf}
    \caption{Converge of Dynamic Experiment to Optimal Solution}
\end{figure}
\end{frame} 

\begin{frame}{Simulations: Regret}
\begin{table} 
    \centering 
    \begin{tabular}{| c|r | }
    \hline 
        \textbf{Method} & \textbf{Regret} \\ 
        \hline 
         Full Information &  0.00  \\
         Iterative Learning & -0.19 \\ 
         Repeated Naive Risk Minimization  & -24.38 \\ 
         Naive Risk Minimization & -48.40 \\ 
         \hline 
    \end{tabular}
    \caption{Average Regret} 
    \end{table} 
\end{frame}


\begin{frame}{Example 2: Prediction with Strategic Agents} 

\begin{itemize}
\item Objective is minimizing prediction error when predicting target based on manipulable features: $r(W_i, Y_i) = (W_i - Y_i)^2$:
\item Treatment $w_i = \beta x_i$ is the prediction of $Y_i$ 
\item  $Y_i$ is target characteristic that is unobserved initially
\item $X_i \in \mathbb R^k$ is observed features used to predict target characteristic       \end{itemize}
\end{frame}

\section{Experiment} 
\begin{frame}{MTurk Experiment } 

\begin{itemize}
    \item Treatment is linear prediction of how much a respondent likes math (1-5) from whether or not they get a factoring question correct 
    
    \[ LikeMath_i = \beta_0 + \beta_1 Correct_i + \epsilon_i \] 
    \item Goal is finding prediction-error minimizing treatment allocation function when respondents have varying incentives to fill out the factoring question
\end{itemize}


\centering
\includegraphics[width = \textwidth]{figures/incentive.png}
\begin{itemize}
    \item In the baseline survey, there is no bonus payment
\end{itemize}

\end{frame} 

\begin{frame}{Distribution Shift} 
\begin{table}[ht]
\centering
\begin{tabular} {|l | r c c |}
\hline
 & \textbf{No Incentive} & \textbf{50 Cents Bonus}
 & \textbf{100 Cents Bonus}\\ 
 \hline 
\hline 
\textbf{Variable} & \textbf{Mean (s.d.)}& \textbf{Mean (s.d.)} & \textbf{Mean (s.d.)} \\ 
\hline
$LikeMath$ & 3.16 (1.20) & 3.10 (1.14) &  3.16 (1.26)  \\ 
$MathSkill$ & 3.18 (1.04) & 3.09 (1.06) & 3.12 (1.06)\\ 
$Education$ & 15.54 (2.09) & 15.57 (2.37) & 15.43 (2.14) \\ 
$Correct$  & 0.41 (0.49) & 0.46 (0.50)& 0.59 (0.49)  \\ 
\hline 
\hline
\textbf{Outcome} & \textbf{Coef (s.d.)} & \textbf{Coef (s.d.)} & \textbf{Coef (s.d.)} \\ 
\hline 
$\hat \beta_0$ & 2.88 (0.08) & 2.85 (0.08) & 2.84 (0.10) \\ 
$\hat \beta_{1}$ &  0.689 (0.13) & 0.552 (0.13) & 0.547 (0.14) \\ 
\hline 
\end{tabular} 
\caption{Summary Statistics for Survey Waves ($n = 316$)} 
\label{tab:data} 
\end{table} 
\end{frame} 


\begin{frame}{Prediction Analysis } 

\begin{itemize} 
\item Treatment allocation for waves with bonus payment: 
\[ w(\bm X_i; \beta) = 1.45\cdot \beta_1 \cdot Correct_i \]
\end{itemize} 
\begin{enumerate} 
\item In-sample $R^2$ for naive RM, for sample without a bonus 
\item Out-of-sample $R^2$ for naive RM, for a sample without a bonus  
\item Out-of-sample $R^2$ for naive RM, for a sample with a targeted bonus 
\item Out-of-sample $R^2$ for OT-DE step, for a sample with a targeted bonus 
\end{enumerate} 
\end{frame} 

\begin{frame}{Experimental Step}

 \centering
    \begin{tabular}{| l |r r | r r |  r | }
    \hline 
      & \textbf{Naive RM}  & \textbf{Gradient} & \textbf{RRM} & \textbf{ Gradient} & \textbf{ Step}  \\ 
      \hline 
      $\hat \beta_0$ & 2.88 & -0.19 & 2.84 & 0.01 & 2.89\\ 
      $\hat \beta_1$ & 0.69 & -0.46 & 0.55 &  1.24 & 0.60\\
      \hline
    \end{tabular}

\end{frame} 

\begin{frame}{Impact on $R^2$} 
\begin{figure}[ht]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/r2exp}
    \caption{$R^2$ of Prediction Rules for Different Settings ($n=300$ for each out-of-sample evaluation) }
    \label{fig:exp_mse}
\end{figure}

\end{frame} 



\begin{frame}{Conclusion}
 \begin{itemize} 
        \item Propose adaptive experiment for designing optimal and robust targeting rules (ex. classification functions, heterogeneous pricing and heterogeneous credit allocation) 
        \item Theoretical, simulation-based and empirical evidence that this works well 
    \end{itemize}
    Key takeaways 
 \begin{enumerate}
 \item  Modeling incentives matters. CATE-based approaches that ignore endogeneity of covariates are sub-optimal. 
  \item A dynamic approach is useful for solving the problem with minimal assumptions 
 \item Estimating the optimal policy requires randomizing the dependence of treatments on observed characteristics. 
  \item Combining the flexibility of statistical optimization approaches with economic models of incentives is useful for estimating robust policy 
 \end{enumerate} 
\end{frame}

\appendix

\begin{frame}[allowframebreaks]{References}
    \bibliography{sample}
\end{frame}
\end{document} 

