Transformation of Many-to-One to One-to-One Matching Problems Through Replication
摘要
Increasingly more issues in production and service operation concern matching situations where stakeholders, physical systems, and social institutions are paired with many others under decentralized preferences and capacity constraints. These problems are formulated by many-to-one and many-to-many matching models and solved by algorithms that derive stable and optimal solutions. However, computational challenges arise when a model encompasses a large number of agents with large capacities that bring about an exponential growth in the length of preference orders. Against this backdrop, this study proposes a variation of the deferred acceptance (DA) algorithm. The proposed method transforms many-to-one matching models into their one-to-one matching equivalents by introducing a “replication” technique of chooser agents and successively processes the fractions of the set of proposer agents, aiming at reducing computational complexity. We provide a mathematical proof that the equivalence relation between the stable solutions of a many-to-one matching and its corresponding one-to-one model is maintained in the proposed method under the assumption of responsive and max-min preferences. Furthermore, the replication method, combined with a tie-breaking approach, can successfully transform many-to-one matching problems with indifferent preferences.