🤖 machine learning

SMaRT: Online Reusable Resource Assignment and an Application to Mediation in the Kenyan Judiciary

케냐 사법부의 사건에 조정인을 배정하는 과제에서 영감을 얻은 본 논문은, 용량 제약과 조정인 품질 학습 사이의 균형을 맞추면서 고차원 상태 공간 전반에 걸쳐 자원을 효율적으로 할당하기 위해 이차 계획법과 다중 에이전트 밴딧 학습을 결합한 온라인 알고리즘인 SMaRT를 소개한다.

원저자: Shafkat Farabi, Didac Marti Pinto, Wei Lu, Manuel Ramos-Maqueda, Sanmay Das, Antoine Deeb, Anja Sautmann

게시일 2026-06-30

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Shafkat Farabi, Didac Marti Pinto, Wei Lu, Manuel Ramos-Maqueda, Sanmay Das, Antoine Deeb, Anja Sautmann

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

케냐의 법원 시스템을 거대하고 북적이는 병원 응급실이라고 상상해 보십시오. 매일 수백 명의 새로운 환자(법적 사건)가 문을 통해 들어옵니다. 이들을 치료하기 위해 병원에는 전문가 팀(조정인)이 있습니다. 하지만 세 가지 큰 문제가 있습니다:

전문화: 모든 전문가가 모든 환자를 치료할 수 있는 것은 아닙니다. 어떤 이들은 "가족 문제"만 다루고, 어떤 이들은 "비즈니스 분쟁"만 다루며, 또 어떤 이들은 특정 도시에서만 일할 수 있습니다.
알려지지 않은 기술: 병원은 전문가가 환자들을 합의에 이르게 하는 데 얼마나 뛰어난지 항상 정확히 알 수는 없습니다. 어떤 이들은 협상의 마술사이지만, 어떤 이들은 어려움을 겪습니다. 또한 새로운 전문가들이 끊임없이 팀에 합류합니다.
"대기 금지" 규칙: 이 응급실에서는 환자에게 "전문가가 한가해질 때까지 내일 다시 오세요"라고 말할 수 없습니다. 환자는 즉시 전문가를 배정받아야 합니다.

이 문제를 해결하기 위해 이 논문은 SMaRT(Selecting Mediators that are Right for the Task, 과업에 적합한 조정인 선택)라는 새로운 "스마트 트리아지(중증도 분류) 시스템"을 소개합니다.

기존 방식: "라운드 로빈" 방식의 셔플

이전에는 인간 관리자들이 수동으로 환자와 전문가를 매칭하려 노력했습니다. 그것은 규칙이 계속 바뀌는 의자 뺏기 게임과 같았습니다.

그들은 종종 동일한 "스타" 전문가에게 너무 많은 환자를 배정하여 그들을 번아웃(과부하) 상태로 만들었습니다.
때로는 해당 전문가가 단순히 시간이 비어 있다는 이유만으로, 그들이 잘 다루지 못하는 어려운 사건을 맡기기도 했습니다.
그 결과, 많은 환자가 해결책을 찾지 못한 채 떠나야 했고, 결국 다시 본 법원으로 돌아가야 했습니다.

새로운 시스템: SMaRT

SMaRT는 더 똑똑하고 지치지 않는 배차원 역할을 하는 알고리즘입니다. 이 시스템은 더 나은 결정을 내리기 위해 두 가지 주요 기술을 사용합니다.

1. "선생님의 성적표" (기술 학습)

학교에서 선생님이 학생의 성장을 얼마나 도왔는지 추적하는 것과 마찬가지로, SMaRT는 조정인이 사건을 얼마나 해결했는지 추적합니다.

추측 게임: 새로운 조정인이 합류할 때, 시스템은 그들의 기술 수준을 알지 못합니다. 처음에는 추측치로 시작합니다.
업데이트: 조정인이 사건을 처리함에 따라, 시스템은 그들의 기술에 대한 자신의 "믿음"을 업데이트합니다. 만약 그들이 계속해서 사건을 해결한다면, 시스템은 그들이 스타라는 확신을 갖게 됩니다. 만약 그들이 어려움을 겪는다면, 추정치를 낮춥니다.
균형: 시스템은 새로운 조정인을 시도해 보고(그들이 유능한지 확인하기 위해), 동시에 이미 유능하다고 알려진 이들을 활용해야 한다는 것을 알고 있습니다. 이것은 부모가 기존에 믿고 있던 베이비시터를 신뢰하면서도, 새로운 베이비시터를 시험해 보는 것과 같습니다.

