Many-to-Many matching with capacity using lexicographic preference

Abstract

Many-to-many matching with capacity(MMC) is a matching problem of two sides of members can be matched to multiple members of opposite side. Given a bipartite graph G = (A $\cup$ P, E), each node in A, P has strict preference list of opposite side and its own capacity. Each applicant A can be matched to multiple posts in P within its capacity, and each post P can be matched to multiple applicants in A within its capacity. In this instance of matching problem, we define each member&amp

amp

rsquo

s preference to a matching with lexicographical order. With this definition, we define lexicographic stability in this many-to-many matching with capacity instance. We give an algorithm and prove this algorithm is stable. We also show the condition whether unique stable matching exists given such instance using side optimality.