JP7680972B2

JP7680972B2 - 公平性判定装置、公平性判定方法及び公平性判定プログラム

Info

Publication number: JP7680972B2
Application number: JP2022011198A
Authority: JP
Inventors: 徹中村; 隆将磯原
Original assignee: KDDI Corp
Current assignee: KDDI Corp
Priority date: 2022-01-27
Filing date: 2022-01-27
Publication date: 2025-05-21
Anticipated expiration: 2042-01-27
Also published as: JP2023109601A

Description

特許法第３０条第２項適用（１）令和４年１月１２日にオンライン配布が開始された２０２２年暗号と情報セキュリティシンポジウム論文集にて公開（２）令和４年１月１９日、２０２２年暗号と情報セキュリティシンポジウムにてオンライン発表

本発明は、マッチングの公平性を判定するための装置、方法及びプログラムに関する。

二部グラフにおけるマッチングの最適化問題は、労働者を仕事に割り当てる問題の数学モデルなどとして古くから研究されている。全体として満足度を最適化するマッチングは、重み付き最小完全二部グラフの最小フロー問題に帰着される。非特許文献１の安定結婚問題は、このマッチングに安定性という概念を採用した問題であり、安定なマッチングをＯ（ｎ^２）の計算量で見つけるアルゴリズムが提案されている。

安定結婚問題については、これまでに様々な拡張問題が考えられており、拡張問題の一分野として、公平性の議論がある。非特許文献１のアルゴリズムによって見つかる安定なマッチングは、男性又は女性の一方に最適なマッチングであり、また、全体としてのコストの最適化などは考慮されていなかった。
そこで、最小コスト安定マッチング、最小後悔安定マッチング（非特許文献２）、男女平等安定マッチング（非特許文献３）など、安定結婚問題を拡張した最適化問題が研究されてきた。これらの問題は、全体最適化の意味合いでの公平性を目指している。

ところが、このような全体最適化によって公平性を満足させるマッチング結果は、例えば、能力や評価の高い参加者にとっては、相対的に不利益をもたらすものである可能性があった。非特許文献４では、必ずしも安定とは限らない男女マッチングなどの問題において、能力主義的な公平性が定義され、また、どれくらい能力主義的公平であるかを定量的に評価できる指標が提案されている。

D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, Vol. 69, pp. 9-15, 1962. R. W. Irving, P. Leather, and D. Gusfield. An efficient algorithm for the "optimal" stable marriage. Journal of the ACM, Vol. 34, No. 3, pp. 532-543, 1987. A. Kato. Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics, Vol. 10, pp. 1-19, 1993. 中村徹，新田修也，磯原隆将．マッチングにおける個人主義的公平性とその侵害検知．コンピュータセキュリティシンポジウム2021(CSS2021)，Vol. 1D1-1，2021.

非特許文献４では、能力主義的な公平性の定義が提案されたが、能力主義的公平性を満たすマッチングであるかどうかを判定する効率の良い手法については言及されていなかった。このため、公平なマッチングを探索する際に、マッチング候補が得られる度に発生する公平性の判定に掛かる処理負荷が課題となっていた。

本発明は、マッチングにおける能力主義的な公平性を効率よく判定できる公平性判定装置、公平性判定方法及び公平性判定プログラムを提供することを目的とする。

本発明に係る公平性判定装置は、互いに素な二つの集合それぞれの各要素における他方の集合の選好順序、及び当該二つの集合の間でマッチングされたペアの情報から、前記二つの集合それぞれの各要素におけるペアの選好順位を取得する選好順位取得部と、前記二つの集合それぞれの各要素に対する選好順位を総合し、各要素の人気度を算出する人気度算出部と、前記二つの集合それぞれについて、各要素を前記人気度の昇順にソートし、当該人気度が同値の場合に同じ人気順位を付与する人気順位算出部と、前記二つの集合それぞれについて、前記人気順位毎に前記選好順位の最小値及び最大値を格納した判定テーブルを生成する判定テーブル生成部と、前記判定テーブルにおいて、前記人気順位がｉ番目までの前記選好順位の最大値が、前記人気順位がｉ＋ｋ＋１番目の前記選好順位の最小値＋ｌより大きいｉが存在しない場合に条件を満たし、存在する場合に条件を満たさないと判定するテーブル別判定部と、前記二つの集合の双方について前記条件を満たすと判定された場合に能力主義的公平であると判定し、いずれかで前記条件を満たさないと判定された場合に能力主義的公平でないと判定する公平性判定部と、を備える。

