Nash Equilibria of Static Prediction Games

Michael Brückner, Tobias SchefferNeurIPS 2009 · OpenReview

The Flaw in the i.i.d. Assumption

Most machine learning models rely on a fundamental assumption: the data you train on comes from the same distribution as the data you will see in the real world (the i.i.d. assumption). However, in fields like spam filtering, fraud detection, or cybersecurity, this assumption is systematically violated. An adversary—such as a spammer—actively changes their behavior to bypass the learner's model.

Traditionally, researchers have used a minimax strategy to handle this. Minimax is essentially "playing against the world's most malicious opponent"—it minimizes the maximum possible loss. While robust, this approach is often overly pessimistic. In reality, an adversary isn't always trying to maximize your pain; they are trying to minimize their own costs. For example, a spammer wants to maximize revenue, not just break your filter. This paper addresses the challenge of finding a Nash Equilibrium: a stable point where neither the learner nor the adversary can improve their situation by changing their strategy alone.

Rationality vs. Malice: The Game Theory Approach

The authors model the interaction as a static infinite game. "Static" means both players move simultaneously without knowing the other's choice, and "infinite" refers to the continuous nature of the strategy spaces (like choosing weights for a model).

The core insight is that assuming an adversary is "rational" (minimizing their own costs) leads to better models than assuming they are purely "malicious." The adversary’s "regularizer" is interpreted as the cost of changing data. For a spammer, changing a message too much might make the "payload" unreadable, providing a natural limit to how much they can distort the data.

AUC performance of Nash vs. baselines under varying amounts of transformation.

The paper introduces two primary algorithmic approaches:

  1. For Non-Antagonistic Loss Functions: This applies when the learner and adversary have different goals. The authors prove that if the loss functions are convex, twice differentiable, and have "distinct monotonicity," a unique Nash equilibrium exists. They use the weighted Nikaido-Isoda function to transform the game into an optimization problem solvable via gradient descent.
  2. For Antagonistic Loss Functions: This covers the "zero-sum" scenario where one player's gain is exactly the other's loss. If a unique Nash equilibrium exists here, it can be found by solving a minimax problem on a specifically derived joint cost function.

Evaluating the Arms Race

The authors evaluated their models on two large-scale email datasets to simulate real-world spam filtering:

  • Public Email Corpus: 65,000 emails combined from the Enron corpus, SpamAssassin, and Bruce Guenter’s spam trap.
  • Private Email Corpus: 40,000 private emails.

Crucially, unlike standard benchmarks, these were processed chronologically. This simulates the real-world "arms race" over time, where the model is trained on the past and tested on the future.

Key Results

  • Better Performance Over Time: In chronological testing, the Nash-based models and minimax baselines significantly outperformed standard SVMs and Logistic Regression, which degraded quickly as the adversary adapted.
  • Cost-Aware Filtering: The Nash model excelled in scenarios with complex costs, outperforming all reference methods by several standard errors when factoring in real-world trade-offs.
  • Efficiency: Despite the complexity of game theory, the proposed algorithms showed execution times comparable to standard game-theoretic baselines, making them practical for real-world applications.
Accuracy over time and execution time for various models.

Limitations and Future Directions

While promising, the paper focuses on "static" (one-shot) games. In reality, adversarial settings are often "repeated games" where players learn from each other's past moves over many rounds. Furthermore, the Nash equilibrium assumes the adversary is a rational actor. If the adversary behaves irrationally or has a different cost structure than modeled, the Nash strategy might underperform compared to a paranoid minimax strategy. Future work could explore more complex transformations, such as structural changes to data or non-linear models.

Summary updated

Abstract

The standard assumption of identically distributed training and test data can be violated when an adversary can exercise some control over the generation of the test data. In a prediction game, a learner produces a predictive model while an adversary may alter the distribution of input data. We study single-shot prediction games in which the cost functions of learner and adversary are not necessarily antagonistic. We identify conditions under which the prediction game has a unique Nash equilibrium, and derive algorithms that will find the equilibrial prediction models. In a case study, we explore properties of Nash-equilibrial prediction models for email spam filtering empirically.
BibTeX
@inproceedings{bruckner2009nash,
  author = {Michael Brückner and Tobias Scheffer},
  title = {{Nash Equilibria of Static Prediction Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=H1ZpC_-_ZS},
}
Figure