Ordinary repeated games do not apply to real societies where one can cheat and escape from partners. We formulate a model of endogenous relationships that a player 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 generates a significantly different evolutionary stability structure from ordinary random matching games. Monomorphic equilibria require initial trust building, while a polymorphic equilibrium includes earlier cooperators than any strategy in monomorphic equilibria and is thus more efficient. This is due to the non-linearity of average payoffs.