前記人気順位算出部は、各要素を前記人気度の昇順、及び前記ペアの選好順位の昇順にソートしてもよい。

前記判定テーブル生成部は、前記二つの集合それぞれについて、最大の人気順位における前記選好順位の最大値の格納を省略してもよい。

前記判定テーブル生成部は、前記二つの集合それぞれについて、最小の人気順位における前記選好順位の最小値の格納を省略してもよい。

本発明に係る公平性判定方法は、互いに素な二つの集合それぞれの各要素における他方の集合の選好順序、及び当該二つの集合の間でマッチングされたペアの情報から、前記二つの集合それぞれの各要素におけるペアの選好順位を取得する選好順位取得ステップと、前記二つの集合それぞれの各要素に対する選好順位を総合し、各要素の人気度を算出する人気度算出ステップと、前記二つの集合それぞれについて、各要素を前記人気度の昇順にソートし、当該人気度が同値の場合に同じ人気順位を付与する人気順位算出ステップと、前記二つの集合それぞれについて、前記人気順位毎に前記選好順位の最小値及び最大値を格納した判定テーブルを生成する判定テーブル生成ステップと、前記判定テーブルにおいて、前記人気順位がｉ番目までの前記選好順位の最大値が、前記人気順位がｉ＋ｋ＋１番目の前記選好順位の最小値＋ｌより大きいｉが存在しない場合に条件を満たし、存在する場合に条件を満たさないと判定するテーブル別判定ステップと、前記二つの集合の双方について前記条件を満たすと判定された場合に能力主義的公平であると判定し、いずれかで前記条件を満たさないと判定された場合に能力主義的公平でないと判定する公平性判定ステップと、をコンピュータが実行する。

本発明に係る公平性判定プログラムは、前記公平性判定装置としてコンピュータを機能させるためのものである。

本発明によれば、マッチングにおける能力主義的な公平性を効率よく判定できる。

実施形態における公平性判定装置の機能構成を示す図である。実施形態における選好順位取得部がペアの選好順位を求めるアルゴリズムを示す図である。実施形態における人気度算出部が各要素の人気度を求めるアルゴリズムを示す図である。実施形態における人気順位算出部が各要素の人気順位を求めるアルゴリズムを示す図である。実施形態における判定テーブル生成部が判定テーブルを生成するアルゴリズムを示す図である。実施形態におけるテーブル別判定部が判定テーブル毎の能力主義的公平性を判定するアルゴリズムを示す図である。実施形態における公平性判定部１６が緩和した（ｋ，ｌ）－能力主義的公平性を判定するアルゴリズムを示す図である。

以下、本発明の実施形態の一例について説明する。
本実施形態の公平性判定方法は、二部グラフにおいて得られたマッチングを入力として、このマッチングが能力主義的公平性を満たすか否かを短時間で判定するものである。ここでは、男女のマッチングを例に説明するが、本実施形態は、ジョブマッチングなどの類似のユースケースにも適用可能である。

マッチングのインスタンスＩは、２つの互いに素な要素数ｎの集合ＭとＷからなる。ここで、Ｍは男性集合、Ｗは女性集合である。各要素は、それぞれ他方の集合の要素に対し、選好順序（ｐｒｅｆｅｒｅｎｃｅｏｒｄｅｒ）と呼ばれる狭義全順序を持つ。
マッチングＸは、ＭとＷのペアである。すなわち、Ｘ⊆Ｍ×Ｗである。ここでは簡単のため、必ず１対１のペアをｎ組作る場合のみ考える。

マッチングＸにおいて、男性ｍと女性ｗとがペアである、すなわち（ｍ，ｗ）∈Ｘのとき、Ｘ（ｍ）＝ｗ，Ｘ（ｗ）＝ｍと表す。また、ｍの選好順序におけるｗの順位をＰ_ｍ（ｗ）と表し、これをｍにおけるｗの選好順位（ｐｒｅｆｅｒｅｎｃｅｒａｎｋ）と呼ぶ。同様に、ｗにおけるｍの選好順位をＰ_ｗ（ｍ）と表す。

