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’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.
MMC는 둘로 나뉜 구성원들이 다수의 반대편 구성원과 맺어질 수 있는 매칭 문제이다. 어떤 이분그래프 G = (A $ \cup$ P, E) 가 주어질 때 A 와 P 의 각 노드는 반대편에 대한 엄격한 선호도 리스트와 자기자신의 용량을 갖는다. 각 지원자 A 는 자신의 용량 이하 다수의 부서 P 와, 각 부서 P 는 자신의 용량 이하 다수 지원자 A 와 매칭될 수 있다. 이러한 매칭 문제에서 우리는 어떤 멤버의 매칭에 대한 선호도를 사전편찬식 순서로 새롭게 정의한다. 이 정의를 이용하여 우리는 다수 대 다수 수용 매칭에서의 사전편찬식 안정성을 정의한다. 제안하는 알고리즘과 함께, 우리는 이 알고리즘의 결과가 사전편찬식으로 안정적이라는 것을 증명할 것이다. 또한, 주어진 상황에서 안정적인 매칭이 유일할 조건을 보일것이다.