We design a laboratory experiment to investigate matching in a decentralized market of deferred acceptance. Agents are undifferentiated and may have multiple partners; their payoff depends on who they match with. The experiment is designed in such a way that a stable configuration exists, but cannot be eyeballed by the participants due to the computational complexity of the game. In spite of this, subjects are remarkably good at reaching a stable match, even when the payoffs of others are not publicly observed. More information does, however, speed up convergence thanks to self-censoring. We trace irrational matching choices mostly to two sources: the tendency of over-think in a setting where strategic thinking is not necessary, and the reluctance to accept matching offers from those who have been disloyal in the past.