The creation of mathematical, as well as qualitative (or rule-based), models is difficult, time-consuming, and expensive. Recent developments in evolutionary computation hold out the prospect that, for many problems of practical import, machine learning techniques can be used to discover useful models automatically. These prospects are particularly bright, we believe, for such automated discoveries in the context of game theory. This paper reports on a series of successful experiments in which we used a genetic programming regime to discover high-quality negotiation policies. The game-theoretic context in which we conducted these experiments-a three-player coalitions game with sidepayments-is considerably more complex and subtle than any reported in the literature on machine learning applied to game theory.