\section{Additional discussion on related work}\label{append:related}

 The work of \cite{hardt2016stratclass} is most relevant to our work---they introduced a Stackelberg game framework to model the interaction between the learner and the test data. Our model can be viewed as a  generalization of \cite{hardt2016stratclass} by allowing \emph{heterogeneous} preferences over classification outcomes.  \cite{hardt2016stratclass} assume a special class of  \emph{separably cost functions}, and prove that the optimal classifier is always a \emph{threshold} classifier. Essentially, the assumption of separable cost functions  reduces the feature space to a low dimension, which is also why the strategic VC dimension in this case is at most $2$ as we proved.  Despite this clean characterization, it appears a strong and somewhat unrealistic requirement. For example, one consequence of  separable cost functions is that  for \emph{any} two features $\x, \z$, the manipulation cost from either $\x$ to $\z$ or from $\z$ to $\x$ must be $0$.\footnote{A cost function $c(\z; \x)$ is separable if there exists two functions $c_1, c_2: \mathcal{X} \to \mathbb{R}$ such that $c(\z; \x) = \qopname\relax n{max} \{ c_2(\z) - c_1(\x), 0 \}$. Since $c(\x; \x) = 0$, we have $c_2(\x) \leq c_1(\x)$ for any $\x$. Therefore, $c_2(\x) + c_2(\z) - c_1(\x) - c_1(\z) \leq 0$. Consequently, either $c_2(\x)  - c_1(\z) \leq 0$ or $ c_2(\z)- c_1(\x) \leq 0$, yielding either $c(\z; \x) =0$ or $c(\x; \z) =0$.} This appears unrealistic in reality. For example, a high-school student  with true average  math grade $80$ and true average literature grade  $95$ is likely to incur cost if she/he wants to appear as $95$ for math and $80$ for literature,  and vice versa. This is  because  different students are good at different aspects. Our model imposes less assumptions on the cost functions. For example, in our study of strategic linear classification, the cost functions are induced by arbitrary semi-norms.

\cite{bruckner2011stackelberg} is one of the first to consider the Stackelberg game formulation of strategic classification, motivated by spam filtering; however they do not study generalization bounds. \cite{zhangincentive} provide the sample complexity result for strategic PAC-learning under the homogeneous preference setting and in particular study the case under the incentive-compatibility constraints, i.e.,  subject to no data points will misreport features. These two works all assume the positive labels are always and equally preferred. There has also been work on understanding the social implications of strategically robust classification~\cite{akyol2016price,milli:fat19,hu:fat19}; these works show that improving the learner's performance may lead to increased social burden and unfairness. \cite{dong:ec18,chen2020learning} extend strategic linear classification to an online setting where the input features are not known a-priori, but instead are revealed  in an online manner. They both focused on the optimization problem of regret minimization.   Our setting however is in the more canonical PAC-learning setup and our objective is to design statistically and computationally efficient learning algorithms. All these aforementioned works, including the present work,  consider \emph{gaming} behaviors. A relevant but quite different line of recent works study \emph{strategic improvements} where the manipulation does really change the inherent quality and labels \cite{kleinberg2019classifiers,miller2019strategic,ustun2019actionable,bechavod2020causal,pmlr-v119-shavit20a}. The question there is mainly to design  incentive mechanisms to encourage agents' efforts or improvements.

Finally, going beyond classification, strategic behaviors in machine learning has received significant recent attentions, including in regression problems \cite{Perote2004StrategyproofEF,dekel2010incentive,chen:ec18}, distinguising distributions \cite{zhang2019distinguishing,zhang2019samples}, and learning for pricing \cite{amin2013learning,mohri2015revenue,vanunts2019optimal}. These are similar in spirit to us, but study a completely different set of problems using different techniques. Their results are not comparable to ours.

\section{Omitted Proofs from Section \ref{sec:stratvc}}
\subsection{Proof of Theorem \ref{theorem:probdet-pac}}\label{sec:append:thm1}
\begin{proof}

Let $\mathcal{Y}=\{+1,-1\}$. Define another binary hypothesis class $\tilde{H}=\{\kappa_c(h): h\in H\}$, where $\kappa_c:(\mathcal{X} \xrightarrow{} \mathcal{Y}) \xrightarrow{} (\mathcal{X} \times R \xrightarrow{}\mathcal{Y})$  is a mapping such that $\kappa_c(h) (\x, r)=h (\Delta_c(\x, r; h)), \forall (\x, r) \in \mathcal{X} \times R$. Note that the input of classifier $\kappa_c(h)$ consists of both the feature vector $\x$ and the preference $r$. By the definition of SVC, we have VC$(\tilde{H})=$SVC$(\mathcal{H}, R, c)=d$.

Given any distribution $\mathcal{D}$, cost function $c$, and $h\in \mathcal{H}$, the strategic 0-1 loss of $h$ is $L_{c}(h, \mathcal{D})=\mathbb{E}_{(\x,y,r)\sim \mathcal{D}}\Big[\mathbb{I} \big[ \kappa_c(h) (\x, r) \not = y \big]\Big]=L(\kappa_c(h), \mathcal{D})$, where $L(\tilde{h}, \mathcal{D})$ is the standard expected risk of the newly defined $\tilde{h} \in \tilde{\mathcal{H}}$ under the distribution $\mathcal{D}$ in the non-strategic setting. Therefore, studying the PAC sample complexity upper bound for $\mathcal{H}$ under the strategic setting $\langle R,c \rangle$ is equivalent to  studying the sample complexity for $\tilde{H}$ in the non-strategic setting. The latter problem can be addressed by employing the standard PAC learning analysis. From the Fundamental Theorem of Statistical Learning (Theorem 6.8 in \cite{shalev2014understanding}), we know $\tilde{H}$ is agnostic PAC learnable with sample complexity $O(\epsilon^{-2}(\text{VC}(\tilde{H})+\log\frac{1}{\delta}))$, meaning that there exists a constant $C$ such that for any $(\delta,\epsilon) \in (0,1)^2$ and any distribution $\mathcal{D}$ for $(\x, y, r)$, as long as $n\geq C\cdot\epsilon^{-2}(\text{VC}(\tilde{H})+\log\frac{1}{\delta})$, with at least probability $1-\delta$, we have $$L(\tilde{h}^*, \mathcal{D}) - \inf_{\tilde{h}\in\tilde{H}} L(\tilde{h},\mathcal{D}) \leq \epsilon ,$$ where $\tilde{h}^*$ is the solution of ERM with $n$ i.i.d. samples from $\mathcal{D}$ as input. Let $h^*$ be the solution of the corresponding SERM conditioned on the same $n$ i.i.d. samples from $\mathcal{D}$. By the definition of $\tilde{H}$ and $L_c$, we have $L_{c}(h^*, \mathcal{D})=L(\tilde{h}^*, \mathcal{D})$, and $ \inf_{h\in\mathcal{H}} L_{c}(h,\mathcal{D})=\inf_{\tilde{h}\in\tilde{H}} L(\tilde{h},\mathcal{D})$. Therefore, with probability $1-\delta$, we have

\begin{align*}
L_{c}(h^*, \mathcal{D}) - \inf_{h\in\mathcal{H}} L_{c}(h,\mathcal{D})\leq \epsilon,
\end{align*}
which implies \prob{} is agnostic PAC learnable with sample complexity $O(\epsilon^{-2} [d+\log(\frac{1}{\delta})])$ by the SERM.

\end{proof}

\subsection{Proof of Proposition \ref{prop:svc=avc}}
\begin{proof}
The adversarial VC-dimension defined in   \cite{cullina:nips18} relies on an auxiliary definition of \emph{corrupted classifier} $\tilde{h} = \kappa_R(h)$ of any classifier $h$ for the standard non-adversarial setting such that $\tilde{h}(\x) = h(\x)$ if all the points in $N(\x)$ have the same label as $\x$ and otherwise, $\tilde{h}(\x)=\perp$. Recall that $N(\x)=\{\z\in \mathcal{X}:(\z;\x) \in \mathcal{B}\}=\{\z\in \mathcal{X}: c(\z;\x) \leq r \}$ denotes the set of all possible adversarial features $\x$ can move to. Given this auxiliary definition, the  adversarial VC-dimension  is defined as AVC$(\mathcal{H}, \mathcal{B}) = \sup\{n: \sigma_n(\mathcal{F}, \mathcal{B}) = 2^n\}$, where

\begin{equation}\label{eq:sscavc}
  \sigma_n(\mathcal{F}, \mathcal{B})=\qopname\relax n{max}_{(\x, \y)\in \mathcal{X}^n\times \{+1,-1\}^n}|\{(f(\x_1, y_1;h),\ldots,f(\x_n, y_n;h)): h\in\mathcal{H}\}|
\end{equation}
is the shattering coefficient, and  $f(\x_i, y_i) = \mathbb{I}(\tilde{h}(\x_i)\neq y_i)$ is   the \emph{loss function} of the corrupted classifier $\tilde{h} = \kappa_R(h)$.

Since $\mathcal{B}$ and $c$ are $r$-consistent, we have $\mathcal{B} = \{(\z;\x): c(\z;\x) \leq r \}$. Let $R = \{+r, -r\}$.  We now prove the proposition by arguing
\begin{equation}
\label{eq:ssc=ssc}
    \sup \{n \in \mathbb{N}: \sigma_n(\mathcal{H}, R,c)=2^n \}=\sup\{n: \sigma_n(\mathcal{F}, \mathcal{B}) = 2^n\}.
