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

技術要約：SMaRT – ケニア司法制度におけるオンライン再利用可能リソース割り当て

問題定義
本論文は、ケニアの裁判所併設調停（CAM）システムにおける、民事事件への調停者の割り当てという課題に取り組んでいる。これは、既存のアルゴリズム（標準的なマルチアームド・バンディットやバンディット・ウィズ・ナップサックなど）では非効率、あるいは適用不可能となる3つの特定の制約を持つ、オンライン・リソース割り当て問題である。

1. 未知かつ学習依存の質： 調停者の有効性（付加価値：Value Added, VA）は事前に既知ではなく、時間の経過とともに学習する必要がある。新しい調停者がシステムに参入するため、探索と活用（exploration and exploitation）のバランスを取りながら、そのパフォーマンスを推定しなければならない。
2. ソフトで動的な容量制約： 標準的な「バンディット・ウィズ・ナップサック（BwK）」が厳格で非補充型の制限を想定しているのに対し、調停者の容量は案件が解決されるにつれて補充される。しかし、システムは案件の到着時に即時の割り当てを必要とするため、容量を超える確率（オーバーロード）がゼロではない。司法当局は調停者が同時に扱う案件を3件以内に抑えることを好むが、これを超えることは厳格な禁止事項ではなく、「ソフト」な制約である。
3. 高次元の状態空間と不均一な認定： 87の裁判所ステーションと12の事件タイプにわたる、多様な認定を持つ2,000人以上の調停者が存在する。調停者は、特定の（ステーション、事件タイプ）のペアに対して認定されている場合にのみ、その案件に割り当てられることができる。これにより、リソースが重複しつつも異なる実行可能なタスク集合を持つ、複雑な二部マッチング問題が生じる。

目的は、最適な調停者の割り当てと、容量制約の遵守（公平なワークロード分布の確保）との間のトレードオフを管理しながら、全体的な案件解決率（合意率）を最大化することである。

手法
著者らは、計量経済学的推定、ベイズ学習、および二次計画法を統合したアルゴリズムであるSMaRT（Selecting Mediators that are Right for the Task）を提案している。

1. 付加価値（VA）の推定：

   • 著者らは、調停者の貢献度を推定するために、教育研究で一般的な付加価値モデルを応用している。このモデルは、ケースのコントロール変数（タイプ、ステーション、時間）と調停者の固定効果を用いて、案件解決の結果を回帰する。
   • 不確実性を扱い、オンライン学習を可能にするために、システムは各調停者のVAに対してガウス型信念分布を保持する。
   • 更新： 案件の結果を観察すると、モーメント・マッチングを通じて事後分布が更新される。明示的な推定値からのドリフトを防ぐため、システムは履歴データを用いた完全なVA推定手順を用いて、これらの事後分布を毎週再校正する。

2. 二次計画法（QP）定式化：

   • 割り当て決定は、短いタイムホライゾン（$T=10$）における二次計画問題としてモデル化される。
   • 目的関数： 期待される解決確率の総和（調停者のVA ＋ 基本的な案件確率）から、容量違反に対する二次ペナルティ項を差し引いたものを最大化する。
   • 制約条件：
     • 到着するすべての実案件は必ず割り当てられなければならない（ハード制約）。
     • 「シャドウ・ケース」（需要分布からサンプリングされた将来の案件）は、将来の需要をシミュレートするために未割り当てのままとなる場合がある。
     • ソフト容量： この制約は、調停者が容量を超えることを許容するが、違反はスラック変数 $\xi_u$ によって捕捉される。目的関数は $\xi_u^2$ にペナルティを課し、トレードオフ・パラメータ $\lambda$ がオーバーロードの厳格さを制御する。
   • この定式化により、アルゴリズムは高性能な調停者を将来の高価値な案件のために「取っておく（hold back）」ことが可能になる（現在の案件に貪欲に割り当ててしまうと、オーバーロードを招く可能性があるため）。

