Local matching dynamics in social networks

We study stable marriage and roommates problems under locality constraints. Each player is a vertex in a social network and strives to be matched to other players. The value of a match is specified by an edge weight. Players explore possible matches only based on their current neighborhood. We study convergence of natural better-response dynamics that converge to locally stable matchings – matchings that allow no incentive to deviate with respect to their imposed information structure in the social network. If we have global information and control to steer the convergence process, then quick convergence is possible and for every starting state we can construct in polynomial time a sequence of polynomially many better-response moves to a locally stable matching. In contrast, for a large class of oblivious dynamics including random and concurrent better-response the convergence time turns out to be exponential. In such distributed settings, a small amount of random memory can ensure polynomial convergence time, even for many-to-many matchings and more general notions of neighborhood. Here the type of memory is crucial as for several variants of cache memory we provide exponential lower bounds on convergence times.