Ordinary repeated games do not apply to real societies where one can cheat and run away from partners. We formulate a model of endogenous relationships which one can unilaterally end and start with a randomly-assigned new partner with no information flow. Focusing on two-person, two-action Prisoner's Dilemma, we show that the endogenous duration of partnerships gives rise to a significantly different evolutionary stability structure from ordinary random matching games. Monomorphic equilibria require initial trust-building, while a polymorphic equilibrium includes early cooperators than any strategy in monomorphic equilibria and is thus more efficient. This is due to nonlinearity of average payoffs.