게일-섀플리 알고리즘

게일-섀플리 알고리즘(Gale–Shapley algorithm)은 수학, 경제학 및 컴퓨터 과학에서 데이비드 게일과 로이드 섀플리의 이름을 딴 안정적인 매칭 문제에 대한 솔루션을 찾기 위한 알고리즘이다. 다항식 시간이 걸리며 시간은 알고리즘에 대한 입력 크기에서 선형이다. 솔루션이 항상 최적인 제안 참가자의 관점에서 볼 때 이것은 신뢰할 만한 메커니즘이다.

배경

가장 기본적인 형태의 안정적인 매칭 문제는 두 가지 유형의 참여자(예: n명의 의대생과 n명의 인턴십)의 동일한 수를 입력으로 사용하고 각 참가자가 선호하는 매칭 대상을 지정하는 순서를 지정한다. 안정적인 매칭은 항상 존재하며 게일-섀플리 알고리즘으로 해결되는 알고리즘 문제는 이를 찾는 것이다. 다음과 같은 경우 매칭이 안정적이지 않다.

1. A가 이미 일치된 요소보다 두 번째 일치된 집합의 일부 주어진 요소 B를 선호하는 첫 번째 일치된 집합의 요소 A가 있고,
2. B는 또한 B가 이미 일치된 요소보다 A를 선호한다.

즉, 쌍(A, B)이 짝이 없는 상대보다 서로를 선호하는 쌍(A, B)이 없을 때 매칭이 안정적이다. 그러한 쌍이 존재하는 경우, 이 쌍의 구성원이 시스템을 떠나 서로 일치되는 것을 선호하여 다른 참가자가 일치하지 않는 상태로 남을 수 있다는 점에서 일치가 안정적이지 않다.

알고리즘

algorithm stable_matching is
    Initialize m ∈ M and w ∈ W to free
    while ∃ free man m who has a woman w to propose to do
        w := first woman on m's list to whom m has not yet proposed
        if ∃ some pair (m', w) then
            if w prefers m to m' then
                m' becomes free
                (m, w) become engaged
            end if
        else
            (m, w) become engaged
        end if
    repeat

외부 링크

• Gale–Shapley JavaScript Demonstration