  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 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 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 miss-predict 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.