本実施形態における個人主義的公平とは、能力又は評価がより高い者はより希望通りになるという考え方である。男女のマッチングにおいては、異性から選好順序上でより上位の（小さい）選好順位に指定される傾向にある人物を、評価の高い人物とみなす。

ここでは、全ての異性からの選好順序上の選好順位の総和により人物の定量的な評価を行うことで、同性他者との比較を行う。あるマッチングにおける任意の人物ａについて、その人物ａよりも評価の低い同性他者ｂとペアになっている相手の選好順序上の選好順位が、その人物ａとペアとなっている相手の選好順序上の選好順位よりも常に下位である（大きい）か等しいとき、このマッチングは個人主義的公平であるとする。

ｍ∈Ｍ及びｗ∈Ｗについて、Ｇ（ｍ）＝Σ^ｎ _ｉ＝１Ｐ_ｗｉ（ｍ）及びＧ（ｗ）＝Σ^ｎ _ｉ＝１Ｐ_ｍｉ（ｗ）を、それぞれｍ及びｗの人気度（ｐｏｐｕｌａｒｉｔｙ）とする。
また、Ｒ（ｍ）を、男性集合Ｍを人気度Ｇ（ｍ）の昇順にソートした場合のｍの順位とし、これをｍの人気順位（ｐｏｐｕｌａｒｒａｎｋ）と呼ぶ。同様に、Ｒ（ｗ）を、女性集合Ｗを人気度Ｇ（ｗ）の昇順にソートした場合のｗの人気順位とする。
なお、あるメンバｍ又はｗについて、人気度Ｇ及び人気順位Ｒが小さいほど、より異性から人気のあるメンバとみなす。
ここで、ある集合Ｈ及びある自然数ｐ∈Ｎについて、人気順位がｐよりも小さい（評価が高い）Ｈの部分集合をＨ_＜ｐとすると、個人主義的公平性は、次のように定義できる。

定義１：任意のｍ∈Ｍ及びｗ∈Ｗについて、
（１）任意のｍ′∈Ｍ_{＜Ｒ（ｍ）}について、
Ｐ_ｍ′（Ｘ（ｍ′））≦Ｐ_ｍ（Ｘ（ｍ））
かつ、
（２）任意のｗ′∈Ｗ_{＜Ｒ（ｗ）}について、
Ｐ_ｗ′（Ｘ（ｗ′））≦Ｐ_ｗ（Ｘ（ｗ））
を満たすとき、マッチングＸは、厳密な能力主義的公平である。

ただし、定義１の条件を満たす厳密な能力主義的公平なマッチングは、任意の選好順序において、必ずしも存在するとは限らない。また、厳密な能力主義的な公平性を満たすものの、全体最適性を大きく損なうマッチングしか存在しない場合もある。
そこで、次のように緩和した条件に基づく能力主義的公平性の定義を示す。
・自分より人気順位が下位ｋ番目以内の同性他者が自分よりも選好順位が小さい異性とマッチングするのを許容する。
・ある同性の２名について、それぞれがマッチングした相手の選好順位の差がｌ以内であれば差がないとみなし許容する。

定義２：任意のｍ∈Ｍ及びｗ∈Ｗについて、
（１）任意のｍ′∈Ｍ_{＜Ｒ（ｍ）－ｋ}について、
Ｐ_ｍ′（Ｘ（ｍ′））≦Ｐ_ｍ（Ｘ（ｍ））＋ｌ
かつ、
（２）任意のｗ′∈Ｗ_{＜Ｒ（ｗ）－ｋ}について、
Ｐ_ｗ′（Ｘ（ｗ′））≦Ｐ_ｗ（Ｘ（ｗ））＋ｌ
を満たすとき、このマッチングＸは、（ｋ，ｌ）－能力主義的公平である。

次に、緩和した能力主義的公平性を判定するための装置の機能構成と、処理アルゴリズムを示す。
なお、厳密な能力主義的公平性についても、緩和した（ｋ，ｌ）－能力主義的公平性のｋ＝０，ｌ＝０となる特殊ケースであるから、本アルゴリズムを用いて判定できる。