\end{equation}
\begin{enumerate}
    \item If $\sup \{n \in \mathbb{N}: \sigma_n(\mathcal{H}, R,c)=2^n \}=n$, by Definition \ref{definition:ssc}, there exists  $(\x'_i, r'_i) \in \mathcal{X} \times R, i=1,\cdots,n$ such that $|\{(h(\Delta_c(\x'_1, r'_1; h )) , \cdots, h(\Delta_c(\x'_n, r'_n;h )):h\in \mathcal{H}\}|=2^n$. Since Definition \ref{definition:ssc} does not rely on the true labels of $\x'_i$, we may let the true labels of $\x'_i$ be $y'_i=-r'_i/r$ for any $i$. In this case, each $\x'_i$'s strategic preference is against its true label, which corresponds to the loss function $f$ in Equation \eqref{eq:sscavc} for the adversarial setting. Therefore, taking $(\x_i, y_i)=(\x'_i, y'_i)$ in Equation \eqref{eq:sscavc} gives $\sigma_n(\mathcal{F}, \mathcal{B})=2^n$. This implies $\sup \{n \in \mathbb{N}: \sigma_n(\mathcal{H}, R,c)=2^n \} \leq \sup\{n: \sigma_n(\mathcal{F}, \mathcal{B}) = 2^n\}$.
   \item Conversely, if $\sup\{n: \sigma_n(\mathcal{F}, \mathcal{B}) = 2^n\}=n$, from Equation \eqref{eq:sscavc}, there exists $(\x_i, y_i) \in \mathcal{X} \times R, i=1,\cdots,n$ such that $|\{(f(\x_1, y_1),\ldots,f(\x_n, y_n)): f\in\mathcal{F}\}|=2^n.$ Similarly, taking $r_i=-r y_i \in R$  gives $\sigma_n(\mathcal{H}, R, c)=2^n$, which implies $\sup \{n \in \mathbb{N}: \sigma_n(\mathcal{H}, R,c)=2^n \} \geq \sup\{n: \sigma_n(\mathcal{F}, \mathcal{B}) = 2^n\}$.
\end{enumerate}
Therefore, we have  AVC$(\mathcal{H}, \mathcal{B})=$SVC$(\mathcal{H}, \{+r,-r\}, c)$ for any $r$-consistent pair $(\mathcal{B}, c)$.
\end{proof}

\subsection{Proof of Corollary \ref{corr:svc-avcrelation}}
\begin{proof}
Since $\{+r, -r\}\subseteq \mathcal{B}$, we have $\sigma_n(\mathcal{H}, R, c)\geq \sigma_n(\mathcal{H}, \{+r, -r\}, c)$ by Definition \ref{definition:ssc}. As a result, SVC$(\mathcal{H}, R, c) \geq $SVC$(\mathcal{H}, \{+r, -r\}, c)$. Then by applying Proposition \ref{prop:svc=avc} we have \\SVC$(\mathcal{H}, R, c) \geq $SVC$(\mathcal{H}, \{+r, -r\}, c)=$AVC$(\mathcal{H}, \mathcal{B})$.
\end{proof}

\subsection{Proof of Proposition \ref{prop:svc>avc} }\label{append:prop:svc>avc}

Given any positive integer $n$, let $[n]$ denotes $\{1,2,\cdots,n\}$, and $\mathcal{S}$ be the power set of $[n]$, i.e., the set that contains all the subsets of $[n]$. Let $\mathcal{X}=[n]\cup \mathcal{S}$ be the sample space of size $n+2^n$, and the hypothesis class $\mathcal{H}$ is the set of all the point classifiers with points from   $\mathcal{S}$, i.e., $\mathcal{H}=\{h_{s}: s \in \mathcal{S}\}$, where point classifier $h_{s}$ only classifies the point $s \in \mathcal{S}$ as positive. The cost function $c(z;x) $ is   a metric defined as follows. Since metric is symmetric, i.e., $c(z;x) = c(x; z)$, we will use the notation $c(x,z)$ instead throughout   this proof.

\begin{equation} \label{eq:costfunc}
c(x,z)=
    \begin{cases}
     x,   & \text{if} \quad x\in [n], z\in \mathcal{S}, x \in z \\
     x+1,   &\text{if} \quad x\in [n], z\in \mathcal{S}, x \notin z \\
     c(z, x),   &\text{if} \quad x\in \mathcal{S}, z\in [n] \\
     x+z,   & \text{if} \quad x,z\in [n], x\neq z\\
     1, & \text{if} \quad x,z\in \mathcal{S}, x\neq z \\
     0, & \text{if} \quad  x=z,
    \end{cases}
\end{equation}
and $R$ is set to be $[-n, -1] \cup [1, n]$.

First, we verify that $c(\cdot, \cdot)$ is indeed  a metric. Given the Definition \eqref{eq:costfunc}, it is easy to see that $c(x,z)=0$ iff $x=z$, and $c(x,z)=c(z,x), \forall x,z \in \mathcal{X}$. It remains to check the triangle inequality, i.e., for any $x,y,z\in \mathcal{X}$, $c(x,y)+c(y,z)\geq c(x,z)$.
Consider the case when $x, y, z$ are different elements in $\mathcal{X}$. By enumerating all the possibility that whether each $x,y,z$ is in $[n]$ or $\mathcal{S}$, it suffices to discuss the following $8(=2^3)$ cases:

\begin{enumerate}
    \item if $x,y,z \in [n]$, $c(x,y)+c(y,z) = x+y+y+z > x+z = c(x,z)$.
    \item if $x,y,z \in \mathcal{S}$, $c(x,y)+c(y,z) = 2 > 1 = c(x,z)$.
    \item if $x,z \in [n], y\in \mathcal{S}$, then $c(x,y)\geq x, c(y,z)\geq z$. $\Longrightarrow$ $c(x,y)+c(y,z) \geq x+z = c(x,z)$.
    \item if $x,y \in [n], z\in \mathcal{S}$, we need to show that $c(x,y)\geq c(x,z)-c(y,z)$. Conditioned on the relationship between $x,y$ and set $z$, the maximum value of $c(x,z)-c(y,z)$ is $x-y+1$ when $y \in z, x\notin z$. Therefore, $c(x,y)=x+y \geq x-y+1 \geq c(x,z)-c(y,z)$.
    \item if $x,z \in \mathcal{S}, y\in [n]$, then $c(x,y)+c(y,z) \geq y+y > 1 \geq c(x,z).$
    \item if $x,y \in \mathcal{S}, z\in [n]$, then the maximum value for $c(x,z)-c(y,z)$ is $z+1-z=1$ when $z \notin x, z\in y$. Therefore, $c(x,y)\geq 1 \geq c(x,z)-c(y,z).$
    \item if $x\in\mathcal{S}, y, z \in [n]$, it is equivalent to case 4.
    \item if $y, z \in \mathcal{S}, x\in [n]$, it is equivalent to case 6.
\end{enumerate}

Next, we show VC$(\mathcal{H})=1$, AVC$(\mathcal{H}, \mathcal{B}_c(r) )=1$, and SVC$(\mathcal{H}, R, c)\geq n$. Observe that VC$(\mathcal{H})=1$ follows easily since no point classifier $h_s \in \mathcal{H}$ can generate the label pattern $(+1,+1)$ for any pair of distinct data points.

Next we prove AVC$(\mathcal{H}, \mathcal{B}_c(r))=1$. We first show AVC$(\mathcal{H}, \mathcal{B}_c(r))\leq1$ by   arguing that under binary nearness relation $\mathcal{B}_c(r) = \{(z;x): c(z,x) \leq r \}$  with $ r \geq 1$, any two elements $x_1, x_2$ in $\mathcal{X}$ cannot be shattered by $\mathcal{H}$

\begin{enumerate}
    \item If at least one of $r_1, r_2$ equals $-r$, e.g., $r_1=-r$, we show that $x_1$ can never be classified as $+1$ by contradiction. Suppose some $h_s \in \mathcal{H}$ classifies $(x_1, -r)$ as $+1$: if $x_1 \neq s$, since $r_1=-r<0$, $x_1$ will not manipulate its feature and be classified as $-1$; if $x_1 = s$, $x_1$ can move to any $z \in \mathcal{S}$ with cost $1 \leq r$, and will also be classified as $-1$. Therefore, $(x_1, x_2)$ can not be shattered.
    \item If $r_1=r_2=r$, consider the following two cases:
    \begin{enumerate}
        \item If at least one of $x_1, x_2$ belongs to $\mathcal{S}$, e.g., $x_1 \in \mathcal{S}$, then $x_1$ can move to any $s\in \mathcal{S}$ as $c(x_1, s)=1 \leq r$ for any $s\in \mathcal{S}$. Therefore $x_1$ can never be classified as $-1$ by any point classifier in $\mathcal{H}$.
        \item if $x_1, x_2 \in [n]$, we may w.l.o.g. assume $x_1<x_2$, i.e., $ x_1+1 \leq x_2$. Observe that when $r<x_1$, any $h_s \in \mathcal{H}$ will classify $x_1$ as -1 because $c(x_1, s)=x_1 > r, \forall s\in \mathcal{S}$; when $r \geq x_1+1$, any $h_s \in \mathcal{H}$ will classify $x_1$ as +1 because $c(x_1, s)=x_1+1 \leq r, \forall s\in \mathcal{S}$. Therefore, in order to shatter $(x_1, x_2)$, $r$ must lie in the interval $[x_1, x_1+1) \cap [x_2, x_2+1) = \emptyset$, which draws the contradiction.
    \end{enumerate}
\end{enumerate}

To see that AVC$(\mathcal{H}, \mathcal{B}_c(r))\geq 1$, for any $x \in [n]$ with $r>0$, it can be classified as either $+1$ or $-1$ as long as $r\in [x,x+1)$. We thus have AVC$(\mathcal{H}, c)=1$.

Finally, we prove that SVC$(\mathcal{H}, R, c) = n$. Consider the subset $[n] \subset \mathcal{X}$ of size $n$, with each element $i$ equipped with a strategic preference $r_i=i$. For any label pattern $\mathcal{L} \in \{+1, -1\}^n$, let $s_{\mathcal{L}}=\{i \in [n]: \mathcal{L}_i=+1\}$ be an element in $\mathcal{S}$. We claim that $h_{s_{\mathcal{L}}} \in \mathcal{H}$ gives exactly the label pattern $\mathcal{L}$ on $[n]$. To see this, consider any $i \in [n]$:
\begin{enumerate}
    \item If $i \in s_{\mathcal{L}}$, $i$ will move to $s_{\mathcal{L}} \in \mathcal{S}$ and be classified as $+1$, as the cost $c(i, s_{\mathcal{L}})=i\leq r_i=i$.
    \item If $i \notin s_{\mathcal{L}}$, $i$ will not move to $s_{\mathcal{L}} \in \mathcal{S}$ and be classified as $-1$, as the cost $c(i, s_{\mathcal{L}})=i+1 > r_i=i$.
\end{enumerate}

Therefore, any label pattern $\mathcal{L} \in \{+1, -1\}^n$ can be achieved by some $h_{s_{\mathcal{L}}} \in \mathcal{H}$. This implies SVC$(\mathcal{H}, R, c) \geq n$. On the other hand, it's easy to see $\mathcal{H}$ cannot shatter $n+1$ points, because any subset of size $n+1$ must contain an element $s_0$ in $\mathcal{S}$, and no matter what strategic preference $s_0$ has, it will either be classified as $+1$ by all $h_s \in \mathcal{H}$, or be classified as $+1$ by only one classifier in $\mathcal{H}$, i.e., $h_{s_0}$. Either case renders the shattering for $n+1$ points impossible.

\subsection{Proof of Proposition \ref{prop:svc-separable}}
\begin{proof}
Define the adversarial region for an adversary $(\x, r)$ as $N(\x, r)=\{\z \in \mathcal{X}:c_2(\z) \leq c_1(\x) + |r|\}\supseteq \{\x\}$. Since staying with the same feature has no cost, this implies $c(\x;\x)=0$ or equivalently $c_2(\x) \leq c_1(\x)$ for any $\x\in \mathcal{X}$.  Then, the best response function for $(\x, r)$ can be characterized by
\begin{enumerate}
    \item if $h(\x)=\text{sgn}(r)$, then $h(\Delta(\x, r;h))=\text{sgn}(r)$;
    \item if $h(\x)=-\text{sgn}(r)$, then \begin{equation}\label{eq:fdeltax}h(\Delta(\x, r;h))=\begin{cases}
    -\text{sgn}(r), \quad \forall \z\in N(\x, r): h(\z)=-\text{sgn}(r)\\ \text{sgn}(r),\quad \exists \z\in N(\x, r): h(\z)=\text{sgn}(r)
    \end{cases}\end{equation}
\end{enumerate}

Suppose there are three points $\{(x_i, r_i)\}_{i=1}^3$ that can be shattered by $\mathcal{H}$. Let $b_i = c_1(\x_i)+r_i$ and w.l.o.g. let $b_1\leq b_2\leq b_3$. From $b_1\leq b_2\leq b_3$, we have $N(\x_1, r_1) \subseteq N(\x_2, r_2)\subseteq N(\x_3, r_3)$.

By Pigeonhole principle, there must exists two elements in $\{r_1,r_2,r_3\}$ which have the same sign. Suppose these two elements are $r_1, r_2$ and consider the following two cases:

\begin{enumerate}
    \item $r_1>0, r_2>0$. From Equation \ref{eq:fdeltax}, for any $h \in \mathcal{H}$, $h(\Delta(\x_2, r_2;h))=-1$ means $h(\z)=-1, \forall \z\in N(\x_2, r_2)$. Note that $N(\x_1, r_1) \subseteq N(\x_2, r_2)$, we also have $h(\z)=-1, \forall \z\in N(\x_1, r_1)$. As a result,  $h(\Delta(\x_1, r_1;h))=-1$, meaning the sign pattern $\{+, -\}$ cannot be achieved by any $h\in \mathcal{H}$ for $\{(\x_1, r_1), (\x_2, r_2)\}$.
    \item $r_1<0, r_2<0$. From Equation \ref{eq:fdeltax}, for any $h \in \mathcal{H}$, $h(\Delta(\x_2, r_2;h))=1$ means $h(\z)=1, \forall \z\in N(\x_2, r_2)$. Similarly, from $N(\x_1, r_1) \subseteq N(\x_2, r_2)$ we conclude $h(\z)=1, \forall \z\in N(\x_1, r_1)$ and $h(\Delta(\x_1, r_1;h))=1$, meaning the sign pattern $\{-, +\}$ cannot be achieved by any $h\in \mathcal{H}$ for $\{(\x_1, r_1), (\x_2, r_2)\}$.
\end{enumerate}

Therefore, $\{(x_i, r_i)\}_{i=1}^3$ cannot be shattered by $\mathcal{H}$, which implies SVC$(\mathcal{H}, R, c)\leq 2$.

\end{proof}

\section{Proof of Theorem \ref{thm:svcinfinite}}\label{append:svcinfinite}
\begin{proof}
Let $\mathcal{X}=\mathbb{R}^2$, and consider the  linear hypothesis class on $\mathcal{X}$: $\mathcal{H}=\{h=\text{sgn}(\w\cdot \x+b):(\w,b)\in \mathbb{R}^3, \x \in \mathcal{X}\}$. We show that for any $n \in \mathbb{Z}^+$ and $R=\{+1\}$, there exist $n$ points $\{\x_i\}_{i=1}^n \in \mathcal{X}^n$ and corresponding cost functions $\{c_i\}_{i=1}^n$, such that the $n$'th shattering coefficients $\sigma_n(\mathcal{H}, R, \{c_i\}_{i=1}^n)=2^n$ (see Definition \ref{definition:ssc} for $\sigma_n$). Note that the cost function is instance-wise. For convenience, here we equivalently think of it as each data point $i$ has a different cost function $c_i$.

Let $\x_i=(0,0), \forall i\in [n]$ be the set of data points. The main challenge of the proof is a very careful construction of  the cost function for each data point. To do so, we first pick a set of $2^n$ different points  $S=\{s_j\}_{j=1}^{2^n} $  lying on the \emph{unit circle}, i.e., $S \subset \{(x,y): x^2+y^2=1\}$. The number $2^n$ is \emph{not} arbitrarily chosen --- indeed, we will map each point $s_j$ to one of the $2^n$ subsets of $[n]$ in a \emph{bijective} manner so that each $s_j$ corresponds to a unique subset of $[n]$. What are these $2^n$ different points will not matter to our construction neither it matters which point is mapped to which subset so long as it is a bijection.  Moreover, let $\bar{S}=\{(-x, -y): (x, y) \in S\}$ be the set that is origin-symmetric to $S$ such that $\bar{S} \cap S =\emptyset$. $\bar{S}$ is   chosen to ``symmetrize'' our construction to obtain a norm and needs not to have any interpretation.
For any $\x_i$, we now define its cost function $c_i$ through the following steps :

\begin{enumerate}
    \item Let $S_i=\{s \subseteq [n]: i \in s\} \subset S$ contains all the $2^{n-1}$ subsets of $[n]$ that include the element $i$.
    \item Let $\bar{S}_i=\{(-x, -y): (x, y) \in S_i\} \subseteq \bar{S}$ be the set that is origin-symmetric to $S_i$.

    \item Let $G_i$ be the convex, origin-symmetric polygon with the vertex set being $S_i \cup \bar{S}_i$.
    \item The cost function of $\x_i$ is defined as $c_i(\z;\x)=\|\x-\z\|_{G_i}$, where $\|\cdot\|_{G_i}=\inf\{\epsilon \in \mathbb{R}_{\geq0}: x\in \epsilon G_i\}$ is a norm derived from polygon  $G_i$ (note the  origin-symmetry of $S_i \cup \bar{S}_i$  and thus $G_i$).
\end{enumerate}

Next we show that for any label pattern $\mathcal{L} \in \{+1,-1\}^n$, there exists some linear classifier $h \in \mathcal{H}_2$ such that  $(h(\Delta_{c_1}(\x_1, +1;h ), \cdots, h(\Delta_{c_n}(\x_n, +1;h))=\mathcal{L}$.

With slight abuse of notation, let $s_{\mathcal{L}}= \{i\in[n]: \mathcal{L}_i=+1\}  \in S$ be the point in $S$ that corresponds to the set of the indexes of $\mathcal{L}$ with $\mathcal{L}_i = 1$. Let $h_{\mathcal{L}}$ be any \emph{linear classifier} whose decision boundary intersects the unit circle centered at $\x_i$ and \emph{strictly} separates $s_{\mathcal{L}}$ from all the other elements in $S\cup \bar{S}$. We will use $h_{\mathcal{L}}$ to denote both the linear classifier and its decision boundary (i.e., a line in $\mathbb{R}^2$) interchangeably. Due to the convexity of $G_i$, such $h_{\mathcal{L}}$ must exist. We further let $h_{\mathcal{L}}$ give prediction result $+1$ for the half plane that contains $s_{\mathcal{L}}$ and $-1$ for the other half plane. Figure \ref{fig:infsvcExample} illustrates the geometry of this example.

We now argue that $h_{\mathcal{L}}$ induces the given label pattern $\mathcal{L}$ for instances $\{(\x_i,  1, c_i)\}_{i=1}^n$. To see this, we examine $h_{\mathcal{L}}(\Delta_{c_i}(\x_i,  1;h))$ for each $i$:

\begin{enumerate}
    \item If $i \in  s_{\mathcal{L}} $, then $s_{\mathcal{L}} \in S_i$ and $\x_i$ can move to $s_{\mathcal{L}}$ with cost $c_i(s_{\mathcal{L}}; \x_i) < 1$. This is because $G_i$ is convex and  there exist a point $\x'_i$ on $h_{\mathcal{L}}$ such that $c_i(\x'_i; \x_i) <  c_i(s_{\mathcal{L}};x_i) = 1  = r_i$ (e.g., choose $\x'_i$ as the intersection point of the segment $[\x_i, s_{\mathcal{L}}]$ and $h_{\mathcal{L}}$). Therefore, $h_{\mathcal{L}}$ will classify $\x_i$ as positive. This case is shown in the left panel of Figure \ref{fig:infsvcExample}.
    \item If $i \notin  s_{\mathcal{L}}$, then $s_{\mathcal{L}} \notin S_i$ and $G_i$ does not intersect $h_{\mathcal{L}}$. In this case, $h_{\mathcal{L}}(\x)=-1$, and moving across $h_{\mathcal{L}}$ always induces a cost strictly larger than $1$. Therefore, the best response for $\x_i$ is to stay put and $h_{\mathcal{L}}$ will classify $\x_i$ as negative. This case is shown in the right panel of Figure \ref{fig:infsvcExample}.
\end{enumerate}

Now we have shown that the $n$'th shattering coefficients $\sigma_n(\mathcal{H}, \{+1,-1\}, \{c_i\}_{i=1}^n)=2^n$. Since $n$ can take any integer, we conclude the strategic VC-dimension in this case is $+\infty$.

\begin{figure}[ht]
    \centering
    \includegraphics[scale=0.33]{figures/example2.png}

    \caption{Left: If $i \in s_{\mathcal{L}}$, $h_{\mathcal{L}}$ intersects with $G_i$, and $\x_i$ can manipulate its feature within $G_i$ to cross $h_{\mathcal{L}}$. Right: If $i \notin s_{\mathcal{L}}$, $h_{\mathcal{L}}$ and $G_i$ are disjoint; $\x_i$ cannot manipulate its feature within $G_i$ to cross $h_{\mathcal{L}}$. Given any label pattern $\mathcal{L} \in \{+1,-1\}^n$, $G_i$ is the convex, origin-symmetric polygon associated with $\x_i$'s cost function. The linear classifier $h_{\mathcal{L}}$ is chosen to separate $s_{\mathcal{L}}$ from all other elements in $\bar{S} \cup S$ and classifies $s_{\mathcal{L}}$ as $+1$. The left/right panel shows the two situations, depending on $i \in s_{\mathcal{L}}$ or $i \not \in s_{\mathcal{L}}$. }
    \label{fig:infsvcExample}
\end{figure}

\end{proof}

\section{Proof of Theorem \ref{thm:strat-vc}}

The following lemma from advanced linear algebra is widely known  and will be useful for our analysis.
\begin{lemma}\label{lem:lp-distance}
For any   seminorm $l:\mathbb{R}^d \xrightarrow{} \mathbb{R}_{\geq 0}$, and the cost function $c(\z;\x)=l(\z-\x)$ induced by $l$, the minimum manipulation cost for $\x$ to move to the hyperplane $\w \cdot \x + b = 0$ is given by the following:
\begin{equation*}
\qopname\relax n{min}_{\x'}\{c(\x';\x):\w \cdot \x'+b=0\}= \frac{|\w \cdot \x +b|}{l^*(\w)}
\end{equation*}
where $l^*(\w) = \sup_{\z \in B } \{\w \cdot \z \} \in \mathbb{R}_{\geq 0} \cup \{+\infty\}$, and $\mathcal{B} = \{ \z: l(\z) \leq 1 \}$ is the unit ball induced by $l$.
\end{lemma}

The proof is divided into the following two parts. The first part is the  more involved one.

\vspace{2mm}
\noindent {\bf Proof of SVC$(\mathcal{H}_d, R, c)\leq d+1-\dim(V_l)$:}

It suffices to show that for any $n>d+1-\dim(V_l)$ and $n$ data points $(\x_i,r_i) \in \mathbb{R}^d \times R, \forall i=1,\cdots,n$, there exists a label pattern $ \mathcal{L} \in \{+1,-1\}^n, $ such that for any $h \in \mathcal{H}_d$ cannot induce $\mathcal{L} $, i.e.,  $$(h(\Delta_c(\x_1, r_1; h), \cdots, h(\Delta_c(\x_n, r_n; h))) \neq \mathcal{L}.$$

The first step of our proof derives a succinct characterization about the classification outcome for a set of data points. For any seminorm $l$,  it is known the set $\mathcal{B}=\{x:l(x)\leq 1\}$ is nonempty, closed, convex, and origin-symmetric. Let $l^*(\w)=\sup_{\z \in B} \{  \w\cdot \z \}$. We have $l^*(\w)>0$ for all $\w \neq \bm{0}$ since $\bm{0}$ is an interior point of $\mathcal{B}$. According to Lemma \ref{lem:lp-distance}, for any $\x \in \mathbb{R}^d$ and any linear classifier $h=(\w,b) \in \mathcal{H}_d$, the minimum manipulation cost for $\x$ to move to the decision boundary of $h$ is $|\w\cdot\x+b|/l^*(\w)$. Note that we may w.l.o.g.  restrict to $\w$'s such that $ l^*(\w)=1$ since the sign function $\text{sgn}(\w \cdot \x+b)$ does not change after re-scaling.  For any data point $(\x,r) \in \mathcal{X} \times R$ and  linear classifier $h \in \mathcal{H}_d$, we  define the \emph{signed} manipulation cost to the classification boundary as
\begin{align*}
\delta (h, \x)  =  h(\x) \cdot  \frac{|\w\cdot\x+b|}{l^*(\w)}  = \w\cdot\x+b,
\end{align*}
using the condition $l^*(\w)=1$.  We claim that $h(\Delta_c(\x, r;h))= 2\mathbb{I}( \w\cdot\x+b \geq -r)-1$. This follows a case analysis:
\begin{enumerate}
    \item If $r \leq 0$, then $h(\Delta_c(\x, r, h))=1$  if and only if $h(\x)=1$ and $\x$ \emph{cannot} move across the decision boundary of $h$ within cost $|r| = -r$. This implies $h(\Delta_c(\x,r;h))=2\mathbb{I}( \w\cdot\x+b \geq -r)-1$.
    \item If $r >0$, then $h(\Delta_c(\x, r, h))=-1$ if and only if $h(\x)=-1$ and $\x$ cannot move across the decision boundary of $h$ within cost $r$. In this case, $h(\Delta_c(\x,r;h))=-(2\mathbb{I}(- (\w\cdot\x+b) > r)-1)=2\mathbb{I}( \w\cdot\x+b  \geq -r)-1$. Note that the first inequality holds strictly because we assume $h$ always gives $+1$ for those $\x$ on the decision boundary.
\end{enumerate}
For a set of samples $(\bm{X}, \bm{\r})$ where $\bm{X}=(\x_1,\cdots,\x_n), \bm{\r}=(r_1,\cdots,r_n)$, define the set of all possible vectors (over the choice of linear classifiers $(\w, b) \in \mathcal{H}_d$)  of signed manipulation costs as
\begin{equation}\label{eq:StraVC-linear-map}
\mathcal{D}(\mathcal{H}_d, \bm{X})=\{( \w\cdot\x_1+b , \cdots, \w\cdot\x_n+b):h\in \mathcal{H}_d\},
\end{equation} there is a $h \in \mathcal{H}_d$ that achieves a label pattern $\mathcal{L}$ on $(\bm{X}, \r)$ if and only if there exist an element in $D(\mathcal{H}_d, \bm{\x}) + \bm{\r}$ with the corresponding sign pattern $\mathcal{L}$.

 Recall that a linear classifier is described by $(\w,b) \in \mathbb{R}^{d+1}$. The second step of our proof rules out ``trivial'' linear classifiers under strategic behaviors, and consequently allows us to work with only linear classifiers in a   linear space of smaller dimension.  Let $\mathcal{B}=\{\x: l(\x)\leq 1\}$ and $V_l$ be the largest linear space contained in  $\mathcal{B}$. We argue that it suffice to consider only linear classifiers $(\w,b) $ with $\w \perp V_l$. This is because for any $\w$ that is not orthogonal to the subspace $V_l$, we can find $\bar{\z} \in V_l$ such that $c(\bar{\z}; \x) = 0$ and $\w \cdot \bar{\z} \to \infty$ since $V_l$ is a linear subspace. This means any data point can induce its preferred label $\text{sgn}(r)$ with $0$ cost, by moving to  $\bar{\z}$ if $\text{sgn}(r)= +$ and $-\bar{\z}$ otherwise.  Any such linear classifier will result in the same label pattern, simply specified by  $\text{sgn}(r)$.  As a consequence, we only need to focus on linear classifiers $(\w,b) $ with $\w \perp V_l$. Let $\tilde{H_d} = \{ (\w, b): \w \perp V_l \}$ denote all such linear classifiers.

Next, we argue that when restricting to the  non-trivial class of linear classifiers $\tilde{ \mathcal{H}_d}$,  the $\mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X})$ defined in Equation \eqref{eq:StraVC-linear-map} lies in a linear subspace with dimension at most $d+1 - \text{dim}(V_l)$.  Consider the linear mapping $\mathcal{G}_{\bm{X}}: \tilde{ \mathcal{H}_d} \to \mathbb{R}^n$ determined by the data features $\bm{X}$, defined as
$$\mathcal{G}_{\bm{X}}(\w, b) = (\w \cdot \x_1+b, \cdots, \w \cdot  \x_n + b), \quad \forall (\w, b) \in \tilde{ \mathcal{H}_d}.$$
Since $\w \perp V_l$, $\w$ is from a linear subspace of $d  - \text{dim}(V_l)$. Linear mapping will not increase the dimension of the image space, therefore $\mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X})$ lies in a space with dimension at most $d+1 - \text{dim}(V_l)$.

Finally, we prove that there must exist label patterns that cannot be induced by linear classifiers whenever the number of data points $n>d+1-\dim(V_l)$. Let  $\text{span} \big( \mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) \big)$ denote the smallest linear space that contains $\mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) $. Since $\text{span} \big( \mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) \big)$ has dimension at most $d+1 - \text{dim}(V_l)<n$ but $\text{span} \big( \mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) \big) \subset \mathbb{R}^n$, there must exist a non-zero vector $\bar{\u} \in \mathbb{R}^n$ such that: (1) $ \bar{\u} \not = \bm{0}$; (2) $\bar{\u} \perp \text{span} \big( \mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) \big)$ (i.e.,    $\bar{\u} \cdot \bm{v} = 0, \forall \bm{v} \in \text{span} \big( \mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) \big)$); and (3)  $\bar{\u} \cdot \bm{\r} \leq 0$ (if $\bar{\u} \cdot \bm{\r} \geq 0$, simply takes its negation). Note that this implies  $\bar{\u} \cdot \bm{v} \leq  0, \forall \bm{v} \in \text{span} \big( \mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) \big) + \bm{r}$.

