DEIM Forum 2023 2b-6-5

選好の有無が混在する場合のマッチング手法
武田 雅俊†

鈴木 伸崇††† 筑波大学情報学群知識情報・図書館学類 〒 305–8550 茨城県つくば市春日 1-2†† 筑波大学図書館情報メディア系 〒 305–8550 茨城県つくば市春日 1-2
E-mail: †s1911502@s.tsukuba.ac.jp, ††nsuzuki@slis.tsukuba.ac.jp
あらましマッチング理論では，大まかに「二部マッチング問題」と「配分マッチング問題」の二つのタイプの問題について扱う．この二つのマッチング問題において，DA アルゴリズムや TTC アルゴリズムを用いることで安定的マッチングを求められることがわかっている．しかし，クラウドソーシングのタスク割り当てなどの状況においては，選好を持つのは必ずしもワーカ側だけでなく，タスク側も求めるワーカのスキルなどの点から選好を持つことがある．
現在のマッチング理論では，選好の有無が混在するケースにおいて従来のアルゴリズムを単体で適用することは不可能である．そこで本研究では，選好の有無が混在する多対多マッチング問題を「混在マッチング問題」と新たに定義し，従来のアルゴリズムを複数組み合わせることにより混在マッチング問題に対する手法を提案する．
キーワード マッチング，二部マッチング問題，配分マッチング問題，タスク割り当てやキャパシティに考慮したタスクの割り当てを行う必要がある．

1 はじめに
1. 1 研 究 背 景
マッチング理論では，数理的アプローチで人と人，人とモノ・

こういったクラウドソーシングのタスク割り当てなどの状況においては，選好を持つのは必ずしもワーカ側だけでなく，タス
ク側も求めるワーカのスキルなどの点から選好を持つことがある．例えば，

サービスをどのようにマッチさせたらよいかを研究する．それ•

簡単なデータ入力

ぞれの需要と供給をできるだけ満たしたマッチングを実現す

•

アンケート

るため，様々なアルゴリズムが社会で幅広く利用されている．

•

ゲームやアプリなどのテスター

マッチング理論で扱うマッチングは，いくつかのタイプに分類されるが，代表的なものとして以下の二つがある．一つが「二などは，どのワーカに割り当てられても結果のデータ品質に影響がないタスクである．一方で，部マッチング問題」と呼ばれるもので，人々が二手に分かれ，•プログラミング

一方の側の人が他方の側の人とマッチする状況を考える．二手•

意訳が必要な翻訳に分かれた人々はどちらの側もどの相手とマッチしたいかにつ•

ホームページやインテリアなどのデザイン案の考案

いて選好を持つ．もう一つが「配分マッチング問題」と呼ばれるもので，一方の側の人が他方の側の非分割財とマッチする状
況を考える．非分割財とは，自動車や臓器，パソコンなどこれ以上分割できないモノ・サービスのことを指す．二部マッチン
グ市場と異なる点は，人側は希望順位について選好を持つが，財はそれを持たないという点である．

などは，ワーカのスキルによって結果のデータ品質が異なるため，よりスキルの高いワーカに割り当てられることが好ましいタスクとなる．つまり，選好を持つタスクと選好を持たないタスクが混在するマッチングとなる．また，学生と授業科目のマッチングでは，特に履修条件がなく定員一杯まで希望する学生を受け入れる授業科目と，その授業科目の分野に関連する学

この二つのマッチング問題において，前者は DA アルゴリズ

部・学科の学生やその授業科目に関連する別の科目を履修済み

ム，後者は TTC アルゴリズムが中心的な役割を持ち，これらである学生を優先的に受け入れたいなど，受け入れに関する選のアルゴリズムを用いることで安定的なマッチングや効率的なマッチングを求められることがわかっている．この二つのメカ
ニズムは非常に重要であり，実際の市場でマッチングをデザインする場合には，どちらか一方を現実に合わせて改良することが多い．しかし，実際のマッチングにおいて二つのマッチング
問題の両方の要素を併せ持つような問題に対し，従来のアルゴ
リズムがそのまま適用できるとは限らない．
例えば，近年，新たな目的遂行の手段としてクラウドソーシ
ングが注目を集めている．マイクロタスク型のクラウドソーシ
ングでは，単純な作業にタスクを分割しそれを複数のワーカで分担して行うことで目的を遂行する．そのため，ワーカの能力好を持つ履修条件がある授業科目が混在するマッチングとなる．
これらの選好の有無が混在するマッチング問題に対して，二部マッチング問題や配分マッチング問題で用いられるマッチン
グアルゴリズムを単体で適用することは不可能であるため，二部マッチング問題と配分マッチング問題のどちらかに分類する
ことは極めて困難である．つまり，従来のマッチング問題と異なる新たなマッチング問題に対して適用可能な新たなマッチン
グ手法を考える必要がある．こういった応募・提案を受ける側の集合の中で選好の所有の有無が混在しているマッチング問題を本研究では「混在マッチング問題」として取り扱う．また，
本論文では想定する状況として，ボランティアベースなど参画するワーカがあらかじめ把握されている，マイクロタスク型の分かれた人々はどちらの側もどの相手とマッチしたいかについクラウドソーシングのタスク割り当てを例に提案手法の説明やて選好を持つ．例として，図 2.1 に簡単な二部マッチング M

