싱가포르 정부가 내놓은 소개팅 앱 '퍼스트데이트(FirstDate)'가 화제가 된 것은 세련된 인터페이스나 공격적인 마케팅 때문이 아니라, 그 뒤에 깔린 수학 때문이다. 이 앱은 1962년 데이비드 게일과 로이드 섀플리가 발표한 '안정 결혼(stable marriage)' 알고리즘, 흔히 게일-섀플리 알고리즘이라 불리는 매칭 이론을 짝짓기 엔진으로 쓴다. 섀플리는 이 공로로 앨빈 로스와 함께 2012년 노벨 경제학상을 받았고, 같은 알고리즘은 지금도 미국의 전공의 배정과 신장 교환 이식 네트워크 같은 생사가 걸린 현장에서 돌아가고 있다. 연애 앱이 수십 년 묵은 조합론을 꺼내 든 셈인데, 그 선택에는 나름의 공학적 논리가 있다.
안정 매칭이란 무엇인가
게일-섀플리 알고리즘이 보장하는 것은 '최적의 짝'이 아니라 '안정적인 짝'이다. 두 집단이 서로에 대한 선호 순위를 갖고 있을 때, 알고리즘은 '현재 맺어진 상대보다 서로를 더 원하는 두 사람'이 존재하지 않는 매칭을 만들어낸다. 이렇게 깨질 유인이 없는 상태를 안정 매칭이라 부른다. 작동 방식은 직관적이다. 한쪽이 가장 선호하는 상대에게 차례로 신청하고, 받는 쪽은 들어온 신청 중 가장 나은 하나를 임시로 붙잡아 두되 더 나은 신청이 오면 갈아탄다. 거절당한 쪽은 다음 순위로 내려가며 이 과정을 반복하고, 더 이상 신청이 오가지 않으면 매칭이 확정된다. 핵심은 이 절차가 반드시 종료되며, 항상 안정 매칭을 하나 이상 만들어낸다는 수학적 증명이 존재한다는 점이다.
이 성질이 왜 중요한지는 전공의 배정 사례가 잘 보여준다. 병원과 지원자가 제각기 유리한 쪽으로 빠져나가려 하면 시장 전체가 무너지는데, 안정 매칭은 '뒷거래로 더 나은 짝을 찾을 수 있는' 쌍을 애초에 남기지 않기 때문에 참가자들이 결과에 승복하게 만든다. 신장 교환처럼 참가자의 이해가 첨예하게 엇갈리는 영역에서도 같은 이유로 채택됐다.
연애에 적용했을 때의 함의
소개팅 앱 입장에서 안정성은 매력적인 속성이다. 사용자가 선호와 '절대 안 되는 조건(dealbreaker)'을 입력하면, 시스템은 모두가 어느 정도 납득할 수 있는 매칭을 전역적으로 계산해 제시한다. 선착순이나 단순 유사도 점수로 짝을 붙이는 방식과 달리, 전체 사용자 풀을 하나의 시장으로 보고 최적화한다는 발상이다. 끝없이 스와이프하며 상대를 소비하게 만드는 상업 앱들과 달리, 정부가 운영 주체라는 점도 이 설계와 맞물린다. 체류 시간을 늘려 광고를 파는 것이 목적이 아니라 '실제로 성사되는 짝'을 늘리는 것이 목표라면, 안정 매칭은 합리적인 선택지다. 다만 공개된 설명은 선호와 데일브레이커를 입력받는 단계까지만 드러나 있어, 실제 구현의 세부 — 선호를 어떻게 수집하고 가중치를 어떻게 매기는지 — 는 아직 확인되지 않았다.
알고리즘이 풀어주지 않는 것
화려한 수식 뒤에 가려지기 쉬운 한계도 분명하다. 첫째, 게일-섀플리는 안정 매칭이 여러 개 존재할 때 '먼저 신청하는 쪽'에게 체계적으로 유리한 결과를 낸다. 전통적 서술에서 남성이 청혼하는 쪽이면 남성에게 최적, 여성에게 최악의 안정 매칭이 나온다는 비대칭성이 있다. 어느 집단을 제안자로 두느냐가 곧 설계 편향이 되는 셈이라, 양방향 선호가 중요한 연애 맥락에서는 이 비대칭을 어떻게 처리하느냐가 공정성의 관건이 된다.
둘째, 알고리즘은 입력된 선호가 정직하고 완결적이라는 전제 위에서만 아름답게 작동한다. 사람의 호감은 몇 개의 체크박스로 환원되지 않고, 만나기 전에는 자신의 선호조차 제대로 모르는 경우가 많다. 수학은 주어진 순위표를 완벽하게 처리하지만, 그 순위표가 현실의 끌림을 얼마나 반영하는지는 전혀 보장하지 못한다. 결국 안정성은 '아무도 더 나은 짝으로 몰래 갈아탈 유인이 없다'는 이론적 평형일 뿐, 두 사람이 실제로 행복할 것이라는 약속은 아니다.
실무자 관점에서 퍼스트데이트가 흥미로운 지점은 연애 성사율보다 설계 철학에 있다. 추천 시스템을 만드는 많은 팀이 개별 사용자의 클릭을 극대화하는 지역 최적화에 매달리는 동안, 이 앱은 시장 전체의 안정성이라는 전역 목표를 내걸고 검증된 매칭 이론을 꺼내 들었다. 반세기 전의 조합론이 추천·배정·자원 할당 문제에 여전히 쓸모 있다는 사실, 그리고 그 수학적 우아함조차 사람의 모호한 선호 앞에서는 겸손해질 수밖에 없다는 사실을 동시에 보여주는 사례다.