ここで、男性集合をＭ＝｛ｍ_１，ｍ_２，…，ｍ_ｎ｝とし、女性集合をＷ＝｛ｗ_１，ｗ_２，…，ｗ_ｎ｝とする。Ｍ，Ｗを配列として考え、これらの配列の要素ａは、属性としてａ．ｐｒｅｆ＿ｒａｎｋ，ａ．ｐｏｐｕｌａｒｉｔｙ，ａ．ｐｏｐ＿ｒａｎｋを持つ構造体とする。
ａ．ｐｒｅｆ＿ｒａｎｋは、ａのペアのａにおける選好順位、すなわちＰ_ａ（Ｘ（ａ））である。また、ａ．ｐｏｐｕｌａｒｉｔｙ及びａ．ｐｏｐ＿ｒａｎｋは、それぞれａの人気度及び人気順位である。

図１は、本実施形態における公平性判定装置１の機能構成を示す図である。
公平性判定装置１は、サーバ装置又はパーソナルコンピュータなどの情報処理装置（コンピュータ）であり、制御部１０及び記憶部２０の他、各種データの入出力デバイス及び通信デバイスなどを備える。

制御部１０は、公平性判定装置１の全体を制御する部分であり、記憶部２０に記憶された各種プログラムを適宜読み出して実行することにより、本実施形態における各機能を実現する。制御部１０は、ＣＰＵであってよい。

記憶部２０は、ハードウェア群を公平性判定装置１として機能させるための公平性判定プログラムを含む各種プログラム、及び各種データなどの記憶領域であり、ＲＯＭ、ＲＡＭ、フラッシュメモリ又はハードディスクドライブ（ＨＤＤ）などであってよい。

制御部１０は、選好順位取得部１１と、人気度算出部１２と、人気順位算出部１３と、判定テーブル生成部１４と、テーブル別判定部１５と、公平性判定部１６とを備える。

選好順位取得部１１は、互いに素な二つの集合Ｍ及びＷそれぞれの各要素における他方の集合の選好順序、及びこれら二つの集合の間でマッチングされたペアの情報から、二つの集合それぞれの各要素におけるペアの選好順位を取得する。

図２は、本実施形態における選好順位取得部１１がペアの選好順位を求めるアルゴリズムＰｒｅｆｅｒｅｎｃｅＲａｎｋを示す図である。
入力は、マッチングのインスタンスＩ、及びマッチングＸである（ステップ１）。なお、Ｉは、長さｎの選好順位のリストが要素である、長さｎ（＝｜Ｍ｜＝｜Ｗ｜）の二つの配列である。

選好順位取得部１１は、要素数ｎ回のループ（ステップ２）により、配列Ｍにおけるｉ番目の要素Ｍ［ｉ］の属性ｐｒｅｆ＿ｒａｎｋに対して、ペアの相手であるＸ（Ｍ［ｉ］）の選好順位Ｐ_Ｍ［ｉ］（Ｘ（Ｍ［ｉ］））を格納する（ステップ３）。
同様に、選好順位取得部１１は、配列Ｗにおけるｉ番目の要素Ｗ［ｉ］の属性ｐｒｅｆ＿ｒａｎｋに対して、ペアの相手であるＸ（Ｗ［ｉ］）の選好順位Ｐ_Ｗ［ｉ］（Ｘ（Ｗ［ｉ］））を格納する（ステップ４）。

選好順位取得部１１は、各要素におけるペアの選好順位が属性ｐｒｅｆ＿ｒａｎｋに格納された配列Ｍ及びＷを出力する（ステップ６）。

人気度算出部１２は、二つの集合Ｍ及びＷそれぞれの各要素に対する選好順位を総合し、各要素の人気度を算出する。

図３は、本実施形態における人気度算出部１２が各要素の人気度を求めるアルゴリズムＰｏｐｕｌａｒｉｔｙを示す図である。
入力は、マッチングのインスタンスＩ、及び二つの配列Ｍ，Ｗである（ステップ１）。