評価実験を行う．混在マッチング問題では複数のワーカに対しを示す．各頂点はどちらの側に属しているかに関わらず選好リ

複数のタスクを割り当てる多対多のマッチング手法を必要とす
る．各ワーカはそれぞれ選好を持っており，各タスクには選好を持つものと持たないものがある．またワーカには許容可能なタスク数，タスクには受け入れ可能ワーカ数がある．本研究の目的は，DA アルゴリズムを含む複数のアルゴリズムを適切に組み合わせることにより，混在マッチング問題に対して適用可
図1

能な新たな多対多マッチングの手法を考案することである．

二部マッチング M

評価実験では，複数通りのテストデータを作成し，提案手法を実行した．マッチした相手の選好順位の合計を評価指標（合計不満度）とし，その観点からベースライン手法との比較を行なった．加えて，マッチングパターンごとの比較によって評価を行った．得られた結果では，提案手法を用いることでマッチ
ング全体の合計不満度がベースライン手法と比べて小さいマッ
チングを実現した．
本論文の構成は以下の通りである．第２章では，二部マッチ

ストを所有している．すなわち，二部マッチング問題では自分が相手を選ぶと同時に，自分も相手に選ばれることに特徴がある．具体例として，一対一マッチングの安定結婚問題や一対多マッチングの研修医配属問題などが二部マッチング問題として挙げられる．
ここで，マッチングの重要な評価指標である安定性について，
安定結婚問題を例に挙げて説明をする．安定結婚問題は以下のング問題と配分マッチング問題，混在マッチング問題の定義や３つの要素からなる.

主要なアルゴリズムについて述べる．第３章では，提案アルゴ（ 1 ） p 人の男性を m1 , …, mp ，男性の集合 M = {m1 , …

リズムについて述べる．第４章では，評価実験について述べる．

, mp } と表す．

第５章では，本研究のまとめを述べる．

（ 2 ） q 人の女性を w1 , …, wq ，女性の集合 W = {w1 , …

, wq } と表す．

2 諸 定 義2. 1 マッチング
離散数学や計算機科学の分野においてマッチングとは，グラ（ 3 ） 各男性 m ∈ M は，女性陣 w1 , …, wq のうち誰とマッチしたいかについて選好 ≿m を持つ．同様に各女性 w ∈ W は
男性陣 m1 , …, mp のうち誰とマッチしたいかについて選好 ≿wを持つ．

フにおける頂点ペアの集合，すなわち頂点と頂点の対応を求め

この問題の出力は一対一のマッチングとなる．一対一マッチン

る（結び付ける）ことを意味する．就活や入試，結婚など社会グにおいて，「マッチング」は男女のペアからなる集合で，誰もにおける様々な問題において，グラフの頂点を人や企業とみな２人以上とはペアになっていないものと定義される．mi と wj

し，最適なペアづくりや資源配分を実現するメカニズムについがペアになっているとき，M (mi ) = wj および M (wj ) = miて取り扱うのがマッチング理論である．

と書く．また mi と wj はマッチしているという．ここで以下本研究においても，マッチングはすべての個人またはモノかのようなマッチングを考える．

らなる集合からすべての個人またはモノからなる集合への写像を指す．また，各頂点は選好と定員に関する情報を持つ．本研
w1 w 4 w2
m1 : w3 w5 ○○1 m3 m2 m5
w 1 : m4 m

た，選好 ≿ は完備性と推移性という二つの性質を満たすと仮w2 w 3 w 4 w5m2 : w1 ○m 2 m3 m4
w 2 : m5 m1 ○定する．完備性とは，任意の二つの選択肢 x と y が比較できる

w3 w 5 w2
m3 : w1 w4 ○m 3 m1 m5 m4
w 3 : m2 ○ことを意味し，必ず x ≿ y または y ≿ x となる．次に，推移性

