Bayesian Strategic Classification
Lee Cohen Saeed Sharifi-Malvajerdi Kevin Stangl Ali Vakilian Juba Ziani
In strategic classification, agents modify their features, at a cost, to
ideally obtain a positive classification from the learner's classifier. The
typical response of the learner is to carefully modify their classifier to be
robust to such strategic behavior. When reasoning about agent manipulations,
most papers that study strategic classification rely on the following strong
assumption: agents fully know the exact parameters of the deployed classifier
by the learner. This often is an unrealistic assumption when using complex or
proprietary machine learning techniques in real-world prediction tasks.
  We initiate the study of partial information release by the learner in
strategic classification. We move away from the traditional assumption that
agents have full knowledge of the classifier. Instead, we consider agents that
have a common distributional prior on which classifier the learner is using.
The learner in our model can reveal truthful, yet not necessarily complete,
information about the deployed classifier to the agents. The learner's goal is
to release just enough information about the classifier to maximize accuracy.
We show how such partial information release can, counter-intuitively, benefit
the learner's accuracy, despite increasing agents' abilities to manipulate.
  We show that while it is intractable to compute the best response of an agent
in the general case, there exist oracle-efficient algorithms that can solve the
best response of the agents when the learner's hypothesis class is the class of
linear classifiers, or when the agents' cost function satisfies a natural
notion of submodularity as we define. We then turn our attention to the
learner's optimization problem and provide both positive and negative results
on the algorithmic problem of how much information the learner should release
about the classifier to maximize their expected accuracy.