We argue that the sign pattern of the vector $\bar{\u}$, denoted as  $\text{sgn}(\bar{\u})$, and  the sign pattern of all negatives ($\mathcal{L}=(-1,\cdots,-1)$) cannot be achieved simultaneously by $\tilde{\mathcal{H}_d}$.  Suppose  $\text{sgn}(\bar{\u})$ can be achieved by $\tilde{\mathcal{H}_d}$, then there must exist $\v^1  \in \text{span}(\mathcal{D}(\tilde{\mathcal{H}_d}, \bm X)) +\bm \r $ such that $\text{sgn}(\bar{\u})=\text{sgn}(\v^1 )$ and $\bar{\u} \cdot \v^1 \leq 0$. Since $\text{sgn}(\bar{\u})=\text{sgn}(\v^1)$ also implies $\bar{\u} \cdot \v^1 \geq 0$, we thus have $\bar{\u} \cdot \v^1=\sum_{j=1}\bar{u}_j v^1_j=0$. We claim that there must exist $j$ such that $\bar{u}_j > 0$. First of all, we cannot have $\bar{u}_j <0$ for any $j$ since that implies $v^1_j < 0$ (only strictly less $v^1_j$'s will be assigned $-1$ pattern due to our tie breaking rule) and consequently, $\bar{\u}   \cdot \v^1 < 0$, a contradiction.  Also note that $\bar{\u} \neq \bm 0$, so there exist $j\in [n]$ such that $\bar{u}_j > 0$.

Utilizing the above property of $\bar{\u}$, we show that the sign pattern $\mathcal{L}=(-1, \cdots, -1)$ cannot be achieved by $\tilde{\mathcal{H}_d}$. Suppose, for the sake of contradiction, that this is not true. Then there exists another $\v^2 =(v_1^2,\cdots,v_n^2) \in  \text{span} \big( \mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) \big) +\bm \r $ with all its elements being strictly negative. Now consider $\v=\v^1-\v^2  \in \text{span}(\mathcal{D}(\tilde{\mathcal{H}_d}, \bm X))$, we have $\bar{u} \cdot \v = \bar{u} \cdot \v^1 - \bar{u} \cdot \v^2 = 0- \bar{u} \cdot \v^2>0$.  Here the inequality holds because $\bar{u}_j\geq 0, v^2_j<0$ for all $j$ and there exists some $j$ such that $\bar{u}_j>0$. Therefore, we draw a contradiction to the fact that $\bar{\u} \cdot \v =0$ for any $\v \in \text{span}(\mathcal{D}(\tilde{\mathcal{H}_d}, \bm X))$.

Now we proved that $\text{sgn}(\bar{\u})$ and $\mathcal{L}=(-1,\cdots,-1)$ cannot be achieved simultaneously by non-trivial classifiers $\tilde{\mathcal{H}}_d$, and the only achievable sign pattern for trivial classifiers is $\text{sgn}(\r)$. Note that $\r \in \text{span} \big( \mathcal{D}(\tilde{ \mathcal{H}_d}, \bm{X}) \big) + \bm{r}$,  $\text{sgn}(\r)$ is thus also achievable by $\tilde{\mathcal{H}}_d$. Therefore, the trivial classifiers has no contributions to the shattering coefficient, and we conclude at least one of $\text{sgn}(\bar{\u})$ and $\mathcal{L}=(-1,\cdots,-1)$ cannot be achieved by $\mathcal{H}_d$.

\vspace{2mm}
\noindent {\bf Proof of SVC$(\mathcal{H}_d, R, c)\geq d+1-\dim(V_l)$:}

The second step of the proof shows SVC$(\mathcal{H}, R, c)\geq d+1-\dim(V_l)$ by giving an explicit construction of $(\bm X,\r)$ that can be shattered by $\mathcal{H}_d$.  Let $\x_0=\bm{0}$, and $(\x_1,\cdots,\x_t)$ be a basis of the subspace orthogonal to $V_l$, $(\x_{t+1}, \cdots,\x_d)$ be a basis of the subspace $V_l$, where $t=d-\dim(V_l)$.

We claim that the $t+1=d+1-\dim(V_l)$ data points in $\{0,1,\cdots,t\}$ can be shattered by $\mathcal{H}_d$. In particular, for any given subset $S\subseteq \{0,1,\cdots,t\}$, consider the linear system

\begin{equation*}
    \begin{cases}
     \x_i \cdot \w_S + b_S = 1, \quad \text{if} \quad i \in S\\
     \x_i \cdot \w_S + b_S = -1, \quad \text{if} \quad i \leq t, \text{ and } i \notin S\\
     \x_i \cdot \w_S = 0, \quad t+1\leq i \leq d.
    \end{cases}
\end{equation*}

Because $(\x_1, \cdots,\x_d)$ has full rank, the solution $(\w_S, b_S)$ must exist. Therefore, the half-plane $h=\w_S\cdot \x+b_S$ separates $S$ and $\{\x_0, \cdots,\x_d\}/S$. Now consider the case when each $\x_i$ has a strategic preference $r_i \in R$. Since $\w_S$ is chosen to be orthogonal to $V_l$, $\w_S \cdot \x_i$ is bounded when $\x_i \in \{\z:c(\z; \x_i) \leq r_i\}$. Let $\delta_S=\qopname\relax n{max}_{0\leq i\leq t} \{\sup \{\w_S \cdot (\z-\x_i):c(\z; \x_i) \leq r_i\}\}$, and $\delta=\qopname\relax n{max}(1, 2\delta_S)$. Then the data set $\{ \delta\x_0, \cdots,\delta\x_t \}$ can be shattered by $\mathcal{H}_d$ for any given $c,R$, because the classifier $(\delta\w_S, \delta b_S)$ separates the subset $S$ and the other points regardless their strategic responses.

\section{Proof of Theorem \ref{thm:determistic-easy}}
\begin{proof}[Proof of Theorem \ref{thm:determistic-easy}]

For any data point $(\x, y, r)$, let the manipulation cost for the data point be $c(\z;\x) = l_{\x}(\z - \x)$ where $l_{\x}$ is any  seminorm. Since the instance is separable, there exists a hyperplane $h: \w \cdot \x + b=0$ that separates the given $n$ training points $(\x_1, y_1, r_1), \cdots, (\x_n, y_n, r_n)$ under strategic behaviors. The SERM problem is thus a feasibility problem, which we now formulate.
Utilizing Lemma \ref{lem:lp-distance} about the signed distance from $\x_i$  to  hyperplane $h$ under cost function $c(\z; \x_i) = l_{\x_i}(\z - \x_i)$, we can  formulate the SERM problem under the separability assumption. Concretely, we would like to find a  hyperplane  $h: \w \cdot \x + b=0$ such that it satisfies the following for any $(\x_i, y_i, r_i)$:
\begin{enumerate}
\item If   $y_i = 1$ and $r_i \geq 0$, we must have either   $\w \cdot \x_i + b \geq 0$ or   $\w \cdot \x_i + b \leq  0$ and $\frac{-(\w \cdot \x + b)}{ l^*_{\x_i}(\w)} \leq  r_i$;
\item If   $y_i = 1$ and $r_i \leq  0$, we must have   $\frac{ \w \cdot \x + b}{ l^*_{\x_i}(\w)} \geq  - r_i$ (this implies   $\w \cdot \x_i + b \geq  0$);
\item If   $y_i = -1$ and $r_i \leq  0$, we must have either   $\w \cdot \x_i + b \leq 0$ or   $\w \cdot \x_i + b > 0$ and $\frac{\w \cdot \x + b}{ l^*_{\x_i}(\w)} < -r_i$;
\item If   $y_i = -1$ and $r_i \geq  0$, we must have   $\frac{ -( \w \cdot \x + b)}{ l^*_{\x_i}(\w)} >  r_i$ (this implies $\w \cdot \x_i + b <  0$);
\end{enumerate}
Note that we classify any point on the hyperplane as $+1$ as well, which is  why the strict inequality for Case 3 and 4. Case 1 can be summarized as   $\frac{\w \cdot \x + b}{ l^*_{\x_i}(\w)} \geq - r_i$. Similarly, Case 3 can be summarized as $\frac{\w \cdot \x + b}{ l^*_{\x_i}(\w)} < -r_i$. To impose the strict inequality for Case 3 and 4, we may introduce an $\epsilon$ slack variable. These observations lead to the following formulation of the SERM problem.

\begin{lp}\label{lp:erm-deterministic}
\find{  \w, b,   \epsilon >0   }
\mbox{subject to}
\qcon{  \frac{\w \cdot \x_i + b }{ l^*_{\x_i}(\w)} \geq -r_i}{ \text{ points }(\x_i, y_i,  r_i) \text{ with } y_i=1}
\qcon{  \frac{\w \cdot \x_i + b }{ l^*_{\x_i}(\w)} \leq -r_i-\epsilon}{ \text{ points }(\x_i, y_i,  r_i) \text{ with } y_i=-1 }
\end{lp}

We now consider the two settings as described in the theorem statement.
We first consider {\bf  Situation 1}, i.e., the essentially adversarial case with $\qopname\relax n{min}^-  \geq \qopname\relax n{max}^+$  and an instance-invariant cost function induced by the same seminorm $l$, i.e., $c(\z; \x) = l(\x - \z)$ for any $\x$.   In this case, System \eqref{lp:erm-deterministic} is equivalent to the following

\begin{lp}\label{lp:erm-essentialAdv}
\find{  \w, b,   \epsilon >0   }
\mbox{subject to}
\qcon{  \w \cdot \x_i + b   \geq  -r_i     }{ \text{ points }(\x_i, y_i,  r_i) \text{ with } y_i =1 }
\qcon{    \w \cdot \x_i + b  \leq -(r_i + \epsilon)   }{ \text{ points }(\x_i, y_i,  r_i) \text{ with } y_i = -1 }
\con{ l^* (\w) = 1}
\end{lp}

This system is unfortunately not a convex feasibility problem. To solve System \eqref{lp:erm-essentialAdv}, we consider the following optimization program (OP), which is a relaxation of System \eqref{lp:erm-essentialAdv} by  relaxing  the non-convex constraint $ l^* (\w) = 1$  to  the convex constraint $ l^* (\w) \leq 1$.
\begin{lp}\label{lp:erm}
\maxi{    \epsilon   }
\mbox{subject to}
\qcon{\w \cdot \x_i + b \geq -r_i  }{ \text{ points }(\x_i, r_i) \text{ with label 1} }
\qcon{ \w \cdot \x_i + b \leq -r_i - \epsilon }{ \text{ points }(\x_i, r_i) \text{ with label -1}}
\con{ l^* (\w)  \leq 1}
\end{lp}

Note that OP \eqref{lp:erm} is a convex program because the objective and constraints are either linear or convex. Therefore, OP \eqref{lp:erm}  can be efficiently solved in polynomial time.\footnote{Note that convex programs can only be solved to be within precision $\epsilon$ in $\text{poly}(1/\epsilon)$ time sine it may have irrational solutions. In this case, we simply say it can be ``solved'' efficiently.  } Note that this relaxation is not tight in general as we will show later that solving System \eqref{lp:erm-essentialAdv}  is NP-hard in general.