w4 w 1 w3
m4 : w2 w5 ○m 4 m2 m5 m1
w 4 : m3 ○w5 w 2 w3
m5 : w4 w1 ○m 5 m2 m4
w 5 : m3 m1 ○究において，選好は全順序制約を満たす完全リストとする．まとは，任意の三つの選択肢 x, y, z があったとき，選好 ≿ が連結して推移していくこと，つまり，x ≿ y と y ≿ z であるときに x ≿ z となることを意味する．定員は多対一マッチングまた

この状況のマッチングにおいて m1 と w5 はペアになっておらは多対多マッチングの場合に導入され，各頂点は定員を超えてず，男性 m1 は現在のパートナー w1 よりも w5 を好み，女性マッチすることはできない．

w5 は現在のパートナー m5 よりも m1 を好むとき，(m1 , w5 )2. 2 二部マッチング問題
従来のマッチング理論の研究では，マッチングは大きく二部
マッチング問題と配分マッチング問題の二つに分類される．二部マッチング問題では，人々が二手に分かれ，一方の側の人が他方の側の人とマッチする二部グラフの状況を考える．二手にをマッチング M に対するブロッキングペアという．つまりブロッキングペアは「マッチングを壊す危険性をはらんだペア」
である．ブロッキングペアを含まないマッチングを安定マッチ
ングという．ゲールとシャプレイは，1962 年に発表した論文
で，結婚市場を導入し，安定マッチングを定義し，安定マッチ
ングの存在を示した．彼らがその存在を示すために用いたのが

DA アルゴリズムである．DA アルゴリズムについては 3 章で

2. 4 混在マッチング問題

詳しく説明する．DA アルゴリズムより本質的に速いアルゴリ

従来のマッチング理論の研究では，主に上記の二つのマッチ

ズムがないことや，多対一マッチングに対しても一対一マッチ

ング問題について取り扱っている．しかし，例えば，先ほどのングから容易に拡張可能であることから，二部マッチング問題

学校選択問題の例で，入学させる生徒について選好を持つ学校

においては，DA アルゴリズムを用いてマッチングを求めること選考を持たない学校が混在しているマッチング問題であったとが最適であるとされている．

場合，従来の二つのマッチング問題のどちらかに分類することは不可能である．そこで本論文では，こういった選好の有無が

2. 3 配分マッチング問題
配分マッチング問題では，一方の側の人が他方の側の非分割財とマッチする状況を考える．非分割財は意思を持った人では混在する場合のマッチング問題を「混在マッチング問題」として扱う．例として，図 2.3 に簡単な混在マッチング M を示す．

なく，自動車やパソコンなどこれ以上分割不可能なモノを指す．
例として，図 2.2 に簡単な配分マッチング M を示す．基本モ

図3
図2

配分マッチング M

混在マッチング M

混在マッチング問題では，選好を持つ財，持たない財に対しそれぞれ異なる処理が必要となるため，従来のマッチングアル

デルとしては，まず個人の集合があり，非分割財の集合がある．

ゴリズムを単体では適用できない．また，財の選好の有無に関二部マッチング問題と異なる点としては，人々はどの財が好き

わらずワーカはその区別を行わない．つまり，タスクの分類にかという選好を持つが，財は選好を持たないというところにあよって二部マッチングと配分マッチングに分割し，段階的に割る．財が最初に誰のものであるかによって，配分マッチング問り当てを行うことは公平性の観点から望ましくない．本研究で題の中でもさらに細かく分類が可能ではあるが，具体例として

は，一回のマッチングメカニズムで混在マッチング問題に対しルームマッチング問題や臓器移植問題が挙げられる．

てより安定的かつ合計不満度の小さいマッチングを求めること

ここで，多対一や多対多の配分マッチング問題において，新を目的としている．

たに登場する性質である非浪費性について公立学校選択問題を例に説明する．ここでは，３人の生徒 (i1 , i2 , i3 ) と 2 つの学校

(s1 , s2 ) を考える．また，各学校の定員を 2 とする．学校は選
好を持たないが，生徒は以下のように共通の選好をもつ．以下で示されるようなマッチングは浪費的なマッチングである．

3 提案手法3. 1 本研究で用いる記法
説明の都合上，本研究では以下の記法を用いる．

•

W ： ワーカ集合

s1 s 2
i1 : ○•

T ： タスク集合

s2i2 : s1 ○•p(w)： タスク t に対してワーカ w が持つ選好順位s2i3 : s1 ○一番人気の学校 s1 は定員割れで，二番人気の学校 s2 は定員一•p(t)： ワーカ w に対してタスク t が持つ選好順位•

c(w)： ワーカ w の許容可能なタスク数（定員）•c(t)： タスク t が受け入れ可能なワーカ数（定員）杯となっている．一番人気の学校にマッチしていない生徒は i1
以外の 2 人で，この 2 人はどちらも自分のマッチしている学校