人気度算出部１２は、要素数ｎ回の二重ループ（ステップ２，３）により、配列Ｍにおけるｉ番目の要素Ｍ［ｉ］の属性ｐｏｐｕｌａｒｉｔｙに対して、配列Ｗの各要素におけるＭ［ｉ］の選好順位を全要素について加算する（ステップ４）。
同様に、人気度算出部１２は、配列Ｗにおけるｉ番目の要素Ｗ［ｉ］の属性ｐｏｐｕｌａｒｉｔｙに対して、配列Ｍの各要素におけるＷ［ｉ］の選好順位を全要素について加算する（ステップ５）。

人気度算出部１２は、各要素の人気度が属性ｐｏｐｕｌａｒｉｔｙに格納された配列Ｍ及びＷを出力する（ステップ８）。

人気順位算出部１３は、二つの集合それぞれについて、各要素を人気度の昇順にソートして人気順位を付与する。このとき、人気順位算出部１３は、人気度が同値の要素に対しては、同じ人気順位を付与する。
また、人気順位算出部１３は、各要素を人気度の昇順、及びペアの選好順位の昇順にソートすることにより、後段の処理を効率化してもよい。

図４は、本実施形態における人気順位算出部１３が各要素の人気順位を求めるアルゴリズムＰｏｐｕｌａｒＲａｎｋを示す図である。
入力は、選好順位及び人気度が各要素の属性として付与された配列であり、Ｍ及びＷが順に入力される。

まず、人気順位算出部１３は、関数Ｓｏｒｔ（Ａ）により、入力された配列Ａを人気度及び選好順位の昇順にソートした配列Ａ’を得る（ステップ２）。
なお、Ｓｏｒｔ（Ａ）は、配列Ａの入力に対して、属性ｐｏｐｕｌａｒｉｔｙの値で昇順にソートし、同値の場合には属性ｐｒｅｆ＿ｒａｎｋでさらに昇順にソートした配列Ａ’を出力する関数である。

次に、人気順位算出部１３は、変数ｐｒｅ＿ｓｃｏｒｅ及びｎｅｘｔ＿ｒａｎｋを、それぞれ０に初期化した後（ステップ３，４）、要素数ｎ回のループ処理を行う（ステップ５）。

ループの中で、人気順位算出部１３は、配列Ａ’のｉ番目の要素の人気度（ｓｃｏｒｅ＝Ａ’［ｉ］．ｐｏｐｕｌａｒｉｔｙ）がｐｒｅ＿ｓｃｏｒｅと異なる（大きい）場合に、ｎｅｘｔ＿ｒａｎｋをｉに更新し（ステップ８）、ｐｒｅ＿ｓｃｏｒｅをｓｃｏｒｅに更新する（ステップ９）。そして、人気順位算出部１３は、人気順位（Ａ’［ｉ］．ｐｏｐ＿ｒａｎｋ）に、ｎｅｘｔ＿ｒａｎｋを格納する（ステップ１１）。
すなわち、ｉが増加しても人気度が同値であった場合（ステップ７でＦＡＬＳＥ）は、ｎｅｘｔ＿ｒａｎｋは更新されず、同じ人気順位が付与される。一方、人気度が増加した場合（ステップ７でＴＲＵＥ）は、加算された人気順位（＝ｉ）が付与される。

人気順位算出部１３は、各要素の人気順位が属性ｐｏｐ＿ｒａｎｋに格納された配列Ａ’を出力する（ステップ１３）。

判定テーブル生成部１４は、二つの集合それぞれについて、人気順位毎に選好順位の最小値及び最大値を格納した判定テーブルを生成する。

図５は、本実施形態における判定テーブル生成部１４が判定テーブルを生成するアルゴリズムＭａｋｅＴａｂｌｅを示す図である。
入力は、各要素の属性に選好順位、人気度、人気順位が付与された配列であり、人気順位算出部１３によりソートされた配列Ｍ’及びＷ’が順に入力される。

まず、判定テーブル生成部１４は、要素数ｎ回のループ処理（ステップ２）により、判定テーブルに格納される最小値（Ｔａｂｌｅ［ｉ］．ｍｉｎ）及び最大値（Ｔａｂｌｅ［ｉ］．ｍａｘ）を０に初期化する（ステップ３，４）。
続いて、変数ｐｒｅ＿ｐｏｐ＿ｒａｎｋ，ｐｒｅ＿ｐｒｅｆ＿ｒａｎｋ，ｐｒｅ＿ｉｎｄｅｘを、それぞれ０，０，１に初期化する（ステップ６～８）。

