Strategic classification

Under a separable cost, acceptance after gaming is a threshold on $c_1$. A contestant ends up accepted iff some accepted $y$ has $c(x,y)\lt2$, that is $c_2(y)\lt c_1(x)+2$, and the cheapest accepted target has the smallest $c_2$, so $$f(\Delta(x))=1\iff c_1(x)\gt\min\{c_2(y):f(y)=1\}-2 .$$ The side conditions enter only here: nonnegativity makes a move to a rejected point useless, and the free option makes a rejected contestant's payoff exactly $-1$. The outcome depends on $f$ only through the single number $s(f)=\min\{c_2(y):f(y)=1\}$.

The jury can restrict to cutoffs on $c_2$, and the strategic maximum is the best cutoff on $c_1$. Replace $f$ by $c_2[s(f)]$: same $s$, hence the same outcome at every $x$. Optimizing over $s$, $$\mathrm{OPT}_h(D,c)=1-\inf_{s\in c_2(X)\cup\{\infty\}}\Pr_{x\sim D}\big[h(x)\ne c_1[s-2](x)\big],$$ with the published rule $c_2[s]$ two cost units above the effective cutoff $c_1[s-2]$ on original features. A brute-force check over all classifiers on small random separable instances matched this formula exactly (my check, not in the paper). In the linear case, moving orthogonally to $\alpha$ is free, so the jury may as well accept a halfspace with normal $\alpha$, and the data choose only its offset.

Empirical risk minimization over $m+1$ candidate cutoffs is exact. The empirical error of $c_1[s-2]$ changes only when $s-2$ crosses some $c_1(x_j)$, and $s_i$ is the highest value of $c_2$ that sample $i$ can reach at cost at most 2, so every distinct empirical behavior is attained among $s_1,\dots,s_{m+1}$. The cutoff must be a value of $c_2$, since a cutoff on $c_1$ at an arbitrary level need not be reachable by any published rule. The search is one-dimensional, which is why the algorithm never has to search $H$.

Uniform convergence, through a Rademacher bound on products. The loss class is $\{h\cdot c_1[s-2]\}$, and for $\pm1$ functions $h\cdot g=|h+g|-1$, so contraction splits its complexity into $R_m(H)$ plus that of the cutoffs, which Massart's lemma bounds by $2\sqrt{\ln(m+1)/m}$ since cutoffs realize at most $m+1$ patterns. Then $$\sup_{h\in H,\,s}\big|\widehat{\mathrm{err}}(s)-\mathrm{err}(s)\big|\le4R_m(H)+8\sqrt{\tfrac{\ln(m+1)}m}+\sqrt{\tfrac{2\ln(2/\delta)}m}\le\tfrac\varepsilon2 .$$ The $R_m(H)$ term is there only for uniformity over targets; for one fixed $h$, the sample size is that of learning a single threshold.

For minima of $k$ separable costs there is one cutoff per piece, and the search grows exponentially in $k$. A contestant uses its cheapest piece, so the accepted set after gaming is a union $\bigcup_b\{b_1(x)\gt s_b-2\}$ with $s_b=\min\{b_2(y):f(y)=1\}$. Replacing $f$ by the intersection of its cutoff sets $\{b_2\ge s_b\}$ leaves every $s_b$ unchanged, and ERM runs over the $(m+1)^k$ grid of candidate vectors, hence $\sqrt{k\ln(m+1)/m}$ and $O(m^k)$. Score each candidate by the actual post-gaming outcome of the rule it publishes: on small two-piece instances that recovered the strategic maximum every time, while the paper's shortcut score returned a worse rule in about 6% of instances, by up to 0.83 in accuracy (my check, not in the paper).

For metrics the problem is NP-hard, by a 3SAT reduction on a two-distance metric. Gaming closes the jury's acceptance set under neighborhoods, which leaves a covering problem with no one-dimensional order to exploit. With distances 1.5 and 2.5 only (the triangle inequality is automatic), close pairs form a graph, and accepting a point accepts all its rejected neighbors. Weighted gadgets (negative literal points, positive clause-pair points, linking points for non-contradictory literal pairs) make accepting anything profitable exactly when one literal per clause can be chosen with no two contradictory, that is, when the formula is satisfiable, with a gap that is a $|X|^{-\eta}$ fraction of the population.

In Hardt's experiment the strategy-robust classifier beats an SVM once gaming is substantial. On review spam with hand-assigned linear costs and deliberately misspecified simulated gaming, the strategy-robust classifier beats a linear SVM once gaming reaches about half a unit, and tolerates misspecification up to about $\sin\theta=0.7$; the SVM is as good with almost no gaming. One data set, results in figures only.

Existence is standard, and uniqueness reduces to positive definiteness of a weighted pseudo-Jacobian. Each cost is continuous and strictly convex in the player's own action on a compact convex set, so the classical existence theorem for convex games applies. For uniqueness, split the generator into $n$ players, one per instance, which keeps the equilibria (its cost is convex over a product set) and allows one Rosen weight per block. The equilibrium is unique if $$g_r(w,\dot x)=\big(r_0\nabla_w\hat\theta_{-1},\ r_1\nabla_{\dot x_1}\hat\theta_{+1},\ \dots,\ r_n\nabla_{\dot x_n}\hat\theta_{+1}\big)$$ is strictly monotone (Rosen's diagonal strict concavity, with signs flipped for costs), for which it suffices that its nonsymmetric Jacobian $J_r$ satisfies $z^\top J_rz\gt0$ everywhere; the weights $r_0=1$, $r_i=c_{-1,i}/c_{+1,i}$ rescale the generator's instance weights to the learner's.