3. 2 評価指標について

よりも定員割れを起こしている学校 s1 とマッチしたいと思って本研究では，非浪費性の検証と合計不満度を評価指標としている．よって，このマッチングは浪費的であるといえる．すな用いる．
．非浪費性の検証について，出力されたマッチングがわち，非浪費的なマッチング M では，各生徒が最終的にマッ最大マッチングでなかった場合に定員割れのタスクを希望するチした学校より上位に希望している学校があった場合に，そのワーカが存在していないことを確認し，非浪費性を満たして学校は必ず定員一杯まで生徒とマッチしている．ここでは，生いるかを評価する．不満度について，第 i 希望の相手とペアに

徒 i2 と学校 s1 がマッチしても，このマッチが他の生徒を犠牲なった人の不満度を i とし，そのマッチングの全員の不満度のにすることはないため，この概念はブロッキングペアとは異な総和を合計不満度と定義する．そして，各ワーカおよびタスク

る．非浪費性はマッチングの品質を評価する指標の一つに数えがより上位に希望する相手とマッチングできているほど不満度られる．

の小さい，より高品質なマッチングであると評価する．同条件のマッチングのシミュレーションデータを用いてベースライン
手法と比較し，それぞれの合計不満度の比較を行う．

3. 3 アルゴリズム

リズムと似ているが，ステップ２以降で別の方法を使う．決定

本節では，本研究で提案するアルゴリズムについて述べる．

的な違いは, ボストンアルゴリズムではそれぞれのステップでこのアルゴリズムは，非浪費性と一定条件下での安定性を考慮実現するマッチは一時的ではなく，最終決定されるということしている．二部マッチング問題において，DA アルゴリズムをである．言い換えれば，ここでの最終的な受け入れは即時に決適用することにより安定マッチングを得ることわかっている．

定され，アルゴリズムが終了する最後のステップまで先送りにしかし，混在マッチング問題においては選好を持たない財に対されない．また，このアルゴリズムはタスク側の選好の有無にして仮マッチを決定することができないため，DA アルゴリズ

関わらず適用が可能であるため，評価実験の際にはボストンア

ムを単体で適用することができない．そこで，主に配分マッチ

ルゴリズム単体の適用をベースライン手法として比較を行う．

ングで採用される，仮マッチを用いないアルゴリズムであるボ

ボストンアルゴリズムの進行は以下の通りである．
ステップ１

ストンアルゴリズムを組み合わせることにより，この問題を解

•

決する．

各ワーカ w は自分の選好リストの１番目に希望しているワー

提案アルゴリズムでは，応募を受ける対象であるタスクが選カに応募する．各タスクは選好リストに従って，応募したワー

好を持つか否かで異なる処理を行う．応募を受けるタスクが選

カと定員までマッチする．受け入れの決定は，タスク t が定員

好を持つ場合には二部マッチング問題のように DA アルゴリズ

c(t) 人のワーカを受け入れるか，あるいは応募したワーカをす

ムの仮マッチを，選好を持たない場合には配分マッチング問題

べて受け入れるまで行う．残りのワーカはすべて拒否される．
ステップ k, k >= 2のようにボストンアルゴリズムの確定マッチを用いる．提案手•法の根幹となる，DA アルゴリズムとボストンアルゴリズムに定員に達していないワーカ w はそれぞれ，許容可能かつまついて説明する．

3. 3. 1 DA アルゴリズム
DA アルゴリズム（受け入れ保留アルゴリズム：Deferred

だ応募していないタスクの中で最も希望しているタスクに応募
する．

•

終了

Acceptance algorithm）は安定結婚問題において，安定マッチ

どのワーカも拒否されないステップ，あるいはすべてのタス

ングを求める方法として，1962 年にデービット・ゲール（David

クの定員が一杯になったステップでアルゴリズムは終了する．

Gale）とロイド・シャプレイ（Lloyd Shapley）によって考案タスクが選好リストを持たない場合，ボストンアルゴリズムのされたアルゴリズムである．特徴として，DA アルゴリズムに確定マッチでは優先順序メカニズムに従って応募が早い順に受おいて提案する側は虚偽申告のインセンティブを持たず，かつ，

け入れる．実際に学校選択問題などにおいて学校側が選好を持

安定マッチングを求めることができる，などが挙げられる．DA

たないと設定した場合，メカニズムの主催者が何らかの方法

アルゴリズムの進行は以下の通りである．

(ランダムに決定など) で応募者の順番を線形的に決定する必要

•

ステップ１

