Mistake, Manipulation and Margin Guarantees in Online Strategic Classification

Binary classification is a well-known problem in supervised learning, with applications in numerous important domains such as marketing, finance, natural language processing and medicine. The traditional binary classification problem aims to learn a decision rule that maps feature vectors to binary labels 1, with the aim of predicting a true underlying label for a feature vector. For example, features may correspond to identifying information of customers of a bank who apply for a loan, and in this context the label may indicate whether the bank will approve or deny the loan. The true underlying label, whether the bank should approve or deny given all future outcomes, is unknown at the time of the loan application, which necessitates the need to use a classification rule. Like the example above, binary classification is now regularly applied to various applications involving human agents. Customers obviously prefer that their loan application be approved rather than denied, and in many other applications there may similarly be one label that is preferred by agents over the other. One can imagine that in practice this leads to strategic behavior of agents, where feature vectors are manipulated in order to achieve the desired label prediction. Of course, there is often also a cost associated with manipulation, so agents may manipulate only if the payoff for achieving the desirable label is worth the cost.