The curvature part is a sum of squares exactly when the curvatures agree. Differentiating twice gives curvature entries $c\,\ell''$ (the score is a scalar index) and coupling entries $c\,\ell'\,I$ (the score is bilinear). With $\ell''_{-1}=\ell''_{+1}$ and the weights above, the curvature part is $$z^\top J^{(1)}z=\sum_ic_{-1,i}\,\ell''_{-1,i}\,\big(z_0^\top\dot x_i+z_i^\top w\big)^2\ge0 ,$$ the curvature of the loss along the change in each score. It is never definite: $z_0=-w$, $z_i=\dot x_i$ leaves every score unchanged to first order, so definiteness has to come from the regularizers. With unequal curvatures the square structure is lost, and the paper warns the equilibrium may then not be unique.

In the coupling only the slopes that fail to cancel count, and the regularizers must dominate them. Definiteness depends only on the symmetric part of the Jacobian, in which the antagonistic difference of the two slopes is skew and drops out. Put the regularizers' floors $\rho_v\lambda_v$ on the diagonal (their excess is positive semidefinite by condition (iii)); after a diagonal congruence, which keeps the signs of the eigenvalues, twice the symmetric part is an arrowhead matrix with spokes $\tilde c_i=\sqrt{c_{-1,i}c_{+1,i}}\,(\ell'_{-1,i}+\ell'_{+1,i})$ and eigenvalues $2\rho_{+1}\lambda_{+1}$ and $$\rho_{-1}\lambda_{-1}+\rho_{+1}\lambda_{+1}\pm\sqrt{(\rho_{-1}\lambda_{-1}-\rho_{+1}\lambda_{+1})^2+\textstyle\sum_i\tilde c_i^2},$$ all positive iff $\sum_i\tilde c_i^2\lt4\rho_{-1}\rho_{+1}\lambda_{-1}\lambda_{+1}$, which (ii) guarantees. For Nash logistic regression, on spam the slopes sum to $\tanh(z/2)$, which vanishes at the decision boundary, so the players are exactly opposed there; on legitimate mail they add to $2\sigma(z)$, since both want a low score. The condition is on the product of the regularization strengths, so a generator that moves cheaply (small $\rho_{+1}$) forces a strongly regularized learner. In a small random instance definiteness failed at half the certified product once the action sets allowed large scores (my check, not in the paper), though a failed certificate does not by itself produce a second equilibrium.

Both solvers rely on the same monotonicity. One descends the weighted Nikaido-Isoda gap, the sum of each player's best unilateral cost saving, which is zero exactly at equilibrium; when $J_r$ is positive definite the direction to the players' best responses is a descent direction, so an Armijo line search along it works. The other is a projected extragradient method on the variational inequality $g_r(z^*)^\top(z-z^*)\ge0$, which converges because $g_r$ is strictly monotone and needs only projections onto balls.

The leader-follower version reduces to one level because the follower's best response is a shift along the model. In Brückner and Scheffer (2011) the learner commits to $w$ and the generator best-responds; the Stackelberg equilibrium solves a bilevel problem. With squared-distance transformation cost, a convex differentiable generator loss and an unconstrained feature space, the follower's problem is strictly convex and its solution moves each point along $w$: $$\dot x_i=\phi(x_i)+\tau_iw,\qquad\tau_i=-\frac n{\rho_{+1}}\,c_{+1,i}\,\ell'_{+1}\big(f_w(x_i)+\tau_i\|w\|^2,\,y_i\big).$$ The bilevel problem becomes a nonconvex single-level one in $(w,\tau)$ with $n$ scalar constraints, solved by SQP to a KKT point. The Nash game's first-order condition gives the same shift at an interior equilibrium (my own observation); the difference is that the Stackelberg leader differentiates through $\tau_i(w)$, and so knows that a longer $w$ invites a larger attack, while the Nash learner treats $\dot x$ as fixed. The 2011 paper takes Nash to fit an adversary who cannot see the model and Stackelberg one who can probe it.

In Brückner's experiments the Nash models beat the baselines on later email in three of four corpora. On four chronologically sorted email corpora, the two solvers agree from random starts even when the bound is violated by a factor of up to 4. Forward in time, the Nash models beat logistic regression, the SVM and the invariance SVM on three corpora, with no significant gain on the short-period TREC 2007. On unshifted data the plain baseline is better (F-measure 0.957 against 0.924 on the provider corpus). The weak points: $\rho_{+1}$ barely affects hold-out F-measure, so the adversary's regularization cannot be estimated from data and is fixed by hand; training costs up to 150 times the baseline; and robustness is tested against the very attack the model assumed. The equilibrium transform barely edits legitimate mail, but it is computed mostly outside the certificate: wherever the transform is visibly large the product $\rho_{-1}\rho_{+1}$ fails the sufficient condition by a factor of more than 13, beyond the range where the solvers were seen to agree (my check, not the paper's).

Consequences and limits. Under a separable cost the defender's best accuracy is fixed by the cost structure: in the linear case the weight on a feature is its cost of manipulation, whatever its predictive value, so a fraud model facing adaptive fraudsters should weight signals that are expensive to fake (account age, device and payment history), with the data setting only the threshold. The Nash learner trains on the adversary's best-response copy of the data, like adversarial augmentation with an attack budget set by $\rho_{+1}$, the one parameter the data could not set. The limits are shared: one round, a deterministic response under a single known cost (Hardt's contestants have no private cost type; Brückner's game assumes complete information and one representative adversary), and no agents who learn the rule from outcomes or forecast the learner's update. Brückner's equilibrium is defined on the transformed training sample, with no generalization theory.