Distributed stable matching with similar preference lists

Abstract

Consider a complete bipartite graph of 2n nodes with n nodes on each side. In a round, each node can either send at most one message to a neighbor or receive at most one message from a neighbor. Each node has a preference list that ranks all its neighbors in a strict order from 1 to n. We introduce a non-negative similarity parameter D < n for the preference lists of nodes on one side only. For D = 0, these preference lists are same and for D = n-1, they can be completely arbitrary. There is no restriction on the preference lists of the other side. We show that each node can compute its partner in a stable matching by receiving O(n(D + 1)) messages of size O(log n) each. We also show that this is optimal (up to a logarithmic factor) if D is constant.