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.

在一个在线的战略分类问题中，每个到达的代理可以操纵其真实特征向量以获得正面的预测标签，同时付出依赖于操纵量的成本。学习者在仅能访问操纵后的特征的情况下，试图预测代理的真实标签。之后学习者公布其预测，代理的真实标签被揭示。我们提供两种新算法，旨在在战略代理行为的情况下恢复最大边界分类器。我们证明了各种代理成本结构的收敛性、有限错误和有限操纵保证。我们还提供了针对不同成本的具有错误保证的战略感知器的广义版本。我们对真实数据和人工合成数据进行的数值研究表明，新算法在边界、操纵数量和错误数量方面优于以前的算法。