2. "미래를 대비하는" 수학 (이차 계획법)

이것이 가장 영리한 부분입니다. 단순한 시스템은 "지금 바로 이용 가능한 최고의 조정인에게 이 사건을 주라"고 말할 것입니다. 하지만 SMaRT는 앞을 내다봅니다.

비유: 당신에게 두 개의 체스판(도시 A와 도시 B)에서 놀 수 있는 뛰어난 체스 선수(조정인 A)와, 도시 A에서만 놀 수 있는 평범한 선수(조정인 B)가 있다고 상상해 보십시오.

탐욕스러운 실수: 만약 도시 A에서 경기가 들어오면, "탐욕스러운" 시스템은 즉시 뛰어난 선수에게 경기를 맡깁니다. 하지만 그 후 도시 B에서 경기가 들어옵니다. 뛰어난 선수는 이미 너무 바빠서, 시스템은 도시 B를 위해 형편없는 선수를 써야만 하는 상황에 처합니다.
SMaRT 전략: SMaRT는 "오늘 도시 A에서 평범한 선수를 쓰는 한이 있더라도, 뛰어난 선수를 도시 B를 위해 아껴두자"라고 말할 수 있습니다. 이는 오늘 승리할 확률을 약간 낮추더라도, 내일 훨씬 더 높은 승리 확률을 확보하기 위함입니다.

이를 위해 SMaRT는 패널티 시스템 역할을 하는 수학 공식(이차 계획법)을 사용합니다.

시스템은 가능한 한 많은 사건을 해결하고자 합니다.
하지만 전문가에게 과부하가 걸리는 것을 매우 싫어합니다.
시스템에는 "다이얼"( $\lambda$ 라고 불리는 매개변수)이 있습니다. 이 다이얼을 높이면, 시스템은 사건을 약간 적게 해결하더라도 누군가에게 과부하가 걸리지 않도록 매우 엄격해집니다. 다이얼을 낮추면, 시스템은 최고의 전문가들이 조금 지칠 수 있음을 감수하더라도 더 많은 사건을 해결하도록 압박합니다.

테스트 결과는 어떠했습니까?

연구진은 실제 케냐 사법부의 데이터(30,000건 이상의 사건과 2,000명의 조정인)를 사용하여 SMaRT를 테스트했습니다.

더 나은 결과: SMaRT는 기존의 수동 방식이나 단순한 "사용 가능한 최선의 인원 선택" 알고리즘보다 더 많은 사건을 해결했습니다.
공정한 업무량: SMaRT는 "스타" 조정인들이 너무 많은 업무로 인해 무너지는 것을 방지하고, 업무 부하를 더 고르게 분산시켰습니다.
유연성: 다이얼을 조절함으로써, 법원은 다음과 같이 결정할 수 있습니다. "오늘 최대한 많은 사건을 해결할 것인가, 아니면 아무도 과로하지 않도록 할 것인가?"

핵심 요약

이 논문은 SMaRT가 케냐 법원을 위한 새로운 디지털 도구의 "두뇌"가 될 준비가 되었다고 주장합니다. 현재 이 시스템은 기존의 수동 시스템을 공식적으로 대체할 수 있는지 확인하기 위해 실제 현장 테스트(무작위 대조 시험)를 거칠 예정입니다. 만약 시뮬레이션 결과만큼 실제로도 잘 작동한다면, 이는 법원의 적체 현상을 해소하고, 조정인들을 번아웃시키지 않으면서도 적재적소에 적절한 사람들이 사건을 처리할 수 있도록 도울 것입니다.

기술 요약: SMaRT – 케냐 사법부를 위한 온라인 재사용 가능 자원 할당

문제 정의
본 논문은 케냐의 법원 부속 조정(Court-Annexed Mediation, CAM) 시스템 내에서 민사 사건에 조정인을 배정하는 문제를 다룹니다. 이는 다음과 같은 세 가지 특정 제약 조건으로 인해 기존 알고리즘(표준 다중 팔 검사기(Multi-Armed Bandits) 또는 배낭이 있는 밴딧(Bandits with Knapsacks) 등)이 비효де적이거나 적용 불가능한 온라인 자원 할당 문제입니다.

