上海科技大学知识管理系统

We consider a stable marriage problem on a network, where two groups of agents (men and women) form a network and each only knows their neighbors. Our objective is to design a novel mechanism that motivates agents to invite their neighbors to participate in the matching game if they are not already in it and they can match with strangers via social relationship. The difficulty is that invitees may hurt the inviters, which occurs if we apply the standard Deferred Acceptance (DA) mechanism. To induce mutual invitations, one idea is to add restrictions on DA and let each agent only propose to their neighbors, which ensures everyone is eager to invite all their neighbors. The drawback is that agents can never match with non-neighbors. Thus, we propose the first mechanism that enables matching with non-neighbors by giving the opportunity to unfamiliar agents, named  Dynamic Deferred Acceptance (DDA). We also demonstrate some impossibility results between stability and other desirable properties, and our mechanism achieves the strongest stability in the networks.