Our main insight is that under the assumption of  $\qopname\relax n{min}^{-} \geq \qopname\relax n{max}^+$, the above relaxation is tight --- i.e.,  there always exists an optimal solution to the above problem with $ l^* (\w) = 1$. This solution is then a feasible solution to System \eqref{lp:erm-essentialAdv} as well,  thus completing our proof. Concretely, given any optimal solution $(\w^*, b^*, \epsilon^*)$ to OP \eqref{lp:erm}, we construct another solution $(\bar{\w}, \bar{b}, \bar{\epsilon})$ as follows: $$ \bar{\w} = \frac{ \w^*}{\alpha} , \quad  \bar{b} = \frac{ b^*}{\alpha} + (\frac{1}{\alpha} -1)\frac{\qopname\relax n{min}^- + \qopname\relax n{max}^+}{2} , \quad \bar{\epsilon} = \frac{ \epsilon^*}{\alpha}, \quad \text{ where } \alpha = l^* (\w^*)  \leq 1.  $$
We claim that the constructed solution above  remains feasible to OP \eqref{lp:erm}. Note that for data point with label 1, we have: (1) $ \frac{\qopname\relax n{min}^- + \qopname\relax n{max}^+}{2} \geq r_i$ by assumption $r_i \leq \qopname\relax n{max}^+ \leq \qopname\relax n{min}^-$; (2) $\x_i \cdot \w^* + b^* \geq -r_i  $ by the feasibility of $(\w^*, b^*, \epsilon^*)$. Therefore
\begin{eqnarray*}
&& \x_i \cdot \frac{\w^*}{\alpha} + \frac{b^*}{\alpha}  \geq -\frac{r_i}{\alpha}  \\
& \Rightarrow &  \x_i \cdot \frac{\w^*}{\alpha} + \frac{b^*}{\alpha}  + (\frac{1}{\alpha} -1)\frac{\qopname\relax n{min}^- + \qopname\relax n{max}^+}{2}  \geq -\frac{r_i}{\alpha}  + (\frac{1}{\alpha} -1)r_i \\
& \Leftrightarrow &  \x_i \cdot \bar{\w} + \bar{b}   \geq -r_i
 \end{eqnarray*}
 This proves that the constructed solution is feasible for data points with label 1. Similar argument using the inequality $  \frac{\qopname\relax n{min}^- + \qopname\relax n{max}^+}{2} \leq r_i $ for any negative label data point shows that it is also feasible for negative data points. It is easy to see that the solution quality is as good as the optimal solution $\epsilon^*$ since $\alpha \leq 1$. This proves the optimality of the constructed solution.

Finally, we consider the {\bf Situation 2 } where the instance is   adversarial, i.e, $\qopname\relax n{min}^- \geq 0 \geq \qopname\relax n{max}^+$. In this case,  $r_i$ in the first constraint of System \eqref{lp:erm-deterministic} is always non-positive whereas $r_i$ in the second constraint is always non-negative. After basic algebraic manipulations, the SERM problem becomes the following optimization problem.
\begin{lp}\label{lp:erm-generalAdv}
\find{  \w, b,   \epsilon >0   }
\mbox{subject to}
\qcon{  \w \cdot \x_i + b   \geq (-r_i) \cdot l^*_{\x_i}(\w)}{ \text{ points }(\x_i, y_i,  r_i) \text{ with } r_i \leq  0}
\qcon{    -( \w \cdot \x_i + b )  \geq (r_i + \epsilon) \cdot l^*_{\x_i}(\w)  }{ \text{ points }(\x_i, y_i,  r_i) \text{ with } r_i \geq 0 }
\end{lp}

This is again not a convex feasibility problem due to the non-convex term $(r_i + \epsilon) \cdot l^*_{\x_i}(\w)$, however for any fixed $\epsilon >0$  both constraints are convex. Moreover, if the system is feasible for some $\epsilon_0>0$ and it is feasible for any $0 < \epsilon \leq \epsilon_0$. Therefore, we can determine the feasibility of the (convex) system for any fixed $\epsilon$ and then binary search for the feasible $\epsilon$. Therefore, the feasibility problem in System \eqref{lp:erm-deterministic} can be solved in polynomial time.
\end{proof}

\section{Proof of Theorem \ref{thm:determistic-hard}}
\begin{proof}

We start with  {\bf Situation 1}, i.e., the preferences are arbitrary but the cost function is $c(\z;\x) = \|\x - \z||_2^2$. We will show later that the second situation can be reduced from the first.  In the first situation, the feasibility problem is System \eqref{lp:erm-essentialAdv} with $l$ as the $l_2$ norm. Our reduction starts by reducing this system to the following optimization problem (OP)

\begin{lp}\label{lp:erm-hardness-1}
\maxi{||\w||_2^2}
\mbox{subject to}
\qcon{\x_i \cdot \w + b \geq -r_i }{ \text{ points }(\x_i, r_i) \text{ with label 1} }
\qcon{ \x_i \cdot \w + b \leq -r_i - \epsilon  }{ \text{ points }(\x_i, r_i) \text{ with label -1}}
\con{||\w||^2_2 \leq 1}
\end{lp}

Formally, we claim that for any fixed $\epsilon$, system \eqref{lp:erm-essentialAdv} is feasible if and only if OP \eqref{lp:erm-hardness-1} has optimal objective value $1$. The ``if" direction is simple. That is, if OP \eqref{lp:erm-hardness-1} has optimal objective value $1$, then the optimal solution $(\w^*, b^*)$ is automatically a feasible solution to System \eqref{lp:erm-essentialAdv} because $||\w^*||_2 = 1$. For the ``only if" direction, let $(\bar{\w}, \bar{b})$ be any feasible solution to System \eqref{lp:erm-essentialAdv}, then it is easy to verify $\w^* = \frac{\bar{\w}}{||\w||_2}$ and $b^* = \frac{\bar{b}}{||\w||_2} $ must also be feasible to System \eqref{lp:erm-essentialAdv}. Moreover, it is an optimal solution to OP \eqref{lp:erm-hardness-1}  with objective value $1$, as desired.

We now prove that determining whether the optimal objective value of OP \eqref{lp:erm-hardness-1} equals $1$ or not is NP-complete. We reduce from the following well-known NP-complete problem called the \emph{partition problem}:
\begin{eqnarray*}
& \text{Given $d$ positive integers $c_1, \cdots, c_d$, decide whether there exists a subset $S \subset [d]$ such that} \\
& \sum_{i \in S} c_i = \sum_{i \not \in S} c_i
\end{eqnarray*}

We now reduce the above partition problem to solving OP \eqref{lp:erm-hardness-1}. Given any instance of partition problem, construct the following SERM instance.

\vspace{2mm}
\noindent {\bf The Constructed Hard SERM Instance for Situation 1}: We will have $n = 2d + 3$ data points with feature vectors from $\mathbb{R}^d$. For convenience, we will use $\e_i$ to denote the basis vector in $\mathbb{R}^d$ whose entries are all $0$ except that the $i$'th  is $1$. For each $i \in [d]$, there is a data point  $(\x, y, r)= (2\sqrt{d} \cdot \e_i, 1, 4)$  as well as a data point $(\sqrt{d} \cdot \e_i, -1, 1-\epsilon)$. The remaining three data points are  $(\c,1, 2)$, data point  $(2\c,-1, 2-\epsilon)$, and data  point  $(3\c,1, 2)$.

We claim that OP \eqref{lp:erm-hardness-1} instantiated with the above constructed instance has an optimal objective value $1$  if and only if the answer to the given partition problem is \emph{Yes}. We first prove the ``if" direction. If the partition problem is a Yes instance, then there exists an $S$ such that $\sum_{i \in S} c_i - \sum_{i \not \in S} c_i = 0$. We argue that the following construction is an optimal solution to OP \eqref{lp:erm-hardness-1} with optimal objective value $1$:
$$ b^* = -2 , \, \,  w_i = \frac{1}{\sqrt{d}} \, \,  \forall i \in S, \, \,  w_i = -\frac{1}{\sqrt{d}} \, \, \forall i \not \in S. $$
Clearly, $||\w^*||_2^2 = 1$. We only need to prove feasibility of $(\w^*, b^*)$. For any label $1$ point  $(\x,r) = (2\sqrt{d} \cdot \e_i, 4)$, we have $ \x \cdot \w^* + b^* =  2\sqrt{d} \e_i \cdot \w^* - 2 = -4  \geq -r $, as desired. Similarly, for any label $-1$  point  $(\x,r) = (\sqrt{d} \cdot \e_i, 1-\epsilon)$, we have $ \x \cdot \w^* + b^* =  \sqrt{d} \e_i \cdot \w^* - 2 = -1 \leq -r-\epsilon$. The feasibility of point $(\c,2)$ with label 1 is argued as follows: $ \x \cdot \w^* + b^* =   \c \cdot \w^* - 2 = -r$. Feasibility of $(2 \c,2-\epsilon)$ and $(3\c, 2)$ are similarly verified.

We now prove the ``only if'' direction.  In particular, we prove that that if OP \eqref{lp:erm-hardness-1} has some optimal solution $(\w^*, b)$ with $||\w^*||_2^2 =1$, then the partition instance must be Yes.

Let us first examine the feasibility of OP \eqref{lp:erm-hardness-1}.
\begin{enumerate}
    \item By the constraints with respect to positive-label data points $(2\sqrt{d} \cdot \e_i, 4)$, we have $2\sqrt{d}  \e_i \cdot \w + b\geq -4$ or equivalently  $w_i  \sqrt{d}  \geq  - \frac{b}{2}-2$.
    \item By the constraints with respect to negative-label data points $(\sqrt{d} \cdot \e_i, 1-\epsilon)$, we have $\sqrt{d}  \e_i \cdot \w + b\leq -1$ or equivalently  $ w_i  \sqrt{d}  \leq -b -1$.
    \item By the constraints with respect to data point $( \c, 2)$ with label 1, we have $ \c \cdot \w + b\geq -2 $, or equivalently $-2  - b \leq  \c \cdot \w$.
    \item By the constraints with respect to data point $(2 \c, 2-\epsilon)$ with label -1, we have $2 \c \cdot \w + b\leq -2$, or equivalently  $-2 - b \geq 2 \c \cdot \w$.
      \item By the constraints with respect to data point $(3 \c, 2)$ with label 1, we have $3 \c \cdot \w + b\geq -2$, or equivalently  $-2 - b \leq 3 \c \cdot \w$.
\end{enumerate}
 Point 3--5 implies $ 2 \c \cdot \w \leq  -2  - b \leq  \qopname\relax n{min} \{  \c \cdot \w, 3 \c \cdot \w \}$. This must imply $\c \cdot \w = 0$ as any non-zero  $\c \cdot \w $ cannot satisfy $ 2 \c \cdot \w  \leq  \qopname\relax n{min} \{  \c \cdot \w, 3 \c \cdot \w \}$. As a consequence, the only feasible $b$ value is $b = -2$. Plugging $b=-2$ into Point 1 and 2, we have
 $$ -\frac{1}{\sqrt{d}} \leq w_i \leq \frac{1}{\sqrt{d}}.$$
 Since the optimal objective value is $1 = \sum_{i=1}^d (w_i^*)^2$, it is easy to see that this optimal objective is achieved only when each $w_i^*$ equals either $-\frac{1}{\sqrt{d}} $ or $\frac{1}{\sqrt{d}}$. Now define $S= \{i: w_i^* = \frac{1}{\sqrt{d}}  \} $ to be the set of $i$ such that $w_i^*$ is positive. It is easy to verify that $S$ will be a solution to the partition problem, implying that it is a \emph{Yes} instance. This proves the NP-hardness for {\bf Situation 1} stated in the theorem.

Finally, we consider {\bf Situation 2}  which can be reduced from the first situation. In particular, the constructed hard instance above has reward preferences all being positive (in fact, drawn from only three possible values $\{ 1, 2, 4 \}$), but do not satisfy the essentially adversarial condition. However, if we are allowed to use instant-wise cost functions, we can simply scale down the reward preference for point with label $1$ but propositionally scale down its cost function so that the right-hand-side of the first constraint in System \eqref{lp:erm-essentialAdv} remains the same. Concretely, we now modify our constructed instance above to be the follows.

 \vspace{2mm}
 \noindent {\bf The Constructed Hard SERM Instance for Situation 2}: We still have $n = 2d + 3$ data points with feature vectors from $\mathbb{R}^d$. For each $i \in [d]$, there is a data point   $(\x, y, r)=(2\sqrt{d} \cdot \e_i, 1, 0.5)$ with  cost function $c(\z;\x) = \frac{1}{8}|\z - \x||_2^2$ as well as a data point   $(\sqrt{d} \cdot \e_i, -1, 1-\epsilon)$ with cost function $c(\z;\x) =  |\z - \x||_2^2$. The remaining three data points are: (1) data point $(\c, 1, 0.5)$ with  cost function $c(\z;\x) = \frac{1}{4}|\z - \x||_2^2$; (2)  data point  $(2\c, -1, 2-\epsilon)$ with cost function $c(\z;\x) =  |\z - \x||_2^2$; (3)  data  point  $(3\c,1, 0.5)$ with cost function $c(\z;\x) = \frac{1}{4}|\z - \x||_2^2$.

It is easy to verify that the above instance satisfy situation 1 in the theorem statement and is equivalent to the instance we constructed for the second situation and thus is also NP-hard.
\end{proof}

\section{Introduction}
\label{sec:intro}
In today's increasingly connected world, it is rare that an algorithm will act alone. When a machine  learning algorithm is used to make predictions or decisions about others who have their own preferences over the learning outcomes, it is well known (e.g., \emph{Goodhart's law}) that \emph{gaming behaviors} may arise---these have been observed in a variety of domains such as finance~\cite{gaming-loan}, online retailing \cite{hannak2014measuring},
education \cite{hardt2016stratclass} as well as during the ongoing COVID-19 pandemic \cite{unemploy-benefits,avoid-test}. In the early months of the pandemic, simple decision rules were designed for COVID-19 testing \cite{covid-test-rule} by the CDC. However, people had different preferences for getting tested. Those with work-from-home jobs and leave benefits preferred to get tested in order to know their true health status whereas some of the people with lower income, and without leave benefits preferred not to get tested (with fears of losing their income)~\cite{avoid-test}.
Policy makers sometimes prefer to make
classification rules confidential \cite{Citron201489WashLRev0001TS} to mitigate such gaming.
However, this is not fool-proof in general since the methods may   be reverse engineered in some cases, and transparency of ML methods is sometimes mandated by law, e.g.,~\cite{goodman2016regulations}.
Such concerns have led to a lot of interest in designing  learning algorithms that are robust to strategic gaming behaviors of the data sources \cite{Perote2004StrategyproofEF,dekel2010incentive,hardt2016stratclass,chen:ec18,dong:ec18,cullina:nips18,awasthi2019robustness}; the present work subscribes to this literature.

This paper focuses on the ubiquitous binary classification problem, and we look to design classification algorithms that are robust to gaming behaviors \emph{during the test phase}. We study a strict generalization of the canonical classification setup that naturally incorporates data points' \emph{preferences} over classification outcomes (which leads to strategic behaviors as we will describe later). In particular, each data point is denoted as a tuple $(\x, y, r)$ where $\x \in \mathcal{X}$ and $y \in \{ -1, +1 \}$ are the \emph{feature} and \emph{label}, respectively (as in classic classification problems), and additionally, $r \in \mathbb{R}$ is a real number that describes how much this data point prefers label $+1$ over $-1$. Importantly, we allow $r$ to be negative, meaning that the data point may prefer label $-1$. For instance, in the decision rules for COVID-19 testing, individuals who prefer to get tested have $r>0$, while those who prefer not to be tested have $r<0$. The magnitude $|r|$ captures how strong their preferences are. For example, in the school choice matching market, students have heterogeneous preferences over universities \cite{pathak2017really,roth2008have} and may manipulate their application materials during the admission process. Let set $R \subseteq \mathbb{R}$ denote the set of all possible values that the preference value $r$ may take. Obviously, the trivial singleton set $R = \{ 0 \}$ corresponds to the classic classification setup without any preferences. Another special case of $R = \{ 1 \}$ corresponds to the situation where all data points prefer label $+1$ equally.
This is the strategic classification settings studied in several previous works \cite{hardt2016stratclass,hu:fat19,miller2019strategic}.  A third special case is   $R = \{-1, 1 \}$. This corresponds to classification under \emph{evasion} attacks \cite{biggio:ecml13,goodfellow2015explaining,li2014feature,cullina:nips18,awasthi2019robustness}, where any test data point $(\x, y)$ prefers the \emph{opposite} of its true label $y$, i.e., the ``adversarial'' assumption.

