Mistake, Manipulation and Margin Guarantees in Online Strategic
  Classification
Lingqing Shen Nam Ho-Nguyen Khanh-Hung Giang-Tran Fatma Kılınç-Karzan
We consider an online strategic classification problem where each arriving
agent can manipulate their true feature vector to obtain a positive predicted
label, while incurring a cost that depends on the amount of manipulation. The
learner seeks to predict the agent's true label given access to only the
manipulated features. After the learner releases their prediction, the agent's
true label is revealed. Previous algorithms such as the strategic perceptron
guarantee finitely many mistakes under a margin assumption on agents' true
feature vectors. However, these are not guaranteed to encourage agents to be
truthful. Promoting truthfulness is intimately linked to obtaining adequate
margin on the predictions, thus we provide two new algorithms aimed at
recovering the maximum margin classifier in the presence of strategic agent
behavior. We prove convergence, finite mistake and finite manipulation
guarantees for a variety of agent cost structures. We also provide generalized
versions of the strategic perceptron with mistake guarantees for different
costs. Our numerical study on real and synthetic data demonstrates that the new
algorithms outperform previous ones in terms of margin, number of manipulation
and number of mistakes.