Regression Equilibrium
  Prediction is a well-studied machine learning task, and prediction algorithms
are core ingredients in online products and services. Despite their centrality
in the competition between online companies who offer prediction-based
products, the \textit{strategic} use of prediction algorithms remains
unexplored. The goal of this paper is to examine strategic use of prediction
algorithms. We introduce a novel game-theoretic setting that is based on the
PAC learning framework, where each player (aka a prediction algorithm aimed at
competition) seeks to maximize the sum of points for which it produces an
accurate prediction and the others do not. We show that algorithms aiming at
generalization may wittingly mispredict some points to perform better than
others on expectation. We analyze the empirical game, i.e., the game induced on
a given sample, prove that it always possesses a pure Nash equilibrium, and
show that every better-response learning process converges. Moreover, our
learning-theoretic analysis suggests that players can, with high probability,
learn an approximate pure Nash equilibrium for the whole population using a
small number of samples.