次に、判定テーブル生成部１４は、要素数ｎ回のループ処理（ステップ９）の中で、入力された配列Ａのｉ番目の要素の人気順位（Ａ［ｉ］．ｐｏｐ＿ｒａｎｋ）がｐｒｅ＿ｐｏｐ＿ｒａｎｋより変化した（大きくなった）場合に（ステップ１０）、判定テーブルにおけるＴａｂｌｅ［ｉ］．ｍｉｎ（ｉ番目の人気順位における選好順位の最小値）にＡ［ｉ］．ｐｒｅｆ＿ｒａｎｋを、Ｔａｂｌｅ［ｐｒｅ＿ｉｎｄｅｘ］．ｍａｘ（一つ前の人気順位における選好順位の最大値）にｐｒｅ＿ｐｒｅｆ＿ｒａｎｋを、それぞれ格納する（ステップ１１，１２）。
また、判定テーブル生成部１４は、判定テーブルのｉ番目の要素（ｍｉｎ）を更新したので、ｐｒｅ＿ｉｎｄｅｘをｉに更新する（ステップ１３）。

一方、配列Ａのｉ番目の要素の人気順位（Ａ［ｉ］．ｐｏｐ＿ｒａｎｋ）がｐｒｅ＿ｐｏｐ＿ｒａｎｋと変わらない場合（ステップ１０）、判定テーブル生成部１４は、判定テーブルへの値の格納を保留し、ｐｒｅ＿ｐｏｐ＿ｒａｎｋをＡ［ｉ］．ｐｏｐ＿ｒａｎｋに、ｐｒｅ＿ｐｒｅｆ＿ｒａｎｋをＡ［ｉ］．ｐｒｅｆ＿ｒａｎｋに、それぞれ更新する（ステップ１５，１６）。

判定テーブル生成部１４は、インデックスが人気順位であり、属性として各人気順位における選好順位の範囲（最小の選好順位ｍｉｎ及び最大の選好順位ｍａｘ）を持つ判定テーブルＴａｂｌｅを出力する（ステップ１８）。

なお、最大の人気順位における選好順位の最大値Ａ［ｎ］．ｍａｘ、及び最小の人気順位における選好順位の最小値Ａ［１］．ｍｉｎは、後段の処理で参照されないため、判定テーブル生成部１４は、これらの値の格納を省略してもよい。

テーブル別判定部１５は、生成された判定テーブルにおいて、人気順位がｉ番目までの選好順位の最大値が、人気順位がｉ＋ｋ＋１番目の選好順位の最小値＋ｌより大きいｉが存在しない場合に能力主義的公平性の条件を満たし、存在する場合に条件を満たさないと判定する。

図６は、本実施形態におけるテーブル別判定部１５が判定テーブル毎の能力主義的公平性を判定するアルゴリズムＪｕｄｇｅを示す図である。
入力は、判定テーブルＴａｂｌｅと、公平性を緩和した条件に関する定数ｋ及びｌである。

まず、テーブル別判定部１５は、変数ｐｒｅｆｅｒ＿ｍａｘを０に初期化する（ステップ２）。

次に、テーブル別判定部１５は、インデックスｉを１からｎ－ｋ－１まで変化させるループ処理（ステップ３）の中で、ｐｒｅｆｅｒ＿ｍａｘとＴａｂｌｅ［ｉ］．ｍａｘとを比較する（ステップ４）。テーブル別判定部１５は、Ｔａｂｌｅ［ｉ］．ｍａｘの方が大きい場合に、ｐｒｅｆｅｒ＿ｍａｘを更新する（ステップ５）。これにより、ｐｒｅｆｅｒ＿ｍａｘには、ｉ番目までの人気順位における選好順位の最大値が格納される。

