Strategic classification, i.e. classification under possible strategic
manipulations of features, has received a lot of attention from both the
machine learning and the game theory community. Most works focus on analysing
properties of the optimal decision rule under such manipulations. In our work
we take a learning theoretic perspective, focusing on the sample complexity
needed to learn a good decision rule which is robust to strategic manipulation.
We perform this analysis by introducing a novel loss function, the
\emph{strategic manipulation loss}, which takes into account both the accuracy
of the final decision rule and its vulnerability to manipulation. We analyse
the sample complexity for a known graph of possible manipulations in terms of
the complexity of the function class and the manipulation graph. Additionally,
we initialize the study of learning under unknown manipulation capabilities of
the involved agents. Using techniques from transfer learning theory, we define
a similarity measure for manipulation graphs and show that learning outcomes
are robust with respect to small changes in the manipulation graph. Lastly, we
analyse the (sample complexity of) learning of the manipulation capability of
agents with respect to this similarity measure, providing novel guarantees for
strategic classification with respect to an unknown manipulation graph.

本文研究了利用学习理论来生成具有鲁棒性的决策规则，以及针对机器学习领域中存在的潜在的策略操纵问题，提出了一种新的损失函数，称为策略操纵损失，分析了在已知操纵网络结构和未知操纵网络结构下的学习样本复杂度，并且基于迁移学习技术，定义了一种相似度度量，用于度量操纵网络结构的相似度，得到了具有鲁棒性的学习结果。