게일-섀플리 알고리즘

• 각 라운드에서, 빈 일자리가 있는 고용주는 아직 제안하지 않은 지원자 중 가장 선호하는 지원자에게 일자리를 제안한다.
• 제안을 받은 지원자는 현재 일자리(있는 경우)와 새 제안을 비교한다. 아직 고용되지 않았거나, 더 좋은 제안을 받으면 새 제안을 수락하고 새 고용주와 매칭된다(이전 고용주는 빈 일자리가 생길 수 있음). 그렇지 않으면 새 제안을 거부한다.
• 모든 고용주가 일자리를 채우거나 지원자 목록을 모두 확인할 때까지 이 과정을 반복한다.

3. 2. 알고리즘 구현 및 시간 복잡도

이러한 자료 구조를 설정하는 데는 $O(n^2)$ 시간이 걸린다. 이러한 구조를 사용하면 미충원된 직책이 있는 고용주를 찾고, 해당 고용주가 다음 지원자에게 제안을 하고, 제안이 수락되었는지 확인하고, 이러한 단계의 결과를 반영하도록 모든 자료 구조를 업데이트하는 데 제안당 상수 시간이 걸린다. 알고리즘이 종료되면 결과 매칭은 각 지원자에 대한 고용주 배열에서 읽을 수 있다. 각 고용주가 제안을 모두 소진하기 전에 $O(n^2)$개의 제안이 있을 수 있으므로 총 시간은 $O(n^2)$이다.

이 시간 경계는 참가자 수에 대해 2차이지만, 크기가 $O(n^2)$인 두 개의 선호도 행렬인 입력의 크기를 기준으로 측정하면 선형 시간으로 간주될 수 있다.^[1]

3. 3. 알고리즘의 보장

• '''모든 사람이 짝을 이룹니다.''' 알고리즘 종료 시점에 지원자와 고용주 모두 짝이 없는 경우는 발생할 수 없다. 짝이 없는 고용주는 모든 지원자에게 제안을 했을 것이다. 제안을 받은 지원자는 알고리즘이 진행되는 동안 계속 고용된 상태로 유지되므로, 실업 상태인 지원자는 있을 수 없다. 지원자와 일자리 수가 같으므로, 남은 빈 일자리도 없을 것이다.

• '''매칭은 안정적입니다.''' 지원자 ''X''와 고용주 ''Y''는 서로의 최종 짝보다 서로를 더 선호할 수 없다. ''Y''가 ''X''에게 제안했다면, ''X''는 더 좋은 제안을 받은 후에만 ''Y''를 거절했을 것이므로, ''X''는 자신의 최종 짝보다 ''Y''를 더 선호할 수 없다. ''Y''가 선호 목록에서 ''X''에게 도달하기 전에 제안을 중단했다면, ''Y''는 자신의 최종 짝보다 ''X''를 더 선호할 수 없다. 어느 경우든 ''X''와 ''Y''는 불안정한 짝을 이루지 않는다.

6. 2. 프랑스의 파쿠르수프 시스템