The Strategic Perceptron
  The classical Perceptron algorithm provides a simple and elegant procedure
for learning a linear classifier. In each step, the algorithm observes the
sample's position and label and updates the current predictor accordingly if it
makes a mistake. However, in presence of strategic agents that desire to be
classified as positive and that are able to modify their position by a limited
amount, the classifier may not be able to observe the true position of agents
but rather a position where the agent pretends to be. Unlike the original
setting with perfect knowledge of positions, in this situation the Perceptron
algorithm fails to achieve its guarantees, and we illustrate examples with the
predictor oscillating between two solutions forever, making an unbounded number
of mistakes even though a perfect large-margin linear classifier exists. Our
main contribution is providing a modified Perceptron-style algorithm which
makes a bounded number of mistakes in presence of strategic agents with both
$\ell_2$ and weighted $\ell_1$ manipulation costs. In our baseline model,
knowledge of the manipulation costs (i.e., the extent to which an agent may
manipulate) is assumed. In our most general model, we relax this assumption and
provide an algorithm which learns and refines both the classifier and its cost
estimates to achieve good mistake bounds even when manipulation costs are
unknown.
