Non-Linear Strategic Classification Made Practical
2026-06-26 • Computer Science and Game Theory
Computer Science and Game TheoryMachine Learning
AI summaryⓘ
The authors developed a new way to handle strategic classification when the best response from individuals is hard to compute, especially for non-linear models. They reformulate the problem using Lagrangian duality, turning it into an optimization task that can be solved more easily with standard methods. Their method also uses the Implicit Function Theorem to link how classifier settings affect strategic behavior during training. Experiments show their approach improves the accuracy of models in strategic environments compared to previous methods.
Strategic ClassificationLagrangian DualityConstrained OptimizationImplicit Function TheoremBest ResponseNon-linear ClassifiersFirst Order OptimizationClassifier Training
Authors
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.