Zettelkasten

즉시 매칭은 들어온 한 사람 기준으로, 모아서 매칭은 풀 전체 기준으로 짝을 정한다

·수정 1회

요약

  • 즉시 매칭은 한 사람이 들어오는 순간 기다리던 사람 중에서 상대를 정한다. 모아서 매칭은 몇 초 동안 들어온 사람을 모은 뒤, 쌍 가치 합이 최대가 되게 한꺼번에 짝짓는다. 모으는 시간만큼 대기가 늘어나는 대신, 먼저 온 사람이 가져갔을 상대를 다른 사람에게 돌려줄 수 있다.
  • 짝을 바꿔서 합이 오르는 경우는 셋이다. 필터 때문에 사람마다 받을 수 있는 상대가 다를 때, 그 쌍에만 있는 궁합이 있을 때, 결과가 두 사람 성향의 곱에 가까울 때다. 쌍 가치가 두 사람 개인 점수의 합이면 누구와 짝짓든 합이 같아서, 모아도 대기만 늘어난다.
  • 성사 여부(0/1)만 따지는 큰 시장에서는 즉시 매칭이 점근적으로 최적이라는 연구가 있다. 쌍 점수는 즉시 매칭의 정렬 기준으로도 쓸 수 있어서, 모아서 매칭만 주는 몫은 그 위에 더하는 재배분이다.

본문

두 방식이 정하는 단위

  • 둘 다 대기열은 있다. 차이는 짝지을 상대가 있을 때 바로 정하는지, 일부러 미뤘다가 여러 명을 한꺼번에 정하는지다.
  • 즉시: 여성이 들어오면 기다리던 남성 목록을 정렬하고 필터를 통과한 첫 사람과 연결한다. 한 번에 들어온 한 사람의 상대만 정한다.
  • 모아서: 3초 같은 시간 창 동안 양쪽을 모아 이분 그래프를 만든다. 쌍 가치를 엣지 가중치로 두고 최대 가중 매칭을 풀어 창 안 전체의 짝을 한 번에 정한다. 정확히 풀려면 헝가리안 알고리즘(개선판 O(n³))을 쓴다. 창 안 N명의 쌍 점수 N²개는 투 타워 모델이면 행렬곱 한 번으로 나온다(투 타워(two-tower) 모델은 양쪽을 따로 임베딩해 쌍 점수를 내적으로 계산한다).

예: 먼저 온 사람이 다른 사람에게 더 잘 맞는 상대를 가져간다

남성 X 남성 Y
여성 A 0.6 0.5
여성 B 0.9 0.1
  • 즉시: A가 먼저 와서 자기 1위인 X와 연결된다. B는 Y와 연결된다. 합 0.7.
  • 모아서: A–Y, B–X로 짝짓는다. 합 1.4.
  • A에게는 X가 Y보다 0.1 낫지만, B에게는 0.8 낫다. 즉시 매칭은 B가 곧 들어온다는 걸 모른 채 A의 상대를 정한다.

짝을 바꿔서 합이 오르는 경우

  • 쌍 가치가 a(여성) + b(남성)처럼 개인 점수의 합이면, 같은 사람들을 어떻게 짝지어도 합은 Σa + Σb로 같다. 이때 모아서 매칭은 대기만 늘린다.
  • 합이 달라지는 경우는 각각 이렇다.
    1. 필터로 받을 수 있는 상대가 사람마다 다를 때. A는 X·Y 둘 다 되고 B는 X만 되면, 즉시 매칭에서는 A가 X를 가져가 B가 빈손이 될 수 있다. 모아서 A–Y, B–X로 짝지으면 둘 다 성사된다. 가치가 0과 1뿐인 쌍 가치다. 다만 이 경우는 큰 시장에서 즉시 매칭이 점근적으로 최적이라는 연구가 있다(아래 Ashlagi 외).
    2. 그 쌍에만 있는 궁합이 있을 때. 위 예처럼 개인 점수의 합으로 표현되지 않는 값이다.
    3. 결과가 두 사람 성향의 곱에 가까울 때. 통화는 먼저 끊는 쪽에서 끝나므로, "N분 넘김" 확률은 두 사람의 오래 머무는 성향의 곱에 가깝다. 곱이면 성향이 높은 사람끼리, 낮은 사람끼리 붙여야 합이 커진다(재배열 부등식). 개인 점수만 있어도 짝짓기가 합을 바꾼다.

장단점

즉시 모아서
대기 늘어나지 않음 창 길이의 절반만큼 평균 대기가 늘고, 그사이 나가는 사람이 생김
짝 품질 들어온 순서가 결과를 정함 창 안 전체 기준 최적
인기 유저 배분 먼저, 자주 들어오는 사람이 가져감 한 사람당 상한 같은 조건을 최적화에 넣을 수 있음
구현 요청마다 정렬과 필터, 상태가 적음 창 경계 처리, 모으는 중 이탈, 창 단위 락, 풀 크기에 따른 계산량
실험 사용자 단위 A/B 가능 같은 풀을 공유해서 사용자 단위 A/B가 섞임. 시간 구간마다 정책을 바꾸는 스위치백을 씀