미지의 상태 및 학습 의존적 품질: 조정인의 효과성(부가가치, Value Added 또는 VA)은 사전에 알려져 있지 않으며 시간이 지남에 따라 학습되어야 합니다. 새로운 조정인이 시스템에 유입되며, 탐색(exploration)과 활용(exploitation)의 균형을 맞추면서 이들의 성과를 추정해야 합니다.
연성(Soft) 및 동적 용량 제약: 엄격하고 비재충전식 한계를 가정하는 표준 "배낭이 있는 밴딧(BwK)"과 달리, 조정인은 사건이 해결됨에 따라 용량이 재충전됩니다. 그러나 시스템은 사건 도착 시 즉각적인 배정을 요구하므로 용량을 초과할 확률이 0이 아닙니다(과부하). 사법부는 조정인이 동시에 최대 3개의 사건을 처리하는 것을 선호하지만, 이를 초과하는 것은 엄격한 금지가 아닌 "연성" 제약입니다.
고차원 상태 공간 및 이질적 자격 인증: 87개 법원 스테이션과 12개 사건 유형에 걸쳐 다양한 자격을 갖춘 2,000명 이상의 조정인이 존재합니다. 조정인은 해당 (스테이션, 사건 유형) 쌍에 대해 인증을 받은 경우에만 배정될 수 있습니다. 이는 자원이 중첩되지만 구별되는 실행 가능한 작업 집합을 가진 복잡한 이분 매칭(bipartite matching) 문제를 생성합니다.

목표는 전체 사건 해결률(합의율)을 극대화하는 동시에, 최적의 조정인을 배정하는 것과 용량 제약을 준수하여 형평성 있는 업무 분배를 보장하는 것 사이의 트레이드오프를 관리하는 것입니다.

방법론
저자들은 계량경제학적 추정, 베이지안 학습, 그리고 이차 계획법(Quadratic Programming, QP)을 통합한 알고리즘인 SMaRT(Selecting Mediators that are Right for the Task)를 제안합니다.

부가가치(VA) 추정:
- 저자들은 조정인의 기여도를 추정하기 위해 (교육 연구에서 흔히 사용되는) 부가가치 모델을 응용합니다. 이 모델은 사건의 통제 변수(유형, 스테이션, 시간)와 조정인 고정 효과를 기준으로 사건 해결 결과를 회귀 분석합니다.
- 불확실성을 처리하고 온라인 학습을 가능하게 하기 위해, 시스템은 각 조정인의 VA에 대한 가우시안 신념 분포(Gaussian belief distribution)를 유지합니다.
- 업데이트: 사건 결과가 관찰되면 모멘트 매칭(moment matching)을 통해 사후 분포가 업데이트됩니다. 명시적 추정치로부터의 표류를 방지하기 위해, 시스템은 과거 데이터를 바탕으로 전체 VA 추정 절차를 사용하여 매주 이러한 사후 분포를 재보정합니다.
이차 계획법(QP) 정식화:
- 할당 결정은 짧은 시간 지평( $T=10$ )에 대한 QP로 모델링됩니다.
- 목적 함수: 기대 해결 확률(조정인 VA + 기본 사건 확률)의 합에서 용량 위반에 대한 이차 페널티 항을 뺀 값을 최대화합니다.
- 제약 조건:
  - 도착하는 모든 실제 사건은 반드시 배정되어야 합니다(강한 제약).
  - "섀도우 케이스(Shadow cases)"(미래 수요를 시뮬레이션하기 위해 분포에서 샘플링된 미래 사건)는 배정되지 않은 상태로 남을 수 있습니다.
  - 연성 용량: 이 제약은 조정인이 용량을 초과하는 것을 허용하지만, 위반 사항은 슬랙 변수 $\xi_u$ 로 포착됩니다. 목적 함수는 $\xi_u^2$ 에 페널티를 부여하며, 이는 과부하 페널티의 엄격함을 조절하는 트레이드오프 파라미터 $\lambda$ 를 생성합니다.
- 이러한 정식화는 알고리즘이 현재의 사건에 탐욕적으로 배정하여 과부하를 일으키는 대신, 미래의 고가치 사건을 위해 고성능 조정인을 "보류(hold back)"할 수 있게 합니다(기회비용).
할당 알고리즘:
- 사건이 도착하면 시스템은 현재 사건, 섀도우 케이스, 그리고 적격한 조정인을 포함하는 상태 그래프를 구성합니다.
- QP를 풀어 분수 할당(fractional assignments)을 얻습니다.
- 알고리즘은 QP 해에서 가장 높은 분수 할당량을 가진 조정인에게 도착한 사건을 배정합니다.
- 변형 모델: 논문은 두 가지 학습 변형을 테스트합니다:
  - SMaRT(E): VA 신념의 평균을 사용합니다(활용 중심).
  - SMaRT(S): 신념 분포에서 VA를 샘플링합니다(톰슨 샘플링 방식의 탐색).