各ワーカ w は自分の選好リストの１番目に希望しているタスクに応募する．各タスク t は選好リストに従って，応募した
ワーカと定員までマッチする．受け入れの決定は，タスク t が定員 c(t) 人のワーカを受け入れるか，あるいは応募したワー
カをすべて受け入れるまで行う．残りのワーカはすべて拒否される．

•

ステップ k, k >= 2

定員に達していないワーカ w はそれぞれ，許容可能かつまだ応募していないタスクの中で最も希望しているタスクに応募する．定員を超えて応募を受けたタスクは以下の中から最も好きなワーカを一時的に受け入れる．ほかのワーカを断る．
（ 1 ） 新しく応募をしてきたワーカ（ 2 ） 前のステップで一時的に受け入れたワーカ（複数の可
能性あり）

•

終了

どのワーカも断られなくなったときにアルゴリズムは終了する．各ワーカはアルゴリズムが終了したときに一時的に割り当てられたタスクとマッチする．

3. 3. 2 ボストンアルゴリズム
ボストンアルゴリズム（受け入れ即決アルゴリズム：Imme-

diate Acceptance algorithm, IA アルゴリズム）は DA アルゴがある．

3. 4 提案アルゴリズム
本研究で提案するアルゴリズムは，ボストンアルゴリズムのステップ毎に割り当てを確定する性質を利用し，DA アルゴリ
ズムに組み込むことで仮マッチを決定できない財に対して安定性や非浪費性の性質を満たし，かつ公平な処理を行う．提案ア
ルゴリズムが安定性を持つことは，DA アルゴリズムが安定性を持つ証明と同様に背理法を用いて簡単に示すことができる．
まず，提案アルゴリズムにて出力されたマッチングが安定マッ
チングでない，すなわち，ブロッキングペアが存在すると仮定する．その場合，ブロッキングペア (wi ,tj ) が存在するはずである．しかし，アルゴリズムの進行を考えるとマッチングは応募するワーカの選好が上位の順に行われるため，アルゴリズムの終了より前のステップにてペア (mi ,wj ) が仮マッチされており，その後，マッチの解消が発生していなければならない．しかし，アルゴリズムの進行上選好を持つ財はステップ数が進む
ほど希望順位の高い相手とマッチングする．また，選好を持たない財はそもそも選好を持たないためブロッキングペアを生成することができない．つまり，ブロッキングペアに矛盾し，提案アルゴリズムは安定マッチングを出力する．具体的なアルゴ
リズムの進行は以下の通りである．

•

ステップ１

各ワーカ w は自分の選好リストの１番目に希望しているタス
クに応募する．
（ 1 ） 応募を受けたタスクが選好を持つ場合
各タスク t は選好リストに従って，応募したワーカと定員までマッチする．受け入れの決定は，タスク t が定員 c(t) 人のワーカを受け入れるか，あるいは応募したワーカをすべて受け入れるまで行う．残りのワーカはすべて拒否される．
（ 2 ） 応募を受けたタスクが選好リストを持たない場合

Algorithm 1 Mixed Acceptance algorithm
Require: ワ ー カ 集 合 W L=(w1 , w2 , ..., wn ) ,wi=<i=< n, タスク集合 T L = (w1 , w2 , ..., tm ),tj =(c(wi ), p(wi )) 1 =(ctj , ptj ) 1 <=j<=m
Ensure: マッチしているワーカとタスクの組の集合 resultlist
1: temlist = []2: conlist = []3: resultlist = []4: while cwi > 0 かつ len(pwi ) > 0 の条件を満たすワーカ wi

各タスク t は定員に達するまで応募したワーカと確定的な∈ W L が存在する doマッチをする．タスク t が定員 c(t) 人のワーカを受け入れるか，

5:

あるいは応募したワーカをすべて受け入れるまで行う．残りの6:

ワーカはすべて拒否される．また，タスクの定員に達した時点

7:

temlist.append(wi , tj )8:cwi = cwi−1

でワーカの選好リストからそのタスクを削除する．

•

ステップ k, k >= 2

if ctj > 0 thenif pti > 0 thenctj = ctj−1

9:
10:

else

定員に達していないワーカ w はそれぞれ，許容可能かつま11:

conlist.append(wi , tj )だ応募していないタスクの中で最も希望しているタスクに応募

12:

cwi = cwi−1

する．

13:

ctj = ctj−1（ 1 ） 応募を受けたタスクが選好リストを持つ場合

14:

if ctj == 0 then

定員を超えて応募を受けたタスクは以下の中から最も好きな

15:

WL 内のワーカのうち，tj とマッチしていない各 wi に対してワーカを一時的に受け入れる．ほかのワーカを断る．
（ a ） 新しく応募を受けたワーカ

