Non-Linear Strategic Classification Made Practical
Jack Geary, Boyan Gao, Henry Gouk · 2026
Read Non-Linear Strategic Classification Made Practical by Jack Geary, Boyan Gao, Henry Gouk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28204.txt.
Introduction
Jack Geary, Boyan Gao, and Henry Gouk study strategic classification, where people change their features, such as reported income, to earn a favorable decision from an algorithm. Most theory assumes a simple linear decision rule because predicting how people respond to a complex, nonlinear rule is computationally hard.
Geary and colleagues recast a person's best response as a constrained optimization problem and build a Lagrangian, a standard reformulation that folds constraints into the objective. That version yields to fast first-order methods and matches the known answers for linear rules. Using the implicit function theorem, they also train the classifier while accounting for the responses it will provoke. Their models earned better strategic accuracy on common benchmark datasets.
Catalog record
| CREATOR | Jack Geary, Boyan Gao, Henry Gouk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28204
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Non-Linear Strategic Classification Made Practical Jack Geary, Boyan Gao, Henry Gouk Abstract Algorithmic developments in Strategic Classification have been mostly limited to linear classifiers in settings where the best response has a closed-form solution or can be easily approximated. While some work has explored the role of non-linear classifiers in strategic settings, progress in this direction is impeded by the computational intractability of the strategic behaviour. Addressing this, we present a novel method for approximating the best response by exploiting Lagrangian duality. By reformulating the strategic response as a constrained optimisation problem, we can construct a Lagrangian that is amenable to first order optimisation methods. This approach reproduces closed-form strategic behaviour in linear settings and can be straight-forwardly applied to non-linear settings. We show how the Implicit Function Theorem can be used in conjunction with our proposed response formulation during classifier learning to compute the total gradient of the loss. This connects the classifier parameters directly to the consequent strategic behaviour, yielding a novel training algorithm that can exploit this relationship. Experimental evaluation shows that the resulting models achieve improved strategic accuracy on common machine learning datasets. [removed for review] 1 Introduction Those with a preference for a certain classification, and knowledge of the classifier that is being used, have an incentive to misrepresent their state to receive a favourable outcome 15 . This dynamic can arise in many sociotechnical situations, spanning from universities deciding which students to enrol as far as institutions determining how to distribute aid and resources in times of need. However the phenomenon is broader than classically considered sociotechnical situations: such strategic behaviour can arise in a broader range of applications than just those that deal with classifying individuals. For example, such dynamics are also a concern in applications of machine learning to protein synthesis ( 34 ) and designing benchmarks for generative AI ( 21 ) . While certain applications are well-served by simple linear models, in many cases deep neural networks have been shown to provide excellent predictive performance. Strategic classification addresses settings where a Learner attempts to classify a population of Agents who strategically perturb their representations to optimise a utility known to both players ( 15 ; 2 ) . The Learner’s goal is to develop a classifier that remains robust to these perturbations, thereby minimising the impact of manipulation. However, computing the optimal response is a significant challenge, as it is typically discontinuous and non-differentiable in most cases. Consequently, much of the existing literature focuses on linear classifiers, which can allow for closed-form expressions of the best response in some situations ( 18 ; 19 ; 6 ) . While this focus on linearity is advantageous for the interpretability required in sociotechnical scenarios, it limits the scope of research and the potential for applying these developments to less socially sensitive settings that could benefit from more flexible models. To address this limitation we observe that the Agents’ objective can be reformulated as a constrained optimisation problem. This admits the utilisation of the Karush Kuhn Tucker (KKT) assumptions to derive the Lagrangian dual corresponding to the problem ( 17 ) . Since the optima of the Lagrangian dual correspond to the optima of the original optimisation problem, it can be used as a surrogate method for approximating the Agents’ best response in general settings. We show that in simple environments our Lagrangian dual-based method for computing the best response better approximates the expected best response than existing gradient-based approaches. Moreover, leveraging this novel method for computing responses to yield an expression for the total derivative of the strategic classification objective. This enables us to explore the utility of directly optimising the standard learning objective, rather than resorting to approaches that optimise for a different solution concept. In summary, we make the following contributions: • We propose a novel method for approximating the best response to a given classifier based on the Lagrangian Dual of an alternate formulation of the Agents’ objective. This method addresses key weaknesses in current response approximation methods, and can be directly applied in settings with linear or non-linear classifiers. • We observe that the Lagrangian Dual response formulation provides a model for relating the learned parameters to the Agents’ behaviour. We propose a novel training algorithm that uses the Implicit Function Theorem to exploit this relationship and demonstrate that the resulting models show improved strategic accuracy on various real world datasets. • We identify a property of some response methods, reputability , indicating a method reliably identifies Agent states that are vulnerable to gaming. We prove that the agreement between reputable response methods and the true best response is monotonically related to the number of points the gamed by the response method, allowing for the comparison of different response methods in non-linear settings, without requiring a source of ground-truth gaming behaviour. 2 Related Work Building off of the setting established by 2 ; 14 , Strategic Classification was originally formulated by 15 15 . This models the classifier learning problem as an interaction between a Learner attempting to construct a classifier, and Agents that have perfect awareness of the classifier and can pay perturb their state before being classified. It is assumed that Agents receive positive utility from positive classification, and that the costs the Agents can pay to change their state is known to both the Agents and the Learner. The resulting optimisation problem is generally computationally intractable; in order to empirically evaluate their algorithm, 15 make the simplifying assumption that the learned classifier is a linear SVM model 15 . Subsequent works in this area have relaxed some of the assumptions made in the original paper; 3 weaken the assumption that the Agents know the Learner’s classifier, 19 assume that Agents can have a preference for positive or negative classification, 29 examines the consequences when the Agents’ cost function is unknown to the Learner, and 31 ; 1 ; 11 explore the setting where there is randomness or uncertainty in the classifier learned by the Learner. However, all of these relaxations are considered exclusively in the setting where the classifier being learned is a linear model, and the results are primarily demonstrated on small-scale toy datasets. 32 32 explicitly explore strategic behaviour for non-linear classifiers. However, their principal motivation is on demonstrating the possible effects of strategic behaviour, and are able to realise this experimentally without having to explicitly compute the best response. ( 18 ) also consider applications of their approach to non-linear classifiers, in the form of recurrent neural network models applied to time series data. However, their solution approach still necessarily relies on model convexity in the inputs, which is not generally true in non-linear settings. A central motivation for the widespread adoption of the linear classifier in Strategic Classification research is its theoretical simplicity, and that its best response has a closed form definition. This makes it possible to learn strategically robust linear classifiers without actually having to solve the bilevel optimisation problem inherent to the standard problem formulation. This is often used in Strategic Classification literature (e.g., ( 18 ; 19 ; 6 ) ). While this facilitates practical experimentation, it limits results to linear models. Some work has been done