This paper invokes complexity considerations to justify Markov behavior in a non-stationary bargaining model of Che and Sakovics (2004) in which the surplus depends on the players' relationship-specific investments. Using the notion of state complexity and the machine game analysis developed by Lee and Sabourian (2007), it is shown that if the players have lexicographic complexity-averse preferences then every Nash equilibrium of the game must be Markov.