주요 기여

새로운 알고리즘 프레임워크: SMaRT는 온라인 학습을 통한 에이전트 품질 학습과 연성 및 재충전 가능한 용량 제약이 있는 고차원의 이질적 자격 인증 환경을 결합한 최초의 알고리즘입니다. 이는 BwK의 "강한 제약" 가정이나 다른 재사용 가능 자원 알고리즘(예: OM-RR-PA)의 "지연된 할당" 가정을 넘어섭니다.
조절 가능한 트레이드오프: 이차 페널티 파라미터 $\lambda$ 를 통해 관리자는 용량 제약의 엄격함과 전체 사건 해결률 사이의 균형을 맞추며 시스템의 동작을 명시적으로 조정할 수 있습니다.
섀도우 가격(Shadow Price)의 해석 가능성: QP의 쌍대 변수(dual variables)는 조정인의 한계 가치에 대한 "섀도 shadow price"를 제공하며, 이는 다양한 맥락에서의 가치를 해석 가능한 메트릭으로 제공하여 "보류" 메커즘을 이해하는 데 도움을 줍니다.

결과
저자들은 정형화된 시뮬레이션과 케냐 사법부의 실제 데이터(2016~2025년, 약 30,600건의 사건)를 모두 사용하여 SMaRT를 검증했습니다.

정형화된 시나리오: SMaRT는 일관되게 베이스라인(Least Load, Greedy, Thompson Sampling)보다 우수한 성능을 보였습니다. 고성능 조정인이 여러 셀(cell)에 걸쳐 공유되는 시나리오에서, SMaRT는 해당 조정인을 과부하시키는 "탐욕적" 함정을 성공적으로 피하고, 미래의 고가치 기회를 위해 용량을 보존하도록 사건을 분배합니다.
실제 데이터 시뮬레이션 (알려진 VA): 조정인의 VA를 알고 있을 때, 낮은 $\lambda$ 를 가진 SMaRT는 이론적 "상한선(Upper Bound)"(모든 사건에 절대적으로 최선인 조정인을 배정하는 것)에 근접한 합의율을 달성하면서도, 순수 탐욕적 접근 방식에 비해 현저히 낮은 과부하(OCDM)와 더 나은 형평성(낮은 지니 계수)을 보여주었습니다.
실제 데이터 시뮬레이션 (학습되는 VA):
- 공백 상태 초기화(Blank Slate Initialization): 사전 지식 없이 시작할 때, 용량 제약은 자연스럽게 충분한 탐색을 유도하여 SMaRT(E)(평균 기반)가 Greedy 베이스라인에 대해 잘 작동하게 만듭니다.
- 웜 스타트 초기화(Warm Start Initialization): 과거 데이터로 초기화된 경우, SMaRT(S)(샘플링 기반)는 Greedy 및 TS* 베이스라인보다 크게 앞섭니다. 이는 Greedy 방식이 간과하는 고성능이지만 경험이 적은 조정인을 성공적으로 식별하여, 더 높은 합의율을 달면서도 더 낮은 과부하를 유지합니다.
조절 가능성: $\lambda$ 를 높이면 과부하가 줄어들고 형평성(낮은 지니 계수)이 개선되지만, 합의율이 약간 감소합니다. 이는 시스템의 유연성을 입증합니다.

의의 및 주장
본 논문은 SMaRT가 연성 제약, 즉각적인 할당 요구, 학습 필요성이라는 특정한 조합 때문에 기존 문헌이 직접적으로 다룰 수 없었던 복잡한 실제 자원 할당 문제에 대해 실행 가능하고 효과적인 솔루션을 제공한다고 주장합니다.

저자들은 이러한 결과를 바탕으로 SMaRT를 사법부의 디지털 플랫폼(Cadaster) 내 "스마트 할당" 기능의 백엔드로 배포할 계획이라고 밝혔습니다. 시스템을 실제로 테스트하기 위해 무작위 대조 실험(RCT)이 승인되었습니다. 이 연구의 의의는 알고리즘적 기여뿐만 아니라, 공공 부문에서 사건 적체를 줄이고, 비용을 낮추며, 조정인 간의 형평성 있는 업무 분배를 개선할 수 있는 잠재력에 있습니다. 논문은 설계가 케냐 사법부와의 긴밀한 협력을 통해 확인된 운영상의 제약 조건을 바탕으로 이루어졌음을 강조하며, 알고리즘이 실제 현장에 적용 가능하다는 점을 분명히 하고 있습니다.