end if17:（ b ） 前のステップで一時的に受け入れたワーカ（複数の可

18:

能性あり）

19:

（ 2 ） 応募を受けたタスクが選好リストを持たない場合

20:

ステップ 1 と同様に各タスク t は定員に達するまで応募した

21:

ワーカと確定的なマッチをする．タスク t が定員 c(t) 人のワー

22:

カを受け入れるか，あるいは応募したワーカをすべて受け入れ23:

るまで行う．残りのワーカはすべて拒否される．また，タスク

pwi .pop(tj )

16:

24:
25:

end ifelse
if pt.index(wi+1 ) > pt.index(temlist[wi ]) thenpwi+1 .pop(t)elsetemlist.pop(wi , tj )temlist.append(wi+1 , tj )end ifの定員に達した時点でワーカの選好リストからそのタスクを削

26:

除する．

27: end while

end if

28: resultlist = temlist + conlist•

終了

29: return resultlist

どのワーカも断られなくなったときにアルゴリズムは終了する．各ワーカはアルゴリズムが終了したときに一時的に割り当

タスクに対してはボストンアルゴリズムの確定マッチを用いるてられたタスクとマッチする．

ため，確定マッチリストである conlist に格納する．19 行目かAlgorithm 3.3.1 に疑似コードを示す．アルゴリズムの入力は，

ら 25 行目はステップ k 以降に応募を受けたタスクが定員を超ワーカ集合 W ，タスク集合 T ，各ワーカは w と各タスク t

えた場合の処理を示している．選好を持たないタスクは定員にの選好 p(w) および p(t)，各ワーカの許容可能なタスク数 (定達した時点でワーカの選好リストから除外しているためここで員)c(w)，各タスク t の受け入れ可能ワーカ数（定員）c(t) であは仮マッチを扱う処理のみが行われる．タスクの選好リストをる．アルゴリズムの出力は，マッチしているワーカとタスクの参照し，定員を超えて応募したワーカの順位と前ステップで仮組の集合 resultlist である．

マッチリストに格納したペアのワーカの順位を比較し，もし前4 行目はアルゴリズムが終了する条件について示している．

者のワーカがより上位の希望であれば現在の仮マッチのペアを

cwi > 0 かつ len(pwi ) > 0，すなわち定員が 1 以上ありその削除し，新たにペアを仮マッチリストに格納する．もし仮マッワーカが希望している全員から断られていないようなワーカがチ中のワーカがより上位の希望であればステップ k で応募をし一人でも存在する限りアルゴリズムは終了しない.6 行目から 9

たワーカの選好リストからそのタスクを削除し，次のワーカの

行目は選好を持つタスクに対する処理を示している．ptj > 0

応募に移る．28 行目はアルゴリズムが終了条件を満たしたとである t，つまり選好を持つタスクに対して DA アルゴリズム

き，仮マッチリスト temlist に格納していたペアを確定マッチの仮マッチを用いるため，仮マッチリストである temlist に格

リスト conlist に追加し，最終的な割り当てとして出力してい納する．10 行目から 16 行目は選好を持たないタスクに対するることを示している．

処理を示している．ptj = 0 である t，つまり選好を持たない

集合とタスク集合の人数と選好を持たないタスクの数，各側の4 評価実験
本章では, 提案アルゴリズムに関する評価実験について述べる.

4. 1 概総定員数」の入力を行うと自動生成される「各ノードの選好リ
スト，定員」をシミュレーションのデータとして用いる．また，第 i 希望の相手とペアになった人の不満度を i と定義している
ため，選好を持たないタスクに対して不満度を計測することは要

まず，前章で述べた提案アルゴリズムを Python を用いて実装した．次に，多対多マッチングに必要なワーカ集合とタスクできない．そこで評価実験では，各側の頂点数および合計定員を同数に設定し，両側で合計不満度の期待値が同じになるよう設定を行った．

集合を用意した．各ワーカは完全リストである選好リストと１以下に評価実験の結果を示す．表 4.1 は提案手法とベースラ

以上の定員を持つ．各タスクは，選好を持つタスクと選好を持イン手法をそれぞれ適用させた場合の合計不満度とマッチング

たないタスクに分けられ，前者は完全リストである選好リスト

不成立数を各マッチングパターンに対して 20 通り，計 80 通りと 1 以上の定員を持ち，後者は選好リストを持たず 1 以上の定のマッチングを実行し出力されたものを示している．

員のみを持つ．各ワーカ，タスクが所有する選好リストはすべ

表1

提案手法

てランダムに順序が線形的に決定されるものを用いる．そして，

