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. Players agree to provide the first favor in a partnership only if they otherwise face the risk of eventual isolation. In equilibrium, players essential for realizing every maximum matching can avoid this risk and enjoy higher payoffsthaninessentialplayers.Althoughthesearchforpartnersisdecentralizedandreflects local partnership opportunities, the strength of essential players drives efficient partnership formation in every network. Equilibrium behavior is determined by the classification of nodes in the Gallai-Edmonds decomposition of the underlying network.
Bhaskar Dutta,