Our model considers any \emph{general preference} set $R$. As we will show, this much richer set of preferences may sometimes make learning more difficult, both statistically and computationally, but not always.
Like~\cite{hardt2016stratclass,dong:ec18,goodfellow2015explaining,cullina:nips18}, our model assumes that manipulation is only possible to the data \emph{features} and happens only during the \emph{test} phase.  Specifically, the true feature of the test data may be altered by the  strategic data point. The cost of  masking a true  feature $\x$ to appear as a different feature $\z$ is captured by a \emph{cost function} $c(\z; \x)$. Therefore,
the test data point's decision needs to balance the \emph{cost} of altering feature and the \emph{reward} of inducing its preferred label captured by $r$.  As is standard in game-theoretic analysis, the test data point is assumed a rational decision maker and will choose to alter to the feature $\z$ that maximizes its quasi-linear utility $[r \cdot \mathbb{I}(h(\z) = 1) - c(\z; \x)]$.   This naturally gives rise to a    \emph{Stackelberg game} \cite{von2010market}. We aim to learn, from i.i.d. drawn  (unaltered) training data, the optimal classifier $h^*$ that minimizes the  0-1  classification loss,
assuming  any randomly drawn test data point (from the same distribution as testing data) will respond to $h^*$ strategically.  Notably,  the data point's strategic behaviors will \emph{not} change its true label. Such behavior is  referred to as  \emph{strategic gaming}, which crucially differs from \emph{strategic improvement} studied recently \cite{kleinberg2019classifiers,miller2019strategic}.

\subsection{Overview of Our Results}

\noindent{\bf The Strategic VC-Dimension.} We  introduce the novel notion of \emph{strategic VC-dimension} SVC($\mathcal{H}, R, c$) which captures the learnability of any hypothesis class $\mathcal{H}$  when test data points' strategic behaviors are induced by cost function $c$ and preference values from any set $R \subseteq \mathbb{R}$.

$\bullet$ We prove that any strategic classification problem is agnostic PAC learnable by the empirical risk minimization paradigm with  $O \big( \epsilon^{-2}[d + \log(\frac{1}{\delta}))] \big)$ samples, where $d=$SVC($\mathcal{H}, R, c$). Conceptually,  this result illustrates that SVC correctly characterizes the learnability  of the hypothesis class $\mathcal{H}$ in our strategic setup.

$\bullet$ Our SVC notion   generalizes the adversarial VC-dimension (AVC) introduced in \cite{cullina:nips18} for adversarial learning with evasion attacks. Formally, we prove that AVC equals precisely SVC($\mathcal{H}, R, c$) for $R=\{-1,1 \}$ when  data points are allowed to move within region  $\{ \z; c(\z;\x) \leq 1 \}$ in the corresponding adversarial learning setup.
However, for general preference set $R$, SVC can  be arbitrarily larger than both AVC and the standard VC dimension. Thus, complex strategic behaviors may indeed make the learning statistically  more difficult. Interestingly,  to our knowledge, this is the first time that adversarial learning and strategic learning are unified under the same PAC-learning framework.

$\bullet$ We prove SVC($\mathcal{H}, R, c$)$\leq 2$ for any $\mathcal{H}$ and $R$ when $c$ is any \emph{separable} cost function (introduced by \cite{hardt2016stratclass}). Invoking our sample complexity results above, this also recovers a  main learnability result of \citeyearpar{hardt2016stratclass} and, moreover, generalizes their result to arbitrary agent preferences.

\noindent {\bf Strategic Linear Classification. }  As a case study, we  instantiate our  strategic classification framework in perhaps one of the most fundamental classification problems,  \emph{linear classification}. Here, features are in $\mathbb{R}^d$ linear space. We assume the cost function $c(\z;\x)$ for any $\x$ is induced by \emph{arbitrary} seminorms of the difference $\z - \x$. We distinguish between two crucial situations: (1) \emph{instance-invariant} cost function which means the cost of altering the feature $\x$ to $\x + \Delta$ is the same for any $\x$; (2) \emph{instance-wise} cost function which allows the cost from $\x$ to $\x + \Delta$ to be different for different $\x$.
Our results show that the more general instance-wise costs impose significantly more difficulties in terms of both statistical learnability and computational tractability.

$\bullet$ {\bf Statistical Learnability.} We prove that the SVC of linear classifiers is  $\infty$ for \emph{instance-wise} cost functions even when features are in $\mathbb{R}^2$; in contrast, the SVC is at most $d+1$ for any \emph{instance-independent} cost functions and any $R$ when features are in $\mathbb{R}^d$. This later result also strictly generalizes the AVC bound for linear classifiers proved in \cite{cullina:nips18}, and illustrates an interesting conceptual message: though SVC can be significantly larger than AVC in general,  \emph{extending from $R = \{ -1, 1\}$ (the adversarial  setting) to an arbitrary strategic preference set $R$  does not affect the statistical learnability of strategic linear classification}.

$\bullet$ {\bf Computational Tractability.} We show that the empirical risk minimization problem for linear classifier can   be solved in polynomial time only when the strategic classification problem exhibits certain \emph{adversarial} nature. Specifically, an instance is said to have \emph{adversarial} preferences if all negative test points prefer label $+1$ (but possibly to different extents) and all positive test points prefer label $-1$.  A strictly more relaxed situation has  \emph{essentially adversarial} references --- i.e.,  any negative test point prefers label $+1$ more than any positive test point.
We show that for instance-invariant cost functions, any essentially adversarial instance can be solved in polynomial time whereas for instance-wise cost functions, only  adversarial instances can be solved in polynomial time. These positive results are essentially the best one can hope for. Indeed, we prove that the following situations, which goes slightly beyond the tractable cases above, are both NP-hard: (1) instance-invariant cost functions but general preferences; (2) instance-wise cost functions but essentially adversarial preferences.

\subsection{Related Work and Comparison}\label{subsec:related}
Most relevant to ours is perhaps the strategic classification model studied by \cite{hardt2016stratclass} and \cite{zhangincentive}, where \citet{hardt2016stratclass} formally formulated the strategic classification problem as a repeated Stackelberg game and \citet{zhangincentive} studied the PAC-learning problem and tightly characterized the sample complexity via ''incentive-aware ERM''. However, their model and results all assume homogeneous agent preferences, i.e., all agents \emph{equally} prefer label $+1$. Our model strictly generalizes the model of \cite{hardt2016stratclass,zhangincentive}  by allowing agents' \emph{heterogeneous} preferences over classification outcomes. Besides the modeling differences, the research questions we study are also quite different from, and not comparable to,  \cite{hardt2016stratclass}. Their positive results are derived under the assumption of \emph{separable cost} functions or its variants. While our characterization of SVC equaling at most $2$ under separable cost functions implies a PAC-learnability result of \cite{hardt2016stratclass}, this characterization serves more as our case study and our main contribution here is the study of the novel concept of SVC, which does not appear in previous works. Moreover, we study the efficient learnability of linear classifiers with cost functions induced by semi-norms. This broad and natural class of cost functions is not separable, and thus the results of \citet{hardt2016stratclass} does not apply to this case.

Our model also   generalizes the setup of  \emph{adversarial classification with evasion attacks}, which has been studied in numerous applications, particularly deep learning models \cite{biggio:ecml13, biggio:icml12,li2014feature,carlini:sp17, goodfellow2015explaining, Jagielski2018ManipulatingML, moosavi:cvpr17, mozaffari:jbhi15, rubinstein:sigmetrics09}; however, most of these works do not yield theoretical guarantees. Our work  extends and strictly generalizes the recent work of \cite{cullina:nips18} through our more general concept of SVC  and results on computational efficiency. In a different work,~\cite{awasthi2019robustness}  studied \emph{computationally} efficient learning of linear classifiers in adversarial classification with $l_{\infty}$-norm-induced $\delta$-ball for allowable adversarial moves. Our computational tractability results generalize  their results to $\delta$-ball  induced by \emph{arbitrary semi-norms}.\footnote{ \cite{awasthi2019robustness} also studied computational tractability of learning other classes of classifiers, e.g., degree-2 polynomial  threshold classifiers, which we do not consider.}

Strategic classification has been studied in other different settings or domains or for different purposes, including spam filtering  \cite{bruckner2011stackelberg},    classification under incentive-compatibility constraints \cite{zhangincentive},  online learning~\cite{dong:ec18,chen2020learning}, and understanding the social implications~\cite{akyol2016price,milli:fat19,hu:fat19}.
A relevant but quite different line of recent works study \emph{strategic improvements}~\cite{kleinberg2019classifiers,miller2019strategic,ustun2019actionable,bechavod2020causal,pmlr-v119-shavit20a}.
Finally, going beyond classification, strategic behaviors in machine learning has received significant recent attentions, including in regression problems \cite{Perote2004StrategyproofEF,dekel2010incentive,chen:ec18}, distinguishing distributions \cite{zhang2019distinguishing,zhang2019samples}, and learning for pricing \cite{amin2013learning,mohri2015revenue,vanunts2019optimal}. Due to  space limit,  we refer the curious reader to Appendix \ref{append:related} for detailed discussions.

\section{Introduction}
\label{sec:intro}
In today's increasingly connected world, it is rare that an algorithm will act alone. When a machine  learning algorithm is used to make predictions or decisions about others who have their own preferences over the learning outcomes, \emph{gaming behaviors} may arise. This is certainly not a new observation, and has been well-known as the \emph{Goodhart's law}, which is why policy makers prefer to make
decision and classification rules confidential \cite{Citron201489WashLRev0001TS}.
However, this is not fool-proof  in general since the methods can be reverse engineered in many settings. Moreover, transparency of machine learning methods is sometimes mandated by law, e.g.,~\cite{goodman2016regulations}.
Gaming behaviors have been observed in a variety of domains such as finance~\cite{gaming-loan}, online retailing \cite{hannak2014measuring},
education \cite{hardt2016stratclass} as well as the recent COVID-19 pandemic \cite{unemploy-benefits,avoid-test}. Such concerns have raised significant recent interests in designing  learning algorithms that are robust to strategic gaming behaviors of the data sources \cite{Perote2004StrategyproofEF,dekel2010incentive,hardt2016stratclass,chen:ec18,dong:ec18,cullina:nips18,awasthi2019robustness}; the present work subscribes to this literature.
\anil{Some references like gam, une, avo look weird. We could insert the COVID example here.}

This paper focuses on the ubiquitous binary classification problem, and we look to design classification algorithms that are robust to gaming behaviors \emph{during the test phase}. We study a strict generalization of the canonical classification setup that naturally incorporates data points' \emph{preferences} over classification outcomes (which leads to strategic behaviors as we will describe later). In particular, each data point is denoted as a tuple $(\x, y, r)$ where $\x$ and $y \in \{ -1, +1 \}$ are the \emph{feature} and \emph{label}, respectively (as in classic classification problems), and additionally, $r \in \mathbb{R}$ is a real number that describes how much this data point prefers label $+1$ over $-1$. Importantly, we allow $r$ to be negative, meaning that the data point may prefer label $-1$. Let  set $R \subseteq \mathbb{R}$ denote the set of all possible values that the preference value $r$ may take. Obviously, the trivial singleton set $R = \{ 0 \}$ corresponds to the classic classification setup without any preferences. Another special case of $R = \{ 1 \}$ corresponds to the situation where all data points prefer label $+1$ equally.
This corresponds to the strategic classification settings studied in several previous works \cite{hardt2016stratclass,hu:fat19,miller2019strategic}. Our model considers \emph{general preference} set $R$. As we will prove, this much richer set of preferences may sometimes make learning more difficult, both statistically and computationally, though  not always.

Similar to many works in this space \cite{hardt2016stratclass,dong:ec18,hu:fat19,milli:fat19}, our model assumes that manipulation is only possible to the data \emph{features} and happens only during the \emph{test} phase.  Specifically, the true feature of the test data may be altered by the  strategic data point. The cost of  masking a true data feature $\x$ to appear as a different feature $\z$ is captured by a \emph{cost function} $c(\z; \x)$. Therefore,
the test data point's decision needs to balance the \emph{cost} of altering feature and the \emph{reward} of inducing his preferred label determined by $r$.   As is standard in game-theoretic analysis, the training data point is assumed a rational decision maker and will choose the optimal feature $\z$ to alter to. Importantly, the data point's strategic behaviors will \emph{not} change its true label; this is  referred to as the strategic \emph{gaming} behaviors. A relevant but crucially different type of strategic behavior is  strategic \emph{improvement}, which changes the data point's label or intrinsic qualities \cite{kleinberg2019classifiers,miller2019strategic}. We refer interested readers to \cite{miller2019strategic} for a in-depth discussion of the differences among these two types of behaviors.

The classification procedure goes as follows: (1) the learner computes a classifier $h$ based on a set of \emph{unaltered  training data} $\{ (\x_i, y_i, r_i) \}_{i=1}^n$ drawn from distribution $\mathcal{D}$ independently; (2) the test data point $(\x, y, r)$, also drawn independently from $\mathcal{D}$, observes the classifier $h$ first, and strategically responds to $h$ by altering to  feature $\z$ that maximizes his quasi-linear utility $[r \cdot \mathbb{I}(h(\z) = 1) - c(\z; \x)]$. This gives rise to a natural \emph{Stackelberg game} between the learner (leader, she) and the test data point (follower, he).
We thus adopt the standard solution concept of \emph{Stackelberg equilibrium}, and aim to find the optimal classifier $h^*$ for the learner that minimizes her 0-1 classification loss (equivalently, maximizes classification accuracy), assuming that any test data point sampled from $\mathcal{D}$ will respond strategically. Note that the strategic Stackelberg equilibrium (SSE) also includes the test data point's best-response manipulated feature $\z$ to $h^*$, which however will be easy to compute given $h^*$ in our setup.