3. 割り当てアルゴリズム：

   • 案件の到着時、システムは現在の案件、シャドウ・ケース、および適格な調停者を含む状態グラフを構築する。
   • QPを解いて分数割り当て（fractional assignments）を得る。
   • アルゴリズムは、QPの解において最も高い分数割り当てを持つ調停者に、到着した案件を割り当てる。
   • バリアント（変種）： 本論文では2つの学習バリアントをテストしている：
     • SMaRT(E)： VAの平均値を使用する（活用重視）。
     • SMaRT(S)： 信念分布からVAをサンプリングする（トンプソン・サンプリング型の探索）。

主な貢献

• 斬新なアルゴリズム・フレームワーク： SMaRTは、エージェントの質に関するオンライン学習と、ソフトで補充可能な容量制約を、高次元で不均一な認定設定の中で組み合わせた初めての枠組みである。これは、BwKの「ハード制約」の仮定や、他の再利用可能リソースアルゴリズム（OM-RR-PAなど）の「遅延割り当て」の仮定を超えたものである。
• 調整可能なトレードオフ： 二次ペナルティ・パラメータ $\lambda$ により、管理者は容量制約の厳格さと案件解決率との間で、システムの挙動を明示的にチューニングできる。
• シャドウ価格の解釈可能性： QPの双対変数は、調停者の「シャドウ価格」を提供し、異なる文脈における彼らの限界価値を示す解釈可能な指標となる。これは「取っておく（holding back）」メカニズムを理解するのに役立つ。

結果
著者らは、様式化されたシミュレーションと、ケニア司法制度からの実データ（2016–2025年、約30,600件の案件）の両方を用いてSMaRTを検証している。

• 様式化されたシナリオ： SMaRTは、一貫してベースライン（Least Load, Greedy, Thompson Sampling）を上回る性能を示す。高性能な調停者が複数のセルで共有されるシナリオにおいて、SMaRTは、その調停者をオーバーロードさせるという「貪欲な（greedy）」罠を回避し、将来の高価値な機会のために容量を確保するように案件を分配することに成功している。
• 実データ・シミュレーション（既知のVA）： 調停者のVAが既知である場合、低い $\lambda$ を用いたSMaRTは、理論的な「上限（Upper Bound）」（すべての案件に絶対的に最適な調停者を割り当てる場合）に近い合意率を達成しつつ、純粋な貪欲法と比較して大幅に低いオーバーロード（OCDM）と優れた公平性（より低いGini指数）を実現している。
• 実データ・シミュレーション（学習するVA）：
  • 空白状態からの初期化： 事前知識がない状態で開始した場合、容量制約が自然に十分な探索を誘発するため、SMaRT(E)（平均ベース）はGreedyベースラインに対して良好なパフォーマンスを示す。
  • ウォームスタート初期化： 履歴データを用いて初期化された場合、SMaRT(S)（サンプリングベース）は、GreedyおよびTS*ベースラインを大幅に上回る。これは、Greedyなアプローチが見落としがちな、高性能だが経験の浅い調停者を特定することに成功しており、より高い合意率を維持しながら、より低いオーバーロードを実現している。
• チューナビリティ（調整可能性）： $\lambda$ を大きくすると、オーバーロードが減少し、Gini指数が低下して公平性が向上する一方で、合意率がわずかに低下する。これは、システムの柔軟性を実証している。

意義と主張
本論文は、SMaRTが、ソフト制約、即時割り当ての要件、および学習の必要性という特定の組み合わせにより、既存の文献では直接対処できなかった複雑な実世界の資源割り当て問題に対して、扱いやすく効果的なソリューションを提供すると主張している。

著者らは、これらの結果に基づき、SMaRTを司法制度のデジタルプラットフォーム（Cadaster）における「スマート・アサインメント」機能のバックエンドとして展開する計画であると述べている。このシステムを実地でテストするためのランダム化比較試験（RCT）も承認されている。その意義は、アルゴリズムの貢献だけでなく、公的部門の設定において、調停者間の公平な仕事の分配を改善し、司法のバックログを削減し、コストを抑える可能性にある。論文は、設計がケニア司法制度との密接な協力によって特定された運用上の制約に基づいていることを強調しており、アルゴリズムが実世界での展開において実現可能であることを保証している。