2025/02/09 by Andrei Constantinescu, Marc Dufay, Constantinescu, Andrei +5
Economics, Econometrics and Finance · #Distributed #FOS: Computer and information sciences #Game Theory and Voting Systems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2502.05889
openalex publication_date 2025/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In stable matching, one must find a matching between two sets of agents, commonly men and women, or job applicants and job positions. Each agent has a preference ordering over who they want to be matched with. Moreover a matching is said to be stable if no pair of agents prefer each other over their current matching. We consider solving stable matching in a distributed synchronous setting, where each agent is its own process. Moreover, we assume up to tL agents on one side and tR on the other side can be byzantine. After properly defining the stable matching problem in this setting, we study its solvability. When there are as many agents on each side with fully-ordered preference lists, we give necessary and sufficient conditions for stable matching to be solvable in the synchronous setting. These conditions depend on the communication model used, i.e., if parties on the same side are allowed to communicate directly, and on the presence of a cryptographic setup, i.e., digital signatures.