The above strategic classification model is natural and well-motivated. In fact, restricted \emph{special cases} of this  model have been considered in previous works \cite{bruckner2011stackelberg,hardt2016stratclass,cullina:nips18}, among which two of them are most relevant to ours. The first is   the seminal work on strategic classification by Hardt et al. \cite{hardt2016stratclass}. They considered a special case of our model where  each test data point always, and equally, prefers label $+1$. This corresponds to our model with a special preference set $R = \{1 \}$.   Our setup allows general preference set $R$ and  can model \emph{heterogeneous} preferences  among  data points. This largely enriches the possible strategic behaviors that can be captured by our setup. Besides motivating domains such as spam filtering and university admission  considered in previous works \cite{bruckner2011stackelberg,hardt2016stratclass}, a notable application domain that falls into our generalized setup, but not previous models, is the use of classification implemented by decision rules to determine who to take virus tests at the early stage of a pandemic (see. e.g., the CDC's rule for selected COVID-19 testing \cite{covid-test-rule}). In this situations, different people have different preferences of getting tests or not. Specifically, those with jobs that are easily adaptable to working from home prefer to get tested in order to know their true health status whereas those who have lower income, or do not get paid when quarantining at home, or cannot easily adapt to working from home would prefer to not get tested since a positive testing outcome may cause them to lose jobs and income \cite{avoid-test}.

The second line of works most relevant to ours is classification under evasion attacks \cite{biggio:ecml13,goodfellow2015explaining,li2014feature,cullina:nips18,awasthi2019robustness}.   Here also training data are assumed uncontaminated whereas each test data point $(\x, y)$ can alter its feature vector  within an allowable region  to induce a classification label \emph{opposite} to its true label $y$, i.e., the ``adversarial'' assumption. This turns out to be another special case of our model with $r = -y \in \{ -1, 1 \} = R$ for each test data point
and the cost function is defined as $0$ in the allowable moving region and $\infty$ otherwise. In a recent intriguing work, Cullina et al. \cite{cullina:nips18} considered the question of probably approximately correct (PAC) learning for this classification problem with evasion attacks. They introduced the notion of adversarial VC-dimension (AVC) and proves that AVC is at most $d+1$ for linear classifiers when the feature vector $\x \in \mathbb{R}^d$. In this paper, we strictly generalize the AVC to our strategic setup, which we coin \emph{strategic VC-dimension} (SVC). We study properties of SVC, its relation to AVC, and characterize SVC for linear classifiers. Notably, we show that AVC is  equivalent to SVC for the special preference set $R=\{-1, 1\}$, but with a general preference set $R$, SVC can be arbitrarily larger than AVC due to much richer class of strategic manipulations. Next, we elaborate our results in more details.
\anil{The above two paragraphs are discussed in some form in section 1.2. One possibility is to cut these into a couple of lines-- just say that the work of Hardt and Cullina is relevant and put a forward pointer. Also, should we move the COVID example into the first paragraph of intro?}

\subsection{Our Contributions}
\todo{add a table to summarize}
\fan{\begin{enumerate}
    \item First, we establish the PAC-learning result under the general strategic setting by introducing a novel notion of \emph{strategic VC-dimension} (SVC), which generalizes the concept of adversarial VC-dimension (AVC) introduced by \cite{cullina:nips18}. We recover the learnability result for linear classifiers from \cite{cullina:nips18} by showing SVC=AVC in that particular setting and also show SVC can be arbitrarily larger than both AVC and the standard VC dimension in general.
    \item We also provide computational learnability result for linear classifiers. We point out that the empirical risk minimization problem is solvable when and only when the allowed strategic behavior pattern exhibits certain adversarial nature.
    \item Finally, we study the power and limits of randomization in strategic classification. Surprisingly, we find that randomization may strictly increase the accuracy in general, but does not help in the special case of adversarial classification under evasion attacks. (actually, why it is the case? I though we only proved Randomization does not help in any perfectly separable adversarial classification problems.)
\end{enumerate}}
\noindent{\bf The Strategic VC-Dimension.} To capture fully general heterogeneous data preferences, we  introduce the novel notion of \emph{strategic VC-dimension} SVC($\mathcal{H}, R, c$) which naturally captures the complexity of any hypothesis class $\mathcal{H}$ in strategic classification setups when test data points' strategic behaviors are induced by cost function $c$ and preference values from set $R \subseteq \mathbb{R}$. We show that any strategic classification problem is agnostic PAC learnable by the empirical risk minimization paradigm with  $O \big( \epsilon^{-2}[d \log(\frac{d}{\epsilon}) + \log(\frac{1}{\delta}))] \big)$ samples, where $d=$SVC($\mathcal{H}, R, c$) is the SVC.  Conceptually,  this result illustrates that SVC correctly characterizes the learnability  of the hypothesis class $\mathcal{H}$ in our strategic setup.
We formally show that our SVC notion strictly generalizes the adversarial VC-dimension (AVC) introduced in \cite{cullina:nips18} for adversarial learning with evasion attacks. Specifically, we prove that AVC equals precisely SVC($\mathcal{H}, R, c$) for $R=\{-1,1 \}$ when  data points' allowable moves are within region  $\{ \z; c(\z;\x) \leq 1 \}$ in AVC.
However,  for general preference set $R$, SVC can be arbitrarily larger than both AVC and the standard VC dimension. This illustrates that complex strategic behaviors can indeed make the learning statistically  more difficult. Interestingly,  to our knowledge, this is the first time  that adversarial learning and strategic learning are studied under the same framework.

\noindent {\bf Implication of SVC in Strategic Linear Classification. Efficient Statistical Learnability:}  Next, we consider strategic classification for the widely adopted hypothesis class, \emph{linear classifiers}. Here, features are in $\mathbb{R}^d$ linear space and the cost function $c(\z;\x)$ for any $\x$ is assumed to be induced by arbitrary seminorms of the difference $\z - \x$. We distinguish between two situations which turn out to significantly affect the efficiency of learning: (1) \emph{instance-invariant} cost function which means the cost of altering the feature $\x$ to $\x + \Delta$ is the same for any $\x$; (2) \emph{instance-wise} cost function which allows the cost from $\x$ to $\x + \Delta$ to be different for different $\x$ (note that the separable cost function considered by Hardt et al.~\cite{hardt2016stratclass} is an instance-wise cost function). Our results illustrate sharp contrast --- in terms of both statistical learnability and computational tractability --- between these two situations. In particular, the SVC of linear classifiers is shown to be $\infty$ for \emph{instance-wise} cost functions even when features are in $\mathbb{R}^2$ whereas the SVC is at most $d+1$ for \emph{instance-independent} cost functions where  features are in $\mathbb{R}^d$. This later result also strictly generalizes the AVC bound for linear classifiers proved in \cite{cullina:nips18}, and illustrates the following interesting conceptual message: though SVC can be significantly larger than AVC in general,  \emph{extending from $R = \{ -1, 1\}$ (the adversarial learning setting) to an arbitrary preference set $R$ (which corresponds to strategic learning) does not increase the strategic VC-dimension of linear classifiers}.
\noindent {\bf Efficient Computational Learnability. } On the computational side, we prove that the empirical risk minimization problem for linear classifier can  be solved in polynomial time when the strategic classification problem exhibits certain \emph{adversarial} nature. In particular, we say the instance has \emph{generally adversarial} preferences if all negative test points prefer label $+1$ (but possibly to different extents) and all positive test points prefer label $-1$.   A strictly relaxed situation has  \emph{essentially adversarial} references; that is, any negative test point prefers label $+1$ more than any positive test point.\footnote{This is a strict generalization of generally adversarial preferences since positive points may also prefer label $+1$ in this case, but not as much as negative points.} We show that for instance-invariant cost functions, any essentially adversarial instance can be solved in polynomial time whereas for instance-wise cost functions, only generally adversarial instances can be solved in polynomial time. Moreover, we prove that these positive results are essentially the best one can hope for. Formally, the following situations, which goes slightly beyond the tractable situations above, are both NP-hard: (1) instance-invariant cost functions but general preferences; (2) instance-wise cost functions but essentially adversarial preferences.
\anil{we bring up the comparison with Hardt and Cullina in this subsection itself. So there is some duplication with the text in section 1.2}

Finally, we  examine the power and limits of \emph{randomization} in strategic classification. It is well-known that randomization does not improve classification accuracy in non-strategic settings (see, e.g., \cite{braverman2020role}). We observe that this ceases to be true in strategic classification --- there are examples where randomized linear classifiers can achieve strictly better accuracy than any deterministic linear classifier (similar result is observed by Braverman and Garg \cite{braverman2020role}; see related work for more discussion). Interestingly, however, we prove that randomization does \emph{not} improve accuracy for   classification with evasion adversaries, by leveraging the special properties of the cost function in adversarial classification.

\subsection{Additional Discussions on Related Works, and Comparisons}\label{subsec:related}

Most relevant to our paper is the recent work by Hardt et al. \cite{hardt2016stratclass} who introduced the Stackelberg game framework to model the interaction between the learner and the test data. As mentioned previously, our model can be viewed as a strict generalization of \cite{hardt2016stratclass} by allowing \emph{heterogeneous} preferences over classification outcomes.  Assuming a special class of  \emph{separably cost functions}, \cite{hardt2016stratclass} proves that the optimal classifier,  among all possible binary classifiers,  is always a \emph{threshold} classifier. Therefore, the assumption of separable cost functions essentially reduces the feature space to one dimension. Despite the clean characterization this assumption yields, it appears a strong and somewhat unrealistic requirement. For example, one consequence of  separable cost functions is that  for \emph{any} two features $\x, \z$, the manipulation cost from either $\x$ to $\z$ or from $\z$ to $\x$ must be $0$.\footnote{A cost function $c(\z; \x)$ is separable if there exists two functions $c_1, c_2: \mathcal{X} \to \mathbb{R}$ such that $c(\z; \x) = \qopname\relax n{max} \{ c_2(\z) - c_1(\x), 0 \}$. Since $c(\x; \x) = 0$, we have $c_2(\x) \leq c_1(\x)$ for any $\x$. Therefore, $c_2(\x) + c_2(\z) - c_1(\x) - c_1(\z) \leq 0$. Consequently, either $c_2(\x)  - c_1(\z) \leq 0$ or $ c_2(\z)- c_1(\x) \leq 0$, yielding either $c(\z; \x) =0$ or $c(\x; \z) =0$.} This is not realistic in reality. For example, a student  with true (average  school grade, SAT score) level as  $(85,1500)$ is likely to incur cost in order to score $(95, 1300)$  and vice versa, because  different students are good at different aspects. Our model imposes less assumptions on the cost functions, except that they are induced by   arbitrary semi-norms.
Working with this broader and more realistic class of cost functions,  we do not have the universal and simple characterization of the optimal classifier any more. This is why we  have to take the classic approach and define learnability for a hypothesis class of classifiers, captured by our novel notion of strategic VC-dimension. As an instantiation of our framework, we then study the efficient learnability, both statistically and computationally, of the ubiquitous linear classifiers.

There has been much recent interest in strategic classification. \cite{bruckner2011stackelberg} is one of the first to consider the Stackelberg game formulation of strategic classification, motivated by spam filtering. They primarily focused on the optimization problem of solving the Stackelberg classification game without deriving  generalization bounds. Zhang and Conitzer \cite{zhangincentive} study PAC learning for strategic classification under incentive-compatibility constraints, i.e.,  subject to no data points will misreport features. These two works all assume the positive labels are always and equally preferred. There has also been work on understanding the social implications of strategically robust classification~\cite{akyol2016price,milli:fat19,hu:fat19}; these works show that improving the learner's performance may lead to increased social burden and unfairness. Dong et al. \cite{dong:ec18} and Chen et al. \cite{chen2020learning} extended strategic linear classification to an online setting where the input features are not known a-priori, but instead are revealed  in an online manner. They both focused on the optimization problem of regret minimization.   Our setting however is in the more canonical PAC-learning setup and our objective is to design statistically and computationally efficient learning algorithms. All these aforementioned works, including the present work,  consider \emph{gaming} behaviors. A relevant but quite different line of recent works study \emph{strategic improvements} where the manipulation does really change the inherent quality and labels \cite{kleinberg2019classifiers,miller2019strategic,ustun2019actionable,bechavod2020causal,pmlr-v119-shavit20a}. The question there is mainly to design  incentive mechanisms to encourage agents' efforts or improvements.

As mentioned earlier, our model of strategic classification also strictly generalizes the problem of  \emph{adversarial classification with evasion attacks}, which has been studied in numerous applications, particularly deep learning models \cite{biggio:ecml13, biggio:icml12,li2014feature,carlini:sp17, goodfellow2015explaining, Jagielski2018ManipulatingML, moosavi:cvpr17, mozaffari:jbhi15, rubinstein:sigmetrics09}.  Our focus here however is on the theoretical side.  Most relevant to our paper is the recent work by Cullina et al. \cite{cullina:nips18}. They introduced the notion of adversarial VC-dimension, which we generalize in this paper. We also  show the connections and differences between our strategic VC-dimension and AVC. Notably, AVC can be viewed as a special case of SVC. Moreover, we studied computational efficiency as well whereas \cite{cullina:nips18} focuses only on statistical  efficiency of learning. In a different work, Awasthi et al. \cite{awasthi2019robustness}  studied \emph{computationally} efficient learning of linear classifiers under $l_{\infty}$-norm $\delta$-ball adversarial classification. Our computational tractability results can be viewed as a generalization of their results to $\delta$-ball  induced by \emph{arbitrary semi-norms} in adversarial classification.\footnote{Awasthi et al. \cite{awasthi2019robustness} also studied computational tractability of learning other classes of classifiers, e.g., degree-2 polynomial  threshold classifiers.}

Our last technical section examines the power and limit of randomization in strategic classification. Braverman and Garg \cite{braverman2020role} recently show that randomized linear classifier can strictly improve strategic classification even in $1$-dimensional feature space, when the cost function is \emph{instance-wise}. Our results complements this finding by proving that when cost function is \emph{instance-invariant}, randomization will not be helpful in $1$-dimensional feature space, but we show it can strictly improve classification accuracy in $2$-dimensional feature space. Moreover, to our knowledge, our result of showing the limit of randomization in adversarial classification is new.

Finally, going beyond classification, strategic behaviors in machine learning has received significant recent attentions, including in regression problems \cite{Perote2004StrategyproofEF,dekel2010incentive,chen:ec18}, distinguising distributions \cite{zhang2019distinguishing,zhang2019samples}, and learning for pricing \cite{amin2013learning,mohri2015revenue,vanunts2019optimal}. These are similar in spirit to us, but study a completely different set of problems using different techniques. Their results are not comparable to ours.

\section{Strategic Linear Classification}\label{sec:linear}
This section instantiates our previous general framework in one of the most fundamental special cases, i.e., linear classification.  We will study both  the \emph{statistical} and \emph{computational} efficiency in   \emph{strategic linear classification}.   Naturally,  we will restrict $\mathcal{X} \subseteq \mathbb{R}^d$ in this section.  Moreover, the cost functions are always assumed to be induced by semi-norms.\footnote{A function $l: \mathcal{X} \to \mathbb{R}_{\geq 0}$ is a \emph{seminorm} if it satisfies: (1) triangle inequality: $l (\x + \z) \leq l(\x) + l(\z)$  for any $\x, \z \in \mathcal{X}$; and (2)
homogeneity: $ l(\lambda \x ) =|\lambda| l(\x)$  for any $ \x \in \mathcal{X}, \lambda \in \mathbb{R}$.} A linear classifier is defined by a hyperplane $  \w \cdot \x + b = 0$; feature vector $\x$ is classified as $+1$ if and only if $\w \cdot \x +b\geq 0$. With slight abuse of notation, we sometimes also call $(\w,b)$ a \emph{hyperplane} or a \emph{linear classifier}.  Let $\mathcal{H}_d$ denote the hypothesis set of all $d$-dimensional linear classifiers. For linear classifier $(\w,b)$,  the data point's best response can be   more explicit expressed as: $$ \Delta_c(x, r;\w,b) = \arg \qopname\relax n{max}_{\z} \big[  \mathbb{I}(\w \cdot \z + b\geq 0) \cdot r - c(\z;\x) \big] .$$

\subsection{Strategic VC-Dimension of Linear Classifiers}
We first study the statistical learnability by examining the strategic VC-dimension (SVC). Our first result is a negative one, showing that SVC can be unbounded in general even for linear classifiers with features in $\mathbb{R}^2$ (i.e., $\mathcal{X} \subset \mathbb{R}^2$) and with simple preference set $R = \{ +1, -1\}$.

 \begin{theorem}
\label{thm:svcinfinite}
Consider strategic linear classification \probL{}.  There is an instance-wise cost function $c(\z; \x) = l_{\x}(\z -\x)$ where each $l_{\x}$ is a norm, such that $SVC(\mathcal{H}_d, R, c) = \infty$ even when $\mathcal{X} \subset \mathbb{R}^2$ and $R = \{1\}$.
\end{theorem}
\begin{proof}[Proof Sketch]
We consider a set of data points $\{\x_i\}_{i=1}^n$ in $\mathbb{R}^2$ whose features are close but with cost functions induced by different norms. The cost functions are designed such that each point $\x_i$ is allowed to strategically alter its feature within a carefully designed polygon $G_i$ centered at the origin. Specifically, for any label pattern $\mathcal{L} \in \{+1,-1\}^n$, it has a corresponding node $s_{\mathcal{L}}$ on a unit cycle. The polygon $G_i$ for $\x_i$ is the convex hull of all $s_{\mathcal{L}}$s whose label pattern $\mathcal{L}$ classifies $i$ as $+1$.
\begin{figure}[ht]
    \centering
    \includegraphics[scale=0.17]{figures/example2.png}

    \caption{$G_i$ is the  polygon associated with $\x_i$'s cost function. Given any label pattern $\mathcal{L} \in \{+1,-1\}^n$, the linear classifier $h_{\mathcal{L}}$ is carefully chosen to induce exactly the label pattern $\mathcal{L}$ on $\{\x_i\}_{i=1}^n$.
    }
    \label{fig:infsvcExample1}
\end{figure}
Figure \ref{fig:infsvcExample1} illustrates a high-level  idea of our construction. Under such cost functions, we   prove that $\mathcal{H}$ can induce all $2^n$ possible label patterns. The formal  construction and proof can be found in Appendix \ref{append:svcinfinite}.
\end{proof}

In the study of adversarial VC-dimension (AVC)  by \cite{cullina:nips18},  the feature manipulation region of each data point is assumed to be \emph{instance-invariant}. As a corollary, Theorem \eqref{thm:svcinfinite} implies that AVC also becomes  $\infty$ for linear classifiers in $\mathbb{R}^2$ if each data point's manipulation region is allowed to be different.

It turns out that the $\infty$-large SVC above is mainly due to the instance-wise cost functions. Our next result shows that under instance-invariant cost functions, the SVC will behave nicely and, in fact, equal to the AVC for linear classifiers  despite the much richer data point manipulation behaviors. This result also strictly generalizes the characterization of AVC by \cite{cullina:nips18} for linear classifiers and shows that linear classifiers will be no harder to learn statistically even allowing richer manipulation preferences of data points.

 \begin{theorem}
\label{thm:strat-vc}
Consider strategic linear classification  \probL{}. For any \emph{instance-invariant} cost function $c(\z; \x) = l(\z -\x)$ where   $l$ is a semi-norm, we have SVC$(\mathcal{H}_d, R, c)=d+1-\dim(V_l)$ for any bounded $R$, where $V_l$ is the largest linear space contained in the ball $\mathcal{B}=\{\x: l(\x)\leq 1\}$.

In particular, if $l$ is a norm (i.e.,  $l(\x) = 0$ \emph{iff} $\x=0$), then  $\dim(V_l)=0$ and SVC$(\mathcal{H}, R, c)=d+1$.
\end{theorem}
\begin{proof}[Proof Sketch]
The key idea of the proof relies on a careful construction of a linear mapping which, given any set of samples $\{ (\x_i, y_i, r_i) \}_{i=1}^n$,  maps   the class of linear classifiers to  the vector space of points' utilities and moreover, the sign of each data point's utility will correspond exactly to the label of the data point after its strategic manipulation. Using the structure of this construction, we can identify  the relationship between the dimension of the linear mapping and the strategic VC-dimension. By bounding the dimension of the space of signed agent utilities, we are able to derive the SVC though with some involved algebraic argument to exactly pin down the dimension of the linear mapping due to possible degeneracy of $V_l$ ball.
\end{proof}

\subsection{The Complexity of   Strategic Linear Classification}
In this subsection, we turn our attention to the computational efficiency of learning.  The standard ERM problem for linear classification to minimize the 0-1 loss is already known to be NP-hard in the general agnostic learning setting \cite{feldman2012agnostic}. This implies that agnostic PAC learning by SERM is also NP-hard in our strategic setup. Therefore, our computational study will focus on the more interesting PAC-learning case, that is, assuming there exists a strategic linear classifier that perfectly separates all the data points. In the non-strategic case, the ERM problem can be solved easily by a linear feasibility problem.

It turns out that the presence of gaming behaviors does make the resultant SERM problem significantly more challenging. We prove essentially tight computational tractability results in this subsection. Specifically, any strategic linear classification instance can be efficiently PAC-learnable by the SERM   when the  problem exhibits some ``adversarial nature''. However, the SERM problem  immediately becomes NP-hard even when we go  slightly beyond such adversarial situations. We start by defining what we mean by ``adversarial nature'' of the problem.

\begin{definition}[Essentially Adversarial Instances]
For any strategic classification problem \prob{}, let
\begin{equation}
\begin{aligned}
      &  \text{ min}^- = \qopname\relax n{min}\{r: (\x, y, r)   \text{ with }  y = -1\} \, \,   \text{ and } \\ & \, \,   \text{max}^+ = \qopname\relax n{max}\{r:   (\x, y, r)  \text{ with }  y = +1 \}
\end{aligned}
\end{equation}
be the minimum reward among all $-1$ points   and the maximum reward among all $+1$ points, respectively. We say the instance is  ``\emph{adversarial}'' if $\qopname\relax n{min}^- \geq 0 \geq  \qopname\relax n{max}^+$ and is ``\emph{essentially adversarial}'' if $\qopname\relax n{min}^- \geq \qopname\relax n{max}^+$.
\end{definition}

In other words, an instance is  ``adversarial'' if each data point would like to move to the opposite side of its label though with different magnitudes of preferences, and is ``essentially adversarial'' if any negative data point has a stronger preference to move to the positive side than any positive data point. Many natural settings are essentially adversarial, e.g., all the four examples  in Subsection \ref{sec:prelim:cases}.

Our first main result of this subsection (Theorem \ref{thm:determistic-easy}) shows that when the strategic classification problem exhibits the above adversarial nature, linear strategic classification can be efficiently PAC-learnable by SERM. The second main result Theorem \ref{thm:determistic-hard} shows that the SERM problem  becomes NP-hard once we go slightly beyond the adversarial setups identified in Theorem \ref{thm:determistic-easy}. These results show that the computational tractability of strategic classification is primarily governed by the preference set $R$. Interestingly, this is in contrast to the statistical learnability results in Theorem \ref{thm:svcinfinite} and \ref{thm:strat-vc} where the preference set $R$ did not play much role.

\begin{theorem}\label{thm:determistic-easy}
Any separable strategic linear classification instance \probL{} is efficiently PAC-learnable by the SERM in polynomial time in the following two situations:
\vspace{-4mm}
\begin{enumerate}
    \item The problem is \emph{essentially} adversarial ($\qopname\relax n{min}^-  \geq  \qopname\relax n{max}^+$) and  cost function $c(\z;\x)=l(\z-\x)$ is  instance-invariant and induced by  seminorm $l$. \vspace{-1mm}
    \item  The problem is  adversarial ($\qopname\relax n{min}^- \geq 0 \geq  \qopname\relax n{max}^+$) and the instance-wise cost function $c(\z;\x) =l_{\x}(\z-\x)$ is induced by seminorms $l_{\x}$.
\end{enumerate}
\end{theorem}
\begin{proof}[Proof Sketch]
For situation 1, we can formulate the SERM problem as the following feasibility problem:
\begin{lp*}
\find{  \w, b,   \epsilon >0   }
\mbox{s.t.}
\qcon{  \w \cdot \x_i + b   \geq  -r_i     }{  y_i =1 }
\qcon{    \w \cdot \x_i + b  \leq -(r_i + \epsilon)   }{  y_i = -1 }
\con{ l^* (\w) = 1}
\end{lp*}
where $l^*$ is the dual norm of $l$.

This unfortunately is not a convex program due to the non-convex constraint $l^* (\w) = 1$ --- indeed we prove later that this program is NP-hard to solve in general. Therefore, instead, we solve a relaxation of the above program, by relaxing constraint $l^* (\w) = 1$ to $l^* (\w) \leq 1$ to obtain a convex program. The crucial step of our proof is to show that this relaxation is tight under the \emph{essentially} adversarial assumption. This is proved by converting any optimal solution of the relax convex program to a feasible and optimal solution to the original problem. This is the crucial and also difficult step since the solution to the relaxed convex program may not satisfy $l^* (\w) = 1$ --- in fact, it will satisfy $l^* (\w) < 1$ generally which is why the original program is NP-hard in general. Fortunately, using the essentially adversarial assumption, we are able to employ a carefully crafted construction to generate an optimal solution the the above non-convex program.

For situation 2, we can formulate it as another \emph{non-convex} program with parameter $\w, \epsilon$:
\begin{lp*}
\find{  \w, b,   \epsilon >0   }
\mbox{s.t.}
\qcon{  \w \cdot \x_i + b   \geq (-r_i) \cdot l^*_{\x_i}(\w)}{ r_i < 0}
\qcon{    -( \w \cdot \x_i + b )  \geq (r_i + \epsilon) \cdot l^*_{\x_i}(\w)  }{  r_i \geq 0 }
\end{lp*}
Fortunately, for any fixed $\epsilon>0$, the above program is convex in variable $\w$.   Moreover, if the system is feasible for   $\epsilon_0>0$ then it is feasible for any $0 < \epsilon \leq \epsilon_0$. This allows us to determine the feasibility  problem above for any $\epsilon$ via binary search, which overall is in polynomial time.
\end{proof}
Our next result shows that the positive claim in Theorem \eqref{thm:determistic-easy} are essentially the best one can hope for. Indeed, the SERM immediately becomes NP-hard if one goes slightly beyond the two tractable situations in  Theorem \eqref{thm:determistic-easy}. Note that our results did not rule out the possibility of other computationally efficient learning algorithms other than the SERM. We leave this as an intriguing open problem for future works.
\begin{theorem}\label{thm:determistic-hard}
Suppose the strategic classification problem is linearly separable, then the SERM Problem   for linear classifiers is NP-hard in the following two situations:
\begin{enumerate}
    \item Preferences are arbitrary and the cost function is instant-invariant and induced by the standard $l_2$ norm, i.e., $c(\z; \x) = \|\x - \z||_2^2$.
     \item The problem is \emph{essentially} adversarial ($\qopname\relax n{min}^-  \geq  \qopname\relax n{max}^+$) and the cost function is  instance-wise and induced by  norms.
\end{enumerate}
\end{theorem}

\begin{remark}
Theorem \ref{thm:strat-vc}, Theorem \ref{thm:determistic-easy} and Theorem \ref{thm:determistic-hard} together imply that
for strategic linear classification:\\
(1) the problem is efficiently PAC-learnable (both statistically and computationally)  when the cost function is instance-invariant and preferences are essentially adversarial;\\
(2) SERM can be solved efficiently but SVC is infinitely large when the cost function is instance-wise and   preferences are adversarial;\\
(3) the problem is efficiently PAC learnable  in statistical sense, but SERM is NP-hard when  the cost function is instance-invariant and preferences are arbitrary.

\end{remark}

\section{Model}
\label{sec:prelim}

{\bf Basic Setup. }We consider binary classification, where each data point is  characterized by a tuple $(\x, y, r)$. Like classic classification setups,  $\x \in \mathcal{X} $ is the feature vector and $y \in \{ +1, -1\}$ is its label. The only difference of our setup from classic classification problems is the additional   $r \in R \subseteq  \mathbb{R}$, which is the data point's (positive or negative) preference/reward of being labeled as $+1$. The data point's reward for label $-1$ is, without loss of generality,  normalized to be $0$.  A classifier is a  mapping $h:\mathcal{X}  \to \{ +1, -1\}$. Our model is essentially the same as that of \cite{hardt2016stratclass,miller2019strategic}, except that the $r$ in our model can be any real value from set $R$ whereas the aforementioned works assume $r=1$ for all data points.
Notably, we also allow $r$ to be \emph{negative}, which means some data points   prefer to be classified as label $-1$.  This generalization is natural and very useful because  it allows much richer  agent preferences. For instance, it casts the adversarial/robust  classification problem  as a special case of our model as well (see discussions later). Intuitively, the set $R$ captures the richness of agents' preferences. As we will prove, how rich it is will affect both the statistical learnability and computational tractability of the learning problem.

 \begin{figure}[ht]
    \centering
    \includegraphics[scale=0.35]{figures/ex5.png}
    \caption{Example illustration of our setup. The line is a linear classifier. Points $\x_3, \x_4$ have incentive to cross the boundary  whereas $\x_1, \x_2$ do not. The dotted cycles contain all manipulated features which have moving cost exactly $1$ and they can be different for different points (i.e., instance-wise costs).}
    \label{fig:ex1}
\end{figure}
\noindent
\textbf{The Strategic Manipulation of \emph{Test} Data.} We consider strategic behaviors during the \emph{test} phase and assume that the training data is unaltered/uncontaminated. An illustration of the setup can be found in Figure \ref{fig:ex1}.  A generic \emph{test} data point is denoted as $(\x, y, r)$.  The  test data point  is strategic and may shift its feature to vector $\z$ with cost $c(\z; \x)$  where $c: \mathcal{X} \times \mathcal{X}  \to \mathbb{R}_{\geq 0}$. In general,  function $c$ can be an arbitrary non-negative cost function. In our study of strategic linear classification, we assume the cost functions are induced by  \emph{seminorms}. We will consider the following two   types of cost functions, with increasing generality.
\begin{enumerate}
 \vspace{-2mm}
   \item  {\bf Instance-invariant cost functions:} A cost function $c$ is \emph{instance-invariant} if there is a common function $l$ such that $c(\z; \x) = l(\z - \x)$ for any point  $(\x, y, r)$.
 \vspace{-2mm}
  \item {\bf  Instance-wise  cost functions:} A cost function $c$ is  \emph{instance-wise}  if  for each data point $(\x, y, r)$, there is a function $l_{\x}$ such that $c(\z; \x) = l_{\x}(\z - \x)$. Notably, $l_{\x}$ may be different for different data point $(\x, y, r)$.  \vspace{-2mm}
\end{enumerate}
Both cases have been considered in previous works. For instance, the separable cost function studied in \cite{hardt2016stratclass} is instance-wise, and the cost function induced by a seminorm  as assumed by the main   theorem  of \cite{cullina:nips18} is instance-invariant. We shall prove later that the choice among these two types of cost functions will largely affect the efficient learnability of the problem.

Given a classifier $h$, the strategic test data point $(\x,  y, r)$ may shift its feature vector to $\z$ and would like to pick the best such $\z$ by solving the following optimization problem:
\begin{equation}\label{def:bestResponse}
\begin{aligned}
& \text{Data Point Best Response: } \\
& \Delta_c(\x,r;h) = \arg \qopname\relax n{max}_{\mathbf{z} \in \mathcal{X}} \big[  \mathbb{I}(h(\z) = 1) \cdot r - c(\z;\x) \big].
\end{aligned}
 \vspace{-2mm}
\end{equation}
where $\mathbb{I}(S)$ is the indicator function and $[  \mathbb{I}(h(\z) = 1) \cdot r - c(\z;\x) ]$ is the quasi-linear \emph{utility function} of data point $(\x,y, r)$. We call $\Delta_c(\x, r;h)$  the  \emph{manipulated feature}. When there are multiple best responses, we assume the data point  may choose any best response and thus will adopt the standard  \emph{worst-case} analysis.
Note that the test data's strategic behaviors do  \emph{not} change its true label.  Such strategic  \emph{gaming} behaviors differs from  strategic \emph{improvements}  (see \citeyearpar{miller2019strategic} for more discussions on their differences).

  \vspace{-1mm}
\subsection{The Strategic Classification (\textsc{StraC}) Problem}
A \textsc{StraC}{} problem is described by a  hypothesis class $\mathcal{H}$,  the set of preferences $R$ and a manipulation cost function $c$. We thus denote it as \prob{}. Adopting the standard statistical learning framework,  the input to our learning task are $n$ \emph{uncontaminated} \emph{training} data points $(\x_1, y_1, r_1), \cdots, (\x_n, y_n, r_n)$ drawn independently and identically (i.i.d.) from distribution $\mathcal{D}$.  Given these training data, we look to learn a classifier $h\in \mathcal{H}$ which  minimizes the basic 0-1 loss,   defined as follows:
\begin{equation}\label{eq:def:straExpLoss}
\begin{aligned}
   & \text{Strategic 0-1 Loss of classifier }h: \\ & L_c(h;\mathcal{D}) = \qopname\relax n{\mathbf{Pr}}_{(\x,y, r) \sim \mathcal{D}} \big[ h(\Delta_c(\x,r;h)) \not = y) \big].