不満度

同×同

異×同

同×異

異×異

計

提案手法とベースライン手法でそれぞれマッチングを行い，不

ワーカ和

1297

1403

1462

1484

5646

満度を計測した．ベースライン手法はボストンアルゴリズムを

タスク和

1584

1606

1542

1589

6321

選好の有無にかかわらず全タスクに対し適用させたものとする．

全体和

2881

3009

3004

3073

11967

実験に用いたデータはすべて，（ワーカ数，タスク数（内選好を

不成立数

6

6

6

12

30

持たないタスク数），ワーカ側の合計定員，タスク側の合計定表2

ベースライン手法

不満度

同×同

異×同

同×異

異×異

計

員）＝（8，8（2），24，24）である．また，合計不満度を計測

ワーカ和

1183

1286

1265

1354

5088

する際に，選好を持たないタスクの不満度の期待値を ((ワーカ

タスク和

1793

1880

1826

1869

7368

集合に含まれるワーカの人数×そのタスクの定員)/2) とする．

全体和

2976

3166

3091

3223

12456

これは，提案手法およびベースライン手法がどちらの側の不満

不成立数

6

20

14

24

64

度により影響を及ぼしているかについて，比較を容易にするためワーカ，タスク間で頂点数の条件を同じにする処理を行う．

ベースライン手法と提案手法で同じデータセットを用いたた

また，混在マッチング問題における多対多マッチングを以下のめ，DA アルゴリズムにおける仮マッチを導入しているか否か

4 つの場合に分けて評価実験を行う．

によって生じた合計不満度の差であることを示している．提案（ 1 ） タスク集合，ワーカ集合がすべて同じ定員数を持つ手法のワーカ和とタスク和，ベースライン手法のワーカ和の 3（同×同）

項目において，不満度に大きく差が生じることはなかった．一

各ワーカの希望タスク数と各タスクの定員はすべて 3 とする．

方で，ベースライン手法のタスク和はマッチングパターンに（ 2 ） タスク集合は同じ定員数を持つが，各ワーカがランダ

よって，1793〜1880 と他の項目と比べて不満度が大きくなる

ムな定員数を持つ（異×同）ことが示されている．そのため，合計不満度では 80 通りの 8

各ワーカの希望タスク数は総定員が 24 となるように 1〜5 の対 8 のマッチングで 489 の不満度の差が生じた．また，マッチ

うちランダムで決定され，各タスクの定員はすべて 3 とする．

ング不成立数についても，ベースライン手法と比べ提案手法を（ 3 ） ワーカ集合は同じ定員数を持つが，各タスクがランダ用いることでその数が小さくなっていることが示されている．

ムな定員数を持つ（同×異）また，マッチング不成立になった場合，ベースライン手法と提各ワーカの希望タスク数はすべて 3 であり，各タスクの定員案手法のどちらにおいても，定員に余りを持つタスクを希望す

は総定員が 24 となるように 1〜5 のうちランダムで決定される．

るワーカが存在しなかった．すなわち，全マッチングで浪費的（ 4 ） 各タスク，ワーカともにランダムな定員数を持つ（異なマッチングは一度も発生しなかった．

×異）各ワーカの希望タスク数と各タスクの定員は総定員が 24 となるように 1〜5 のうちランダムで決定される．

4. 3 考察

前節で示した結果を見ると，多対多マッチングの全パターン

多対多マッチングにおいては，マッチングパターンによってにおいて提案アルゴリズムを用いることで不満度の小さいマッ

マッチング不成立の発生条件や確率が異なるため上記のようなチングを出力できたことが分かる．詳細に述べるなら，ワーカ分類を行う．これには，提案手法がどのマッチングパターンに側の合計不満度は提案手法よりもベースライン手法の方がわず

おいてより効果を発揮するのかを検証するという意図もある．

かに小さい．しかし，ベースライン手法ではタスク側の合計不満度が非常に大きく，提案手法の合計不満度に大きく差が生ま4. 2 評価実験の結果れるため，両側を含むマッチング全体では，提案手法の合計不前節で述べたシミュレーションデータを用い，提案手法と満度の方がより小さくなった．ベースライン手法ではワーカ側

ベースライン手法をそれぞれ実行し不満度を計測した．
「ワーカと比べ，タスク側の合計不満度が大きくなる傾向がみられる．

これは，ボストンアルゴリズムにおいて，応募を受けるタスク必要がある場合がある．ワーカとタスクを一対一に結びつける側の選好リストを参照するのが，同ステップ内で定員を超えるだけでなく，依存関係を考慮した複雑なマッチング問題に対し応募があった場合のみとなることが主な理由である．一方で，て機能するアルゴリズムを設計・実装することによってより現DA アルゴリズムでは，ステップに関係なく定員を超えるたび

