안정적인 무작위 선택을 위한 매끄러운 부분 복권 (Smooth Partial Lotteries)

과학적 연구 자금 지원부터 입학 및 채용에 이르기까지, 경쟁적인 선택 프로세스는 후보자들에게 점수를 부여하기 위해 평가를 사용하며, 최종적으로 해당 점수를 바탕으로 후보자의 일부를 선택합니다. 최근 많은 조직이 평가 점수에 따라 선택을 무작위화하는 부분 복권 (Partial Lotteries) 방식을 채택해 왔습니다. 그러나 기존의 복권 설계는 본질적으로 불안정합니다. 단 한 명의 후보자의 점수가 미세하게 변하더라도 그들의 선택 확률에 큰 변화를 일으킬 수 있기 때문입니다. 이러한 불안정성은 결정 경계 (Decision Boundary) 근처에서 미세한 점수 차이의 영향을 줄인다는 복권의 핵심 목표를 저해합니다. 본 논문에서는 매끄러움 (Smoothness)을 부분 복권의 설계 원칙으로 제안하며, 이를 후보자에 대한 리뷰 점수에서 선택 확률로의 매핑에 대한 Lipschitz 조건으로 공식화합니다. 우리는 상한 임계값(이 위로는 항상 수락)과 하한 임계값(이 아래로는 항상 거절) 사이에서 선택 확률이 추정된 품질에 따라 선형적으로 비례하는 단순한 메커니즘인 Clipped Linear Lottery를 소개합니다. 우리는 Clipped Linear Lottery의 최악의 후회 (Worst-case Regret)가 수락률인 $k/n$에 대해 $(1 - k/n)$ 배수까지 모든 매끄러운 선택 규칙의 하한선과 일치함을 증명합니다. 우리는 매끄러운 선택을 개인적 공정성 (Individual Fairness) 및 차분 프라이버시 (Differential Privacy)와 같은 다른 안정성 개념과 비교하여, Clipped Linear Lottery가 대안들보다 더 나은 매끄러움-후회 (Smoothness-Regret) 트레이드오프를 달성함을 보여줍니다. ICLR 2025, NeurIPS 2024, 그리고 스위스 국립 과학 재단 (Swiss National Science Foundation)의 실제 동료 검토 (Peer Review) 데이터를 활용한 실험을 통해, 기존의 복권 설계가 단 하나의 점수에 대한 섭동 (Perturbation) 하에서도 실제로는 매우 불안정하다는 것을 입증합니다. 또한 우리의 실험은 이론적 분석의 엄밀함을 확인시켜 주며, 제안된 Clipped Linear Lottery가 실제 환경에서 대안들보다 더 나은 매끄러움-효용 (Smoothness-Utility) 트레이드오프를 달성함을 보여줍니다.