\end{aligned}
 \vspace{-2mm}
\end{equation}
Notably, the classifier $h$ in the above loss definition takes the manipulated feature $\Delta_c(\x,r;h))$ as input and, nevertheless, looks to correctly predict the true label $y$.
For notational convenience, we sometimes omit $c$ when it is clear from the context and simply write $\Delta (\x,r;h)$ and $L(h;\mathcal{D})$.

 \vspace{-1mm}
\subsection{Notable Special Cases }\label{sec:prelim:cases}
Our strategic classification model  generalizes several models studied in previous literature, which we now sketch.\\

{\bf Non-strategic classification. } When $R = \{ 0 \}$  and $c(\z;\x)>0$ for  any $\x \not =\z$, our model degenerates to the standard non-strategic setting.\\
{\bf  Strategic classification with homogeneous preference.}  When $R = \{ 1 \}$, our model degenerates to the strategic classification model  studied in prior work \cite{hardt2016stratclass,hu:fat19,milli:fat19}---here all data points have the same incentive of being classified as $+1$.\\
{\bf Adversarial Classification. } When $R = \{ 1, -1 \}$  (or $\{\delta, -\delta\}$,$\delta\neq 0$), our model becomes the adversarial classification problem \citeyearpar{cullina:nips18,awasthi2019robustness}, where each data point can adversarially move to induce the \emph{opposite} of its true label ---  within the ball of radius $1$ induced by cost function $c$. Our Proposition \ref{prop:svc=avc} provides formal evidence for this connection.\\
{\bf Generalized Adversarial Classification. } An interesting generalization of the above adversarial classification setting is that $r < 0$ for all data points with true label $+1$ and $r>0$  for all data points with true label $-1$. This captures the  situation where each point has different ``power'' (decided by $|r|$) to play against the classifier. To our knowledge, this generalized setting has not been considered before.
    Our results yield new efficient statistical learnability and computational tractability for this setting.

\section{The Power and Limits of Randomization}\label{sec:rand}
It is well-known that in standard classification, randomization over the classifiers cannot result in strictly smaller loss. Interestingly, it turns out that randomization can lead to strictly smaller loss in strategic classification, as we  show in this section.  We start by defining randomized classifiers as follows.

\begin{definition}[Randomized Binary Classifiers] A binary classifier $H$  is called a randomized classifier over \emph{any} hypothesis class $\mathcal{H}$ (not necessarily linear classifiers) if there exists a set of deterministic classifiers $\{h_1,\ldots, h_k\} \subseteq \mathcal{H}$, and a probability vector $\mathbf{p} = \{p_1,\ldots, p_k\}$ with $\sum_j p_j = 1$, such that for any input feature $\x$, $H(\x) = h_j(\x)$ with probability $p_j$.
\end{definition}

The capital $H$ notation is to distinguish randomized classifiers from deterministic ones, and can be viewed as a random variable. Since we always focus on binary classification,  we simply say randomized classifiers henceforth. Note that randomized classifier should not be confused with classification methods like logistic regression or ensemble methods (e.g., random forest), which ultimately still output a deterministic label. The following proposition, whose proof is deferred to Appendix \ref{append:sec:rand:rand-2D-linear}, shows that randomization can help in strategic linear classification.

\begin{proposition}\label{prop:rand-2D-linear}
There are strategic classification instances which are perfectly separable by a \emph{randomized} linear classifier  but not by  any deterministic linear classifier.  This is true even when all data points have the same reward value $r$.
\end{proposition}