実的な問題に対して効率的なタスクの割り当てを実現できるとに応募したワーカと仮マッチ中のワーカとを選好リストを参照

考えられる．

し比較する．そのため，DA アルゴリズムを組み合わせた提案

また，本研究では，ワーカと選好を持つタスクがお互いにフ手法では，タスク側の選好リストを参照する回数が多く，タス

ルサイズの選好リストを所有している場合には完全マッチング

ク集合にとってより希望するワーカが割り当てられやすくなっを出力できることを示しているが，部分的な選好リストが含またと考えられる．クラウドソーシングのタスク割り当てのようれる場合については対応できていない．実際のクラウドソーシ

な，選好の有無が混在する場合のマッチング手法は現時点で考ングのタスク割り当てにおいては，ワーカが対象のタスクに対案されていなかったが，選考を持つ財と持たない財について，

し厳密な選好リストを所有しているとは限らないため，選好リ

それぞれ別のアルゴリズムを適用することによって，不満度のストのサイズに制限がある状況で機能するアルゴリズムを設

小さいマッチングを求めることが可能となった．また，マッチ

計・実装することが望ましい．部分的選好下における学校選択

ング不成立数については，選好リストを持つタスクに対して問題を考察している関連研究があり，学生最適性を満たす割り仮マッチを導入することにより，ベースライン手法と比較して当てを出力するアルゴリズムの提案が行われている．これらをワーカが応募可能なタスク数が大きく減少しないため，全タス

混在マッチング問題へ応用した新たな手法を考案予定である．

クから拒否を受けてマッチが不成立となる最終ステップへ移行する前に定員までマッチしやすくなったと考えられる．また，提案手法はボストンアルゴリズムと DA アルゴリズムのマッチ
ング手法を組み合わせたものであるが，ボストンアルゴリズム，

DA アルゴリズムともに非浪費性の性質を満たしているため，提案手法も同様に非浪費性を満たしたマッチングとなると考えられる．

5 む す びインターネットの普及に伴って，これまで不可能だった様々な出会いが可能となり，人やモノ，サービスを結びつけるマッ
チングサービスが社会に浸透してきた．社会を取り巻く複雑なマッチングは従来のマッチング理論の研究では扱うことが困難なものも存在する．本論文では，複雑なマッチングの一つである，選好の有無が混在するマッチングを「混在するマッチング問題」として取り上げた．従来のマッチング問題の特徴から混在マッチングを定義した上で，非浪費性や一定条下の安定性を考慮した，多対多マッチングアルゴリズムを提案した．
評価実験では，主に配分マッチング問題において適用されているボストンアルゴリズムをベースライン手法に設定し，シミュレーションを通して得られたマッチング結果の合計不満度を比較することにより提案アルゴリズムの有用性の検証を行った．ベースライン手法では応募を受ける側の希望を満たす性質を持たないことが分かっていたが，提案手法を用いることにより，選好を持たない財が混在するマッチングに対しても仮マッ
チを導入することに成功した．仮マッチを導入することで，応募を受ける側の希望をある程度満たし，合計不満度の小さいマッチングの出力が可能であることを確認した．
今後の課題として，本研究ではクラウドソーシングのタスク
割り当てを想定しているが，個々のタスクを独立に扱っている．
しかし，実際のクラウドソーシングにおけるタスクには互いに依存関係がある．依存関係とはタスク同士が関連または連続している関係を指し，同一ワーカが連結した複数のタスクを行う

文

献[1] 宮崎修一. 安定マッチングの数理とアルゴリズム トラブルのない配属を求めて. 現代数学社, 2018, p. 4, 6, 12-13[2] 山口大河, 鈴木伸崇. マイクロタスク型クラウドソーシングにおけるワーカの希望タスク数を考慮したタスク割当て手法 .
DEIM Forum, 2021-01-24, 2021.
[3] 栗野盛光. ゲーム理論とマッチング. 日経文庫, 2019, p. 94-123,
150-193.
[4] ギオーム・ハーリンジャー. マーケットデザイン オークションとマッチングの理論・実践. 栗野盛光訳. 中央経済社, 2020, p.
199-214, 234-236, 255, 309-320.
[5] 秋葉俊祐, 鈴木伸崇. 安定性とインクルージョン性を考慮したマッチング手法 . DEIM Forum, 2022-3, 2022.
[6] 和田凌司, 八尋健太郎, 山口知晃, 東藤大樹, 横尾真. 部分的選好下における学校選択メカニズム. 人工知能学会全国大会論文集,2019.