また、テーブル別判定部１５は、ループ処理（ステップ３）の中で、ｐｒｅｆｅｒ＿ｍａｘと、ｉ＋ｋ＋１番目の人気順位における選好順位の最小値（Ｔａｂｌｅ［ｉ＋ｋ＋１］）とを比較する。そして、Ｔａｂｌｅ［ｉ＋ｋ＋１］が０でなく、かつ、ｐｒｅｆｅｒ＿ｍａｘとの差がｌより大きい場合、能力主義的公平性の条件を満たさないと判定される（ステップ７～９）。一方、全てのｉでＴａｂｌｅ［ｉ＋ｋ＋１］が０か、又はｐｒｅｆｅｒ＿ｍａｘとの差がｌ以下の場合、能力主義的公平性の条件を満たすと判定される（ステップ１１）。

公平性判定部１６は、二つの集合Ｍ及びＷの双方から生成された判定テーブルについて、テーブル別判定部１５により条件を満たすと判定された場合に能力主義的公平であると判定し、いずれかで条件を満たさないと判定された場合に能力主義的公平でないと判定する。

図７は、本実施形態における公平性判定部１６が緩和した（ｋ，ｌ）－能力主義的公平性を判定するアルゴリズムＦａｉｒＪｕｄｇｅを示す図である。
入力は、マッチングのインスタンスＩ、マッチングＸ、及び緩和した条件に関する定数ｋ及びｌである。

まず、公平性判定部１６は、選好順位取得部１１（アルゴリズムＰｒｅｆｅｒｅｎｃｅＲａｎｋ）を用いて、配列Ｍ及びＷに選好順位を格納する（ステップ２）。
続いて、公平性判定部１６は、人気度算出部１２（アルゴリズムＰｏｐｕｌａｒｉｔｙ）を用いて、さらに人気度を格納した配列Ｍ’及びＷ’を得る（ステップ３）。
さらに、公平性判定部１６は、人気順位算出部１３（アルゴリズムＰｏｐｕｌａｒＲａｎｋ）を用いて、人気順位を格納した配列Ｍ”及びＷ”を得る（ステップ４，５）。

次に、公平性判定部１６は、判定テーブル生成部１４（アルゴリズムＭａｋｅＴａｂｌｅ）を用いて、配列Ｍ”及びＷ”のそれぞれから、判定テーブルＴａｂｌｅ＿Ｍ及びＴａｂｌｅ＿Ｗを得る（ステップ６，７）。
続いて、公平性判定部１６は、テーブル別判定部１５（アルゴリズムＪｕｄｇｅ）を用いて、判定テーブルＴａｂｌｅ＿Ｍ及びＴａｂｌｅ＿Ｗのそれぞれについて、公平性の条件を満たすか否かを得る（ステップ８，９）。
そして、公平性判定部１６は、判定テーブルのいずれも公平性の条件を満たす場合に（ステップ１０）、全体として能力主義的公平性を満たすと判定し（ステップ１１）、少なくともいずれかで条件を満たさない場合に、能力主義的公平性を満たさないと判定する（ステップ１３）。

本実施形態によれば、公平性判定装置１は、二つの集合それぞれについて、人気順位毎に選好順位の最小値及び最大値を格納した判定テーブルを生成し、この判定テーブルにおいて、人気順位がｉ番目までの選好順位の最大値が、人気順位がｉ＋ｋ＋１番目の選好順位の最小値＋ｌより大きいｉが存在しない場合に条件を満たし、存在する場合に条件を満たさないと判定する。これにより、公平性判定装置１は、二つの集合の双方について条件を満たすと判定された場合に能力主義的公平であると判定し、いずれかで条件を満たさないと判定された場合に能力主義的公平でないと判定する。
これにより、公平性判定装置１は、判定テーブルを利用したアルゴリズムＪｕｄｇｅにおいて、１回のみのループ処理により、能力主義的公平性を判定できる。したがって、公平性の定義に単純に従った判定方法では集合の要素毎に他の要素との比較をするために、二重ループを伴うＯ（ｎ^２）の計算量が見込まれるのに比べて、本実施形態ではＯ（ｎ）の計算量に抑えられる。この結果、能力主義的公平性を満たしたマッチングの探索に掛かる処理負荷が大きく低減される。

また、公平性判定装置１は、集合の各要素を人気度の昇順、及びペアの選好順位の昇順にソートしておくことにより、アルゴリズムＭａｋｅＴａｂｌｅ、及びアルゴリズムＪｕｄｇｅが効率化されるので、さらに処理負荷を低減できる。

