Optimal Stochastic Decision Rule for Strategic Classification

The decision problem of strategic classification is one where the classifier knows the underlying classification rule as opposed to learning it from the data. The classifier has to perform classification in the presence of a startegic agent who can manipulate the feature vector at a cost to obtain their desired label. Such strategic behaviour results in errors, necessitating the classifier to adjust the decision rule to account for the adversary's actions. In this paper, we construct an optimal stochastic decision rule and show that, by allowing for randomization, it makes fewer errors than a deterministic decision rule. Furthermore, the stochastic decision rule has a similar structural form to that of the deterministic decision rule.