연구와 사례

  • 성사 여부(0/1)만 따지면 즉시 매칭이 낫다는 결과가 있다.
    • Ashlagi·Nikzad·Strack(ReStud 2023): 쉬운 유형과 어려운 유형 두 종류가 있고 어려운 쪽이 더 많은 불균형 시장을 다룬다. 시장이 커지는 극한에서 도착하자마자 짝짓는 greedy는 점근적으로 최적이고, 모아서 매칭은 최적이 아니다. 미국 신장 교환(NKR) 실데이터 1,364쌍 시뮬레이션에서 greedy는 월 1회 배치보다 이식이 1.8% 많고 대기가 16일 짧았다(arXiv판은 1.6%, 23일). 비교 대상이 몇 초 배치가 아니라 월 1회 배치다. 원문은 매칭 품질이 아니라 매칭 수만 본다고 밝히고, 쌍마다 가치가 다른 경우는 열린 문제로 남긴다.
    • Akbarpour·Li·Oveis Gharan(JPE 2020): 누가 곧 떠날지 알 수 있으면, 기다려서 시장을 두껍게 만드는 쪽이 못 짝지은 비율을 크게 줄인다. 모르면 greedy가 최적의 상수배 안에 든다.
  • 쌍마다 가치가 뚜렷한 곳에서는 몇 초씩 모은다.
    • Uber는 요청 뒤 몇 초 동안 근처 기사와 승객을 한 배치로 평가한다. 이유로 모두의 평균 대기를 줄이는 것과 "가장 가까운 기사가 늘 가장 빠르지는 않다"는 점을 든다. 정확한 초 수는 공개하지 않았다.
    • Lyft는 몇 초마다 이분 매칭 그래프를 만들어 푼다. 창을 길게 잡으면 대기가 줄고 차량 가동률이 오르지만, 배정이 늦어져 취소 위험이 생긴다고 쓴다.
    • 1:1 영상통화 서비스 아자르는 예상 대화 시간을 엣지 가중치로 두고 풀 전체 합을 최대화한다(아자르 CUPID는 예상 대화 시간을 엣지 가중치로 두고 매칭 풀 전체 합을 최대화한다). 보고된 평균 대화 시간 +6.8%는 세션 정보를 넣은 모델의 효과라, 모아서 매칭 자체의 효과로 읽으면 안 된다.
  • 시뮬레이션에서 이득이 작게 나온 사례도 있다. EOMM(Chen 외, WWW 2017)은 게임 대기 풀을 두 사람의 이탈 위험 합이 최소가 되게 짝지었다(실제 게임 데이터 기반 시뮬레이션, 이탈은 8시간 안에 다시 안 함). 실력 기반 매칭 대비 한 라운드 잔존이 평균 0.7% 늘었다(풀 200500명에서 0.31.1%). 100명 풀에서는 무작위 매칭과 유의한 차이가 없었고, 풀을 키워도 이득이 꾸준히 오르지 않았다(400명 1.1%, 500명 0.6%).

한 1:1 랜덤 통화 서비스에 대입해 본 값 (사내 데이터 관찰, 대기열·시뮬레이션은 2026-10-11~17)

  • 지금은 즉시 방식이다. 매칭 요청마다 대기 목록을 등급 순으로 정렬하고 필터를 통과한 첫 사람과 연결한다(코드 확인 2026-10-13). 통화의 85%는 여성이 나중에 들어와 기다리던 남성과 연결된 경우라, 실제로 상대를 정하는 건 대기 남성 정렬 순서다.
  • 모을 사람은 있다. 다른 여성과 같은 창에 들어온 여성 큐 진입 비율:
권역·시간대 3초 창 5초 창 10초 창
한국 21~01시 69% 86% 98%
한국 그 외 43% 58% 78%
일본 21~01시 36% 53% 78%
그 외 국가 21~01시 23% 35% 58%
  • 대기 비용: 창 길이의 절반만큼 여성 대기가 는다. 통화 1회 주기 약 343초(통화 331 + 대기 6.1 + 연결 5.6) 기준으로 3초 창은 여성 시간의 0.4%, 5초 창은 0.7%다.
  • 점수 없이 지금 정렬 순서 그대로 모으면 모든 여성에게 같은 순서라 결과가 거의 같다. 남는 여지는 여성마다 필터가 달라 생기는 1번 경우뿐이다(해석, 시뮬레이션으로 재지 않음).
  • 쌍 점수의 신호:
    • 대화 텍스트 임베딩으로 궁합을 맞히면, 같은 사람 안에서 상대만 바꿔 비교한 AUC가 0.52~0.54다(무작위 0.50).
    • 통화 기록으로 학습한 BPR은 같은 비교에서 0.715다. 라벨은 log 통화 시간에서 두 사람 각자의 평균을 뺀 잔차다. 쌍 신호는 대화 내용보다 행동 기록에 있다. 개인 성향이 완전히 빠졌는지는 확인하지 않았다.
  • 즉시 매칭에 쌍 점수만 넣은 시뮬레이션: 기존 정렬을 다 지키고 마지막 동점만 쌍 모델 점수로 깨면, 통화당 3분 도달이 같은 정렬에서 동점을 무작위로 깬 경우보다 +2.03.4%p 높다(기본 등급 남성과 연결된 여성 요청 84,680건, 통화의 57%). 대신 과거 3분 도달률 하위 20% 남성의 통화는 913% 준다.
  • 모아서 매칭이 이 위에 더하는 재배분 몫은 아직 재지 않았다. 순서를 정하면 쌍 점수를 즉시 매칭 정렬에 먼저 넣어 이득을 확인하고, 그다음 모으는 창을 시험한다(설계 의견).

관련 노트

참고