We analyze the formation of partnerships in social networks. Players need favors at random times and ask their neighbors in the network to form exclusive long-term partnerships that guarantee reciprocal favor exchange. Refusing to provide a favor results in the automatic removal of the underlying link. When favors are costly, players agree to provide the first favor in a partnership only if they otherwise face the risk of eventual solitude. In equilibrium, the players essential for realizing every maximum matching can avoid this risk and enjoy higher payoffs than inessential players. Although the search for partners is decentralized and reflects local incentives, the strength of essential players drives efficient partnership formation in every network. When favors are costless, players enter partnerships at any opportunity and every maximal matching can emerge in equilibrium. In this case, efficiency is limited to special linking patterns: complete and complete bipartite networks, locally balanced bipartite networks with positive surplus, and factor-critical networks.