We study two person infinitely repeated games in which players seek to minimize the complexity of their strategies. Players' preferences are assumed to depend both on repeated game payoffs and the complexity of the strategies they use. The model considered is that of Rubinstein (1986). Players simultaneously choose finite automata (Moore-machines) to implement their strategies. The complexity of a strategy is measured by the number of states in the automaton used to play the strategy. We analyze Nash equilibrium in the "machine game." Strong necessary conditions on the structure of equilibrium machine pairs are derived, under general assumptions about how players trade off repeated game payoffs against implementation costs. These structural results in turn place significant restrictions on equilibrium payoffs. We provide a complete characterization for symmetric 2 x 2 stage games, when repeated game payoffs are evaluated according to the limit of means, and complexity costs enter preferences lexicographically. We find that all Nash equilibrium payoffs must lie on one of the two "diagonals" of the payoff matrix, and show that "main" diagonal payoffs are always attained. Taken together our results suggest that the introduction of implementation costs results in a striking discontinuity in the Nash equilibrium set in terms of strategies, plays, and payoffs.