さらに、公平性判定装置１は、判定テーブルのうち、アルゴリズムＪｕｄｇｅで使用しないデータの格納を省略して効率化することができる。具体的には、二つの集合それぞれについて、最大の人気順位における選好順位の最大値、及び最小の人気順位における選好順位の最小値、あるいはそのいずれかの格納を省略してもよい。

なお、これにより、例えばインターネット上で能力主義的公平なマッチングサービスを効率的に提供できることから、国連が主導する持続可能な開発目標（ＳＤＧｓ）の目標９「レジリエントなインフラを整備し、持続可能な産業化を推進するとともに、イノベーションの拡大を図る」に貢献することが可能となる。

以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、前述した実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、実施形態に記載されたものに限定されるものではない。

公平性判定装置１による公平性判定方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ－ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。

１公平性判定装置
１０制御部
１１選好順位取得部
１２人気度算出部
１３人気順位算出部
１４判定テーブル生成部
１５テーブル別判定部
１６公平性判定部
２０記憶部

Claims

互いに素な二つの集合それぞれの各要素における他方の集合の選好順序、及び当該二つの集合の間でマッチングされたペアの情報から、前記二つの集合それぞれの各要素におけるペアの選好順位を取得する選好順位取得部と、
前記二つの集合それぞれの各要素に対する選好順位を総合し、各要素の人気度を算出する人気度算出部と、
前記二つの集合それぞれについて、各要素を前記人気度の昇順にソートし、当該人気度が同値の場合に同じ人気順位を付与する人気順位算出部と、
前記二つの集合それぞれについて、前記人気順位毎に前記選好順位の最小値及び最大値を格納した判定テーブルを生成する判定テーブル生成部と、
前記判定テーブルにおいて、前記人気順位がｉ番目までの前記選好順位の最大値が、前記人気順位がｉ＋ｋ＋１番目の前記選好順位の最小値＋ｌより大きいｉが存在しない場合に条件を満たし、存在する場合に条件を満たさないと判定するテーブル別判定部と、
前記二つの集合の双方について前記条件を満たすと判定された場合に能力主義的公平であると判定し、いずれかで前記条件を満たさないと判定された場合に能力主義的公平でないと判定する公平性判定部と、を備える公平性判定装置。
前記人気順位算出部は、各要素を前記人気度の昇順にソートする際に、当該人気度が同値の場合に前記ペアの選好順位の昇順にソートする請求項１に記載の公平性判定装置。
前記判定テーブル生成部は、前記二つの集合それぞれについて、最大の人気順位における前記選好順位の最大値の格納を省略する請求項１又は請求項２に記載の公平性判定装置。
前記判定テーブル生成部は、前記二つの集合それぞれについて、最小の人気順位における前記選好順位の最小値の格納を省略する請求項１から請求項３のいずれかに記載の公平性判定装置。
互いに素な二つの集合それぞれの各要素における他方の集合の選好順序、及び当該二つの集合の間でマッチングされたペアの情報から、前記二つの集合それぞれの各要素におけるペアの選好順位を取得する選好順位取得ステップと、
前記二つの集合それぞれの各要素に対する選好順位を総合し、各要素の人気度を算出する人気度算出ステップと、
前記二つの集合それぞれについて、各要素を前記人気度の昇順にソートし、当該人気度が同値の場合に同じ人気順位を付与する人気順位算出ステップと、
前記二つの集合それぞれについて、前記人気順位毎に前記選好順位の最小値及び最大値を格納した判定テーブルを生成する判定テーブル生成ステップと、
前記判定テーブルにおいて、前記人気順位がｉ番目までの前記選好順位の最大値が、前記人気順位がｉ＋ｋ＋１番目の前記選好順位の最小値＋ｌより大きいｉが存在しない場合に条件を満たし、存在する場合に条件を満たさないと判定するテーブル別判定ステップと、
前記二つの集合の双方について前記条件を満たすと判定された場合に能力主義的公平であると判定し、いずれかで前記条件を満たさないと判定された場合に能力主義的公平でないと判定する公平性判定ステップと、をコンピュータが実行する公平性判定方法。
請求項１から請求項４のいずれかに記載の公平性判定装置としてコンピュータを機能させるための公平性判定プログラム。