Strategic Classification: A Game-Theoretic Approach

Entities of physical presence have always been susceptible to attacks. Entities of online presence are more prone to cyberattacks, as the lack of local boundaries permits anyone from anywhere in the world to launch a potentially successful attack. People aim to protect their physical and virtual assets daily: Locking doors and cars, setting up alarms and protecting passwords and credit card numbers are just a few examples. History has proven, though, that any defense system can be compromised. Defenders and attackers have delved into continuous action and counteraction: The more intelligent the defense strategy gets, the more sophisticated the attacker becomes, and the defense needs to adapt again. Game Theory provides us with the mathematical tools and concepts to capture these strategic interactions between players and their different and often antagonistic interests. Such a concept is a Nash equilibrium: a set of strategies that dictates what the players should do, such that the players have no incentive to deviate. We model the strategic interactions between a strategic adversary and a classifier using Game Theory. Our analysis leads to Nash equilibria in randomized strategies, increasing the difficulty for the attacker to reconstruct the classification rule. We give a polynomial time algorithm to compute the Nash equilibrium strategies of the players. Our setting, albeit simple, gives interesting insights that could be beneficial in practical settings: We quantify the impact of the various parameters like cost from detection, false alarms and statistics about the normal traffic on the equilibrium strategies and payoffs. We show that if the classification is based on several features, the defender should apply a threshold on the attacker's reward. This is in contrast with known algorithms such as logistic regression which have a predefined shape of the boundary independently of the attacker's goal. In view of the recent security breaches, like Anthem, Target and Home Depot, we are motivated to study a class of games in which there are multiple defenders (companies) that compete to acquire legitimate users in the presence of malicious traffic. To this purpose we analyze the economic incentives for ad networks to fight click fraud in advertising markets. By click fraud, we define the act of clicking an ad without an interest to see the ad or buy the advertised product. When such clicks are counted as "valid" by the ad network, the advertiser pays for a useless click, and the publisher (webpage at which the ad was displayed) is rewarded for generating it. Thus there is an incentive for fraudulent publishers to inflate click numbers. Ad networks have an incentive to classify fraudulent clicksin order to deliver a more valuable service to advertisers. On the other hand, ad networks do receive revenue for fraudulent clicks, which creates an incentive in the opposite direction to fight fraud less.We develop a model to capture the incentives of two competing ad networks to fight click fraud, under different assumptions about the bidding process of advertisers. Our equilibrium results show that ad networks are highly incentivized in combating click fraud. We explore the investment strategies of ad networks to improve their classification algorithms and investigate when ad networks over or under invest compared to social optimum