ㅋ

안정적인 결혼 문제(Stable Marriage Problem)

세상 일이라는 것은 수많은 변수가 숨어 있는 복잡다단한 것이지만, 여기서는 상황을 조금 단순하게 만들어 보자. 우선, 남성 n 명과 여성 n 명이 서로의 파트너를 정하려는 상황이라고 생각하자. 그리고 각각의 남성은 선호도에 따라 n 명의 여성에 대해 순위를 매긴 목록을 가지고 있고, 각각의 여성은 선호도에 따라 n 명의 남성에 대해 순위를 매긴 목록을 가지고 있으며, 이 순위에 동률은 없다고 하자. 이런 상황에서 남녀가 커플이 되는 경우를 생각해 보자. 아무렇게나 짝을 지어서 남A-여A, 남B-여B 커플이 만들어지고 보니, 사실은 남A가 자기 파트너인 여A보다 여B를 더 좋아하고, 여B 역시 자기 파트너인 남B보다 남A를 더 좋아하는 상황이 벌어질 수 있다. 이러면 바로 두 남녀가 바람이 나서 두 커플이 다 깨져 버리는 불상사가 생긴다.

서로 바람이 나지 않게 커플을 맺어주는 것이 “안정적인 결혼 문제”의 목적이다. <출처: NGD>

따라서 커플을 맺어주려면 적어도 이런 일로 커플이 깨지는 일은 생기지 않아야 할 것이다. 즉, 남A가 여B를 더 좋아하더라도 여B가 자기 파트너인 남B를 더 좋아해서 남A의 구애를 거절할 수 있어야 한다. 이런 조건 아래 남녀 각각 n 명의 짝을 맺어주는 문제를 '안정적인 결혼 문제(Stable Marriage Problem)'라 부른다. 모든 커플의 안정적인 해피엔딩이 목표인 것이다.