The advantages of randomized classifiers over deterministic classifiers  fundamentally comes from the strategic data points' tradeoff between two factors: (a) manipulation cost; (b) the gain from classification outcomes. Interestingly, \emph{if any of these two factors is absent, then randomization will not be beneficial}. First, if there is no gain from classification outcome (i.e., $r=0$ for any data point), then naturally the data points have no benefit to move and thus will stay put. This is precisely the classic classification setup. Second, our following result shows that if data points have no moving cost, randomization will not help neither in the separable case. Formally, we consider a special type of strategic classification where each data point is constrained to move within a designated region which can be \emph{arbitrary} (even can be unconnected) and has no moving cost, i.e., $c(\z; \x) = 0$ for any feasible move. We term this the \emph{zero-manipulation-cost} strategic classification. Note that the adversarial or robust classification setup falls into this case \cite{cullina:nips18,awasthi2019robustness}.

\begin{theorem}
\label{thm:rand-no-help}
 Consider \emph{zero-manipulation-cost} strategic classification. For any hypothesis class $\mathcal{H}$, if there is a randomized  classifier over $\mathcal{H}$ that perfectly separates the positive points from the negative (i.e., achieving $0$   loss), then there must exist a deterministic  classifier in $\mathcal{H}$ that achieves so as well.
\end{theorem}

In adversarial classification, it is usually assumed that each data point can move  within a $\delta$-ball around it with no cost.
An immediate corollary of Theorem \ref{thm:rand-no-help} is the following.
\begin{corollary}
Randomization does not help in any perfectly separable adversarial classification problems.
\end{corollary}

We remark that   perfectly separable assumption in Theorem \ref{thm:rand-no-help} is necessary. That is, even for zero-manipulation-cost strategic classification problem, there are non-separable examples where randomized linear classifier can achieve strictly larger accuracy  than any deterministic linear classifier, as shown in the following proposition with proof deferred to Appendix \ref{append:sec:rand:randhelp}.
\begin{proposition}\label{prop:randhelp}
There exists zero-manipulation-cost \emph{non-separable} strategic classification instances in $\mathbb{R}^2$  where the  minimum  risk of any deterministic linear classifier is strictly larger than some randomized linear classifier.
\end{proposition}

\section{VC-Dimension for Strategic Classification}
\label{sec:stratvc}

In this section, we  introduce the notion of \emph{strategic VC-dimension} (SVC) and show that it properly captures the behaviors of a hypothesis class in the strategic setup introduced above. We then show the connection of SVC with previous studies on both strategic and adversarial learning.
Before formally introducing SVC, we first define the shattering coefficients in strategic setups.

\begin{definition}[Strategic Shattering Coefficients]
\label{definition:ssc}
The $n$'th shattering coefficient of any strategic classification problem \prob{} is defined as
\begin{equation}
    \begin{aligned}\label{eq:shattering-coeff}
    & \sigma_n (\mathcal{H}, R, c )= \qopname\relax n{max}_{\bm{(\x,r)} \in \mathcal{X}^n \times R^n}\\ \nonumber
    &|\{(h(\Delta_c(\x_1, r_1; h )) , \cdots, h(\Delta_c(\x_n, r_n;h )):h\in \mathcal{H}\}|,
    \end{aligned}
\end{equation}
where $\Delta_c(\x_i, r_i; h)$   defined in Eq. \eqref{def:bestResponse} is a best response of data point $(\x_i,y_i,r_i)$ to classifier $h$ under cost function $c$.
\end{definition}
That is, $\sigma_n (\mathcal{H}, R, c )$ captures the maximum number of classification behaviors/outcomes (among all choices of data points) that classifiers in $\mathcal{H}$ can possibly induce by using manipulated features as input. Like classic definition of shattering coefficient,  the $\sigma_n (\mathcal{H}, R, c )$ here does not involve the labels of the data points at all. In contrast, in the shattering coefficient definition for adversarial VC-dimension of \cite{cullina:nips18},  the ``$\qopname\relax n{max}$''  is allowed to be over data labels as well. This is an important difference from us.
Given the definition of the strategic shattering coefficients, the definition of strategic VC-dimension is standard.

\begin{definition} \label{definition:svc}
The Strategic VC-dimension (SVC) for  strategic classification problem \prob{} is defined as
\begin{equation}
    \text{SVC}(\mathcal{H},R, c)=\sup \{n \in \mathbb{N}: \sigma_n(\mathcal{H}, R,c)=2^n \}.
\end{equation}
\end{definition}
We show that the SVC  defined above correctly characterizes the learnability of any strategic classification problem \prob{}.   We  consider the standard Empirical risk minimization (ERM) paradigm for strategic classification, but  take into account training data's manipulation behaviors. Specifically, given any cost function $c$, any $n$ uncontaminated  training data points $(\mathbf{x}_1, y_1, r_1), \cdots, (\mathbf{x}_n, y_n, r_n)$ drawn independently and identically (i.i.d.) from the same distribution $\mathcal{D}$,
the \emph{strategic empirical risk minimization} (SERM) problem computes a classifier $h \in \mathcal{H}$ that minimizes the empirical strategic 0-1 loss in Eq. \eqref{eq:def:straExpLoss}. Formally, the SERM    for \prob{} is  defined as follows:
\begin{equation}\label{def:erm}
\begin{aligned}
&\text{SERM} : \quad   \text{argmin}_{h \in \mathcal{H}} \, \,   L_{c}(h, \{ (\x_i,y_i,r_i) \}_{i=1}^n ) \\& = \sum_{i=1}^n \mathbb{I} \big[ h (\Delta_c(\x_i, r_i; h)) \not = y_i \big]
\end{aligned}
\vspace{-2mm}
\end{equation}
where $L_{c}(h, \{ (\x_i,y_i,r_i) \}_{i=1}^n ) $ is the \emph{empirical loss} (compared to the expected loss $L_c(h, \mathcal{D})$ defined in Equation \eqref{eq:def:straExpLoss}).
Unlike the standard (non-strategic) ERM problem and similar in spirit to the ''incentive-aware ERM'' in \cite{zhangincentive}, classifiers in the SERM problem take each data point's strategic response $\Delta_c\ (\x_i, r_i; h) $ as input, while not the original feature vector $\x_i$.

Given the definition of strategic VC-dimension and the SERM framework, we state the sample complexity result for PAC-learning in our strategic setup:

\begin{definition}[PAC-Learnability]
In a strategic classification problem \prob{},  the hypothesis class $\mathcal{H} \subseteq (\mathcal{X} \xrightarrow{} \{+1,-1\})$ is \emph{Probably Approximately Correctly (PAC) learnable} by an algorithm $\mathcal{A}$ if there is a function $m_{\mathcal{H}, R, c}:(0,1)^2 \xrightarrow{}\mathbb{N}$ such that $\forall (\delta,\epsilon) \in (0,1)^2$, for any  $n\geq m_{\mathcal{H}, R, c}(\delta, \epsilon)$ and any distribution $\mathcal{D}$ for $(\x, y, r)$, with at least probability $1-\delta$, we have $L_{c}(h^*, \mathcal{D}) \leq \epsilon$ where $h^*$ is the output of the algorithm $\mathcal{A}$ with $n$ i.i.d. samples from $\mathcal{D}$ as input.  The problem is \emph{agnostic PAC learnable} if  $L_{c}(h^*, \mathcal{D}) - \inf_{h\in\mathcal{H}} L_{c}(h,\mathcal{D}) \leq \epsilon $.
\end{definition}

\begin{theorem}
\label{theorem:probdet-pac}
Any strategic classification instance \prob{} is agnostic PAC learnable with sample complexity $m_{\mathcal{H},R,c}(\delta,\epsilon)\leq C \epsilon^{-2} [d+\log(\frac{1}{\delta})]$ by the SERM in Eq. \eqref{def:erm}, where $d=SVC(\mathcal{H}, R, c)$ is the strategic VC-dimension and $C$ is an absolute constant.
\end{theorem}
\begin{proof}[Proof Sketch]
The key idea of the proof is to convert our new strategic learning setup to a standard PAC learning setup, so that the Rademacher complexity argument can be applied. This is done by viewing the preference $r \in R$ as an additional dimension in the augmented feature vector space. Formally, we consider the new binary hypothesis class $\tilde{H}=\{\kappa_c(h): h\in H\}$, where classifier $\kappa_c$ satisfies $\kappa_c(h) : (\x,r) \mapsto h(\Delta_c(\x, r;h)), \forall (\x, r) \in \mathcal{X} \times R$. It turns out that the SVC defined above captures the VC-dimension for this new hypothesis class $\tilde{H}$. Formally proof can be found in Appendix \ref{sec:append:thm1}.
\end{proof}

Due to space limit, we defer all formal proofs to the appendix. Proof sketches are provided for some of the results.  Next, we illustrate how SVC  connects to previous literature, particularly the two most relevant works by Cullina et al. \cite{cullina:nips18} and Hardt et al. \cite{hardt2016stratclass}.

\subsection{SVC generalizes Adversarial VC-Dimension (AVC)}
We show that SVC generalizes the adversarial VC dimension (AVC) introduced by \cite{cullina:nips18}. We give an intuitive description of AVC here, and refer the curious reader  to  Appendix \ref{prop:svc=avc} for its formal definition. At a high level,  AVC captures the behaviors of binary classifiers under \emph{adversarial} manipulations. Such adversarial manipulations are described by a binary nearness relation $\mathcal{B}\subseteq \mathcal{X}\times\mathcal{X} $ and  $(\z; \x)  \in \mathcal{B}$ if and only if data point with feature $\x$ can manipulate its feature to $\z$.
Note that there is no direct notion of agents' \emph{utilities} or \emph{costs} in adversarial classification since each data point simply tries to ruin the classifier by moving within the allowed manipulation region (usually an $\delta$-ball around the data point). Nevertheless, our next result shows that AVC with binary nearness relation $\mathcal{B}$ always equals  to SVC as long as the set of strategic manipulations induced by the data points' incentives is the same as $\mathcal{B}$.  To formalize our statement, we need the following consistency definition.

\begin{definition}\label{def:bc-consistency}
Given any binary relation $\mathcal{B}$ and any cost function $c$, we say $\mathcal{B},c$ are $r$-consistent if $\mathcal{B} = \{(\z;\x): c(\z;\x) \leq r \}$. In this case, we also say $\mathcal{B}$ [resp. $c$] is $r$-consistent with $c$ [resp. $\mathcal{B}$].
\end{definition}
By definition  any cost function $c$ is $r$-consistent with the natural binary nearness relation it  induces $\mathcal{B}_c  = \{ (\z;\x): c(\z;\x) \leq r \}$.  Conversely, any binary relation $\mathcal{B}$ is $r$-consistent (for any $r>0$) with a natural cost function that is simply an indicator function of $\mathcal{B}$ defined as follows
\begin{equation}
    c_{\mathcal{B}}(\z; \x) = \begin{cases}
\infty, & \text{if } (\z;\x) \in \mathcal{B} \\
0,  & \text{if }  ( \z;\x) \not \in \mathcal{B}
\end{cases}.
\end{equation}
Note that, $\mathcal{B}$ and $c$ may be $r$-consistent for infinitely many different $r$, as shown in the above example with $\mathcal{B}$ and $c_{\mathcal{B}}$.

\begin{proposition} \label{prop:svc=avc}
For any hypothesis class $\mathcal{H}$ and any binary nearness relation $\mathcal{B}$, let AVC$(\mathcal{H}, \mathcal{B})$ denote the adversarial VC-dimension defined in \cite{cullina:nips18}. Suppose $\mathcal{B}$ and $c$ are $r$-consistent for some $r>0$, then we have AVC$(\mathcal{H}, \mathcal{B})=$SVC$(\mathcal{H}, \{+r,-r\}, c)$.
\end{proposition}

 As a corollary of Proposition \ref{prop:svc=avc}, we know that SVC is in general larger than or at least equal to AVC when the strategic behaviors it induces include $\mathcal{B}$. This is formalized in the following statement.

\begin{corollary}
\label{corr:svc-avcrelation}
Suppose a cost function $c$ is $r$-consistent with binary nearness relation $\mathcal{B}$ and $ \pm r \in R$, then we have  $$SVC(\mathcal{H}, R, c)   \geq AVC(\mathcal{H}, \mathcal{B}).$$
\end{corollary}

Corollary \ref{corr:svc-avcrelation} illustrates that for any cost function $c$, the  SVC with a rich preference set $R$  is generally no less than the corresponding AVC under the natural binary nearness relation that $c$ induces. One might wonder how large their gap can be. Our next result shows that for a general $R$  the gap between  SVC and AVC  can be \emph{arbitrarily large}  even in natural setups. The intrinsic reason is that a general preference set $R$ will lead to different extents of preferences (i.e., some data points strongly prefers label $1$ whereas some slightly prefers it). Such variety of   preferences gives rise to more  strategic classification outcomes and renders the SVC larger than AVC, and  sometimes significantly larger, as shown in the following proposition.

\begin{proposition}
\label{prop:svc>avc}
For any integer $n>0$, there exists a hypothesis class $\mathcal{H}$ with point classifiers,  an instance-invariant cost function  $c(\z;\x) = l(\z - \x)$ for some \emph{metric} $c$ and preference set $R$ such that  $ SVC (\mathcal{H}, R, c)= n$ but $VC(\mathcal{H}) = AVC(\mathcal{H}, \mathcal{B}_c(r)) = 1$ for any $ r\in R$  where $\mathcal{B}_c(r) = \{ (\x,\z): c(\z;\x) \leq r \}$ is the natural nearness relation induced by $c$ and $r>0$.
\end{proposition}

\subsection{SVC under Separable Cost Functions} Not only restricting the  set $R$ of preference values can reduce the SVC. This subsection shows that restricting to special classes of cost functions can also lead to a small SVC. One special  class of cost functions studied in many previous works  is the \emph{separable cost functions} \cite{hardt2016stratclass, milli:fat19, hu2019disparate}.
Formally, a cost function $c(\z;\x)$ is separable if there exists function $c_1, c_2: \mathcal{X} \to \mathbb{R}$ such that $c(\z;\x) = \qopname\relax n{max} \big\{ c_2(\z) - c_1(\x), 0 \big\}$.

The following Proposition \ref{prop:svc-separable} shows that when the cost function is separable,  SVC is at most 2 for \emph{any} hypothesis class $\mathcal{H}$ and  any class of preference set $R$.\footnote{ The model of \cite{hardt2016stratclass} corresponds to the case $R = \{ 1\}$ in our model. For that restricted  situation, the proof of Proposition \ref{prop:svc-separable} can be simplified to prove SVC = 1 when $R = \{ 1\}$. It turns out that arbitrary preference set $R$ only increases the SVC by at most $1$.}  Therefore,  separable cost function essentially reduces any classification problem to a problem in lower dimension. Together with Theorem \ref{theorem:probdet-pac}, Proposition \ref{prop:svc-separable} also recovers the PAC-learnability result of   \cite{hardt2016stratclass} in their strategic-robust learning model (specifically, Theorem 1.8 of \citeyearpar{hardt2016stratclass})  and,  moreover, generalizes their learnability from  homogeneous agent preferences  to the case with \emph{arbitrary} agent preference values.

\begin{proposition}\label{prop:svc-separable}
For any hypothesis class $\mathcal{H}$, any preference set $R$ satisfying $0\not \in R$, and  any separable cost function $c(\z;\x)$, we have SVC$(\mathcal{H}, R, c)\leq 2$.
\end{proposition}
The assumption $0 \not \in R$ means each agent must  strictly prefer either label $+1$ or $-1$. This assumption is necessary   since if $0 \in R$, SVC will be at least the classic VC dimension of $\mathcal{H}$ and thus Proposition \ref{prop:svc-separable} cannot hold. We remark that the above SVC upper bound $2$ holds for any hypothesis class $\mathcal{H}$. This bound $2$ is tight for some classes of hypothesis, e.g., linear classifiers.

\section{Summary}
In this work, we propose and study a general strategic classification setting where data points have different preferences over classification outcomes and different manipulation costs. We establish the PAC-learning framework for this strategic learning setting and characterize both the statistical and computational learnability result for linear classifiers. En route, we generalize the recent characterization of adversarial VC-dimension  \cite{cullina:nips18} as well as computational tractability for learning linear classifiers by \cite{awasthi2019robustness}. Our conclusion reveals two important insights. First, the additional intricacy of having different preferences harms the statistical learnability of general hypothesis classes, but \emph{not} for linear classifiers. Second, learning   strategic linear classifiers can be done efficiently only when the setup exhibits some adversarial nature and becomes NP-hard in general.

Our learnability result for linear classifiers applies to cost functions induced by semi-norms. A future direction is to generalize the theory to cost function induced by asymmetric semi-norms or even any metrics. We also note that the strategic classification model we consider is under the full-information assumption, i.e., the cost function and the strategic preferences are transparent. This is analogous to the evasion attack in the adversarial machine learning literature, where the training data is supposed to be uncontaminated and the manipulation only happens during testing. What if we cannot observe the strategic preferences during training or do not know the adversaries' cost function? This can be reformulated as online learning through repeated Stackelberg games and has been studied in \cite{dong:ec18}, but it does not apply to classifiers with 0-1 loss.