(57)【要約】      （修正有）【課題】適切な応募対象への割り当てを求めるマッチングプログラムを提供する。【解決手段】マッチングプログラムは、それぞれに優先順位が付された複数の応募者および複数の応募対象のマッチングについて、部分ゲーム完全均衡を求めてマッチングを行う処理と、生成する処理と、繰り返す処理とをコンピュータに実行させる。生成する処理は、複数の応募対象それぞれについての応募の集合を示す応募情報を生成する。繰り返す処理は、集合の中から、複数の応募者に対する優先順位に従い、複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定し、応募確定に伴い失敗が確定する他の応募者の応募を特定し、他の応募者の失敗確定に対応した応募をキャンセルさせ、キャンセルにより成功が確定する応募を特定し、成功確定した応募者の、当該成功確定した応募より利得が低い応募をキャンセルさせる処理を繰り返す。【選択図】図１
2019067158.tif 000002
【特許請求の範囲】
【請求項１】
それぞれに優先順位が付された複数の応募者と、前記複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象とのマッチングをコンピュータに実行させるマッチングプログラムであって、
前記マッチングに対応した展開型ゲームであって、前記複数の応募者それぞれの選好に対応した利得を有する独立した複数のプレイヤーに関し、前記複数の応募者それぞれの優先順位をプレイの順番と対応づけられ、かつ、前記複数のプレイヤーそれぞれは前記複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求め、
前記部分ゲーム完全均衡の結果に基づくマッチングを行い、
特定の他の応募者と組になった形での利得を持つカップリング応募者それぞれ、および、個別の応募者に対応する応募者それぞれについて、利得が設定された各応募対象へ応募させ、前記複数の応募対象それぞれについての応募の集合を示す応募情報を生成し、
生成された前記応募情報の集合の中から、前記複数の応募者に対する前記優先順位に従い、前記複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定する第１処理と、
前記応募確定に伴い失敗が確定する他の応募者の応募を特定する第２処理と、
前記他の応募者の失敗確定に対応した応募をキャンセルさせるとともに、当該キャンセルにより成功が確定する応募を特定する第３処理と、
前記成功確定した応募者の、当該成功確定した応募より前記利得が低い応募をキャンセルさせる第４処理との前記第１処理から第４処理を前記集合の中から確定する応募が無くなるまで繰り返す、
処理をコンピュータに実行させることを特徴とするマッチングプログラム。
【請求項２】
前記生成して繰り返す処理は、前記成功確定から失敗確定となる応募の応募者について、利得が設定された各応募対象へ応募させて別の応募を行う、
ことを特徴とする請求項１に記載のマッチングプログラム。
【請求項３】
前記生成して繰り返す処理は、前記部分ゲーム完全均衡を求める処理に先立って、または、前記部分ゲーム完全均衡を求める処理の途中で行う、
ことを特徴とする請求項１または２に記載のマッチングプログラム。
【請求項４】
前記特定の他の応募者と組になった形での利得を持つカップリング応募者とは、互いにきょうだい関係を有する応募者である、
ことを特徴とする請求項１乃至３のいずれか一項に記載のマッチングプログラム。
【請求項５】
前記マッチングは、優先順位が付された複数の子どもと、当該複数の子どもそれぞれに対する優先順がそれぞれ付された複数の保育所とのマッチングである、
ことを特徴とする請求項１乃至４のいずれか一項に記載のマッチングプログラム。
【請求項６】
それぞれに優先順位が付された複数の応募者と、前記複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象とのマッチングをコンピュータが実行するマッチング方法であって、
前記マッチングに対応した展開型ゲームであって、前記複数の応募者それぞれの選好に対応した利得を有する独立した複数のプレイヤーに関し、前記複数の応募者それぞれの優先順位をプレイの順番と対応づけられ、かつ、前記複数のプレイヤーそれぞれは前記複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求め、
前記部分ゲーム完全均衡の結果に基づくマッチングを行い、
特定の他の応募者と組になった形での利得を持つカップリング応募者それぞれ、および、個別の応募者に対応する応募者それぞれについて、利得が設定された各応募対象へ応募させ、前記複数の応募対象それぞれについての応募の集合を示す応募情報を生成し、
生成された前記応募情報の集合の中から、前記複数の応募者に対する前記優先順位に従い、前記複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定する第１処理と、
前記応募確定に伴い失敗が確定する他の応募者の応募を特定する第２処理と、
前記他の応募者の失敗確定に対応した応募をキャンセルさせるとともに、当該キャンセルにより成功が確定する応募を特定する第３処理と、
前記成功確定した応募者の、当該成功確定した応募より前記利得が低い応募をキャンセルさせる第４処理との前記第１処理から第４処理を前記集合の中から確定する応募が無くなるまで繰り返す、
処理をコンピュータが実行することを特徴とするマッチング方法。
【請求項７】
それぞれに優先順位が付された複数の応募者と、前記複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象とのマッチングを実行するマッチング装置であって、
前記マッチングに対応した展開型ゲームであって、前記複数の応募者それぞれの選好に対応した利得を有する独立した複数のプレイヤーに関し、前記複数の応募者それぞれの優先順位をプレイの順番と対応づけられ、かつ、前記複数のプレイヤーそれぞれは前記複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求め、前記部分ゲーム完全均衡の結果に基づくマッチングを行うマッチング処理部と、
特定の他の応募者と組になった形での利得を持つカップリング応募者それぞれ、および、個別の応募者に対応する応募者それぞれについて、利得が設定された各応募対象へ応募させ、前記複数の応募対象それぞれについての応募の集合を示す応募情報を生成し、生成された前記応募情報の集合の中から、前記複数の応募者に対する前記優先順位に従い、前記複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定する第１処理と、前記応募確定に伴い失敗が確定する他の応募者の応募を特定する第２処理と、前記他の応募者の失敗確定に対応した応募をキャンセルさせるとともに、当該キャンセルにより成功が確定する応募を特定する第３処理と、前記成功確定した応募者の、当該成功確定した応募より前記利得が低い応募をキャンセルさせる第４処理との前記第１処理から第４処理を前記集合の中から確定する応募が無くなるまで繰り返す応募状況更新部と、
を有することを特徴とするマッチング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、マッチングプログラム、マッチング方法およびマッチング装置に関する。
【背景技術】
【０００２】
従来、多くの応募者（例えば保育を希望する保護者の子ども）を応募対象（例えば保育所などの保育機関）へ割り当てるマッチング処理では、Ｄｅｆｅｒｒｅｄ−Ａｃｃｅｐｔａｎｃｅ（Ｇａｌｅ−Ｓｈａｐｌｅｙ）が知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Gale, David, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American Mathematical Monthly 69.1 (1962): 9-15.
【非特許文献２】Roth, Alvin E., and Elliott Peranson. "The redesign of the matching market for American physicians: Some engineering aspects of economic design." No. w6963. National bureau of economic research, 1999.
【非特許文献３】Kojima, Fuhito, Parag A. Pathak, and Alvin E. Roth. "Matching with couples: Stability and incentives in large markets." The Quarterly Journal of Economics 128.4 (2013): 1585-1632.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の従来技術では、保育所などの応募対象側で応募者の選好順序が決まっている場合、その選好順序を考慮した適切な応募対象への割り当てを行うことが困難であるという問題がある。
【０００５】
１つの側面では、適切な応募対象への割り当てを求めることを可能とするマッチングプログラム、マッチング方法およびマッチング装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
第１の案では、マッチングプログラムは、それぞれに優先順位が付された複数の応募者と、複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象とのマッチングをコンピュータに実行させる。また、マッチングプログラムは、部分ゲーム完全均衡を求める処理と、マッチングを行う処理と、生成する処理と、繰り返す処理とをコンピュータに実行させる。求める処理は、マッチングに対応した展開型ゲームであって、複数の応募者それぞれの選好に対応した利得を有する独立した複数のプレイヤーに関し、複数の応募者それぞれの優先順位をプレイの順番と対応づけられ、かつ、複数のプレイヤーそれぞれは複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求める。マッチングを行う処理は、部分ゲーム完全均衡の結果に基づくマッチングを行う。生成する処理は、特定の他の応募者と組になった形での利得を持つカップリング応募者それぞれ、および、個別の応募者に対応する応募者それぞれについて、利得が設定された各応募対象へ応募させ、複数の応募対象それぞれについての応募の集合を示す応募情報を生成する。繰り返す処理は、第１処理から第４処理を集合の中から確定する応募が無くなるまで繰り返す。第１処理は、生成された応募情報の集合の中から、複数の応募者に対する優先順位に従い、複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定する。第２処理は、応募確定に伴い失敗が確定する他の応募者の応募を特定する。第３処理は、他の応募者の失敗確定に対応した応募をキャンセルさせるとともに、当該キャンセルにより成功が確定する応募を特定する。第４処理は、成功確定した応募者の、当該成功確定した応募より利得が低い応募をキャンセルさせる。
【発明の効果】
【０００７】
本発明の１実施態様によれば、適切な応募対象への割り当てを求めることができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、実施形態にかかるマッチング装置の機能構成例を示すブロック図である。
【図２】図２は、応募対象情報と、応募者情報とを説明する説明図である。
【図３】図３は、結果データを説明する説明図である。
【図４】図４は、展開型ゲームを説明する説明図である。
【図５】図５は、部分ゲーム完全均衡を説明する説明図である。
【図６】図６は、部分ゲーム完全均衡を説明する説明図である。
【図７】図７は、部分ゲーム完全均衡を説明する説明図である。
【図８】図８は、部分ゲーム完全均衡を説明する説明図である。
【図９】図９は、部分ゲーム完全均衡を説明する説明図である。
【図１０】図１０は、バックトラックを説明する説明図である。
【図１１】図１１は、応募状況更新の概要を説明する説明図である。
【図１２】図１２は、互いの選好順序が論理的に独立であるケースを説明する説明図である。
【図１３】図１３は、実施形態にかかるマッチング装置の動作例を示すフローチャートである。
【図１４】図１４は、応募状況更新処理の一例を示すフローチャートである。
【図１５】図１５は、応募最大化処理の一例を示すフローチャートである。
【図１６−１】図１６−１は、応募状況の具体例を説明する説明図である。
【図１６−２】図１６−２は、応募状況の具体例を説明する説明図である。
【図１６−３】図１６−３は、応募状況の具体例を説明する説明図である。
【図１６−４】図１６−４は、応募状況の具体例を説明する説明図である。
【図１６−５】図１６−５は、応募状況の具体例を説明する説明図である。
【図１６−６】図１６−６は、応募状況の具体例を説明する説明図である。
【図１６−７】図１６−７は、応募状況の具体例を説明する説明図である。
【図１７−１】図１７−１は、ノードの探索を説明する説明図である。
【図１７−２】図１７−２は、ノードの探索を説明する説明図である。
【図１８−１】図１８−１は、応募状況の具体例を説明する説明図である。
【図１８−２】図１８−２は、応募状況の具体例を説明する説明図である。
【図１８−３】図１８−３は、応募状況の具体例を説明する説明図である。
【図１８−４】図１８−４は、応募状況の具体例を説明する説明図である。
【図１９−１】図１９−１は、ノードの探索を説明する説明図である。
【図１９−２】図１９−２は、ノードの探索を説明する説明図である。
【図２０−１】図２０−１は、応募状況の具体例を説明する説明図である。
【図２０−２】図２０−２は、応募状況の具体例を説明する説明図である。
【図２０−３】図２０−３は、応募状況の具体例を説明する説明図である。
【図２０−４】図２０−４は、応募状況の具体例を説明する説明図である。
【図２０−５】図２０−５は、応募状況の具体例を説明する説明図である。
【図２１】図２１は、部分ゲーム完全均衡の探索結果を説明する説明図である。
【図２２】図２２は、実施形態にかかるマッチング装置のハードウエア構成例を説明する説明図である。
【発明を実施するための形態】
【０００９】
以下、図面を参照して、実施形態にかかるマッチングプログラム、マッチング方法およびマッチング装置を説明する。実施形態において同一の機能を有する構成には同一の符号を付し、重複する説明は省略する。なお、以下の実施形態で説明するマッチングプログラム、マッチング方法およびマッチング装置は、一例を示すに過ぎず、実施形態を限定するものではない。また、以下の各実施形態は、矛盾しない範囲内で適宜組みあわせてもよい。
【００１０】
図１は、実施形態にかかるマッチング装置の機能構成例を示すブロック図である。図１に示すマッチング装置１は、例えばＰＣ（パーソナルコンピュータ）等の情報処理装置である。マッチング装置１は、入力された情報に基づいて、それぞれに優先順位が付された複数の応募者と、複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象とのマッチングを実行し、マッチング結果を出力する。このマッチング結果をもとに、ユーザは、応募対象への応募者の割り当てを行う。
【００１１】
なお、本実施形態では応募対象を保育所とし、応募者を保育所での保育を希望する保護者の子どもとしているが、応募対象および応募者については実施形態の例に限定しない。例えば、応募者を宿泊客、応募対象を客室として旅館における宿泊客の部屋割りに適用してもよい。
【００１２】
図１に示すように、マッチング装置１は、記憶部１０、入力部２０、マッチング処理部３０、応募状況更新部４０および出力部５０を有する。
【００１３】
記憶部１０は、各種情報をＲＡＭ（Random  Access  Memory）、ＨＤＤ（Hard  Disk  Drive）等の記憶装置に格納する。具体的には、記憶部１０は、入力部２０より入力された応募対象情報１１および応募者情報１２等の入力情報、マッチング処理部３０および応募状況更新部４０による演算時の演算データ１３およびマッチング結果を示す結果データ１４を格納する。
【００１４】
応募対象情報１１は、入力部２０により入力されて予め設定された、応募対象についての情報である。応募者情報１２は、入力部２０により入力されて予め設定された、応募者についての情報である。
【００１５】
図２は、応募対象情報と、応募者情報とを説明する説明図である。なお、申請者１２ａには、「Ｉ〜ＩＶ」のギリシャ数字が申請者ＩＤとして割り当てられているものとする。以後、申請者１２ａを区別して称する場合は、申請者１２ａ（Ｉ）などの申請者ＩＤとして割り当てられたギリシャ数字を記するものとする。また、応募者であるこども１２ｂには、「１〜６」の囲み数字が子どもＩＤとして割り当てられているものとする。以後、こども１２ｂを区別して称する場合は、こども１２ｂ（１）などの子どもＩＤとして割り当てられた囲み数字を記するものとする。また、応募対象である保育所１１ａには、「Ａ〜Ｃ」の文字が保育所ＩＤとして割り当てられているものとする。以後、保育所１１ａを区別して称する場合は、保育所１１ａ（Ａ）などの保育所ＩＤとして割り当てられた囲み数字を記するものとする。
【００１６】
図２に示すように、応募対象情報１１には、応募対象である保育所１１ａごとの受け入れ人数（定員）と、応募者であるこども１２ｂの選好順序（優先順位）とが設定されている。例えば、選好順序については、子どもＩＤの並び順で示される。一例として、保育所１１ａ（Ａ）については、定員が２名であり、「５＞６＞１＞２＞３＞４」の順にこども１２ｂの選好順序が設定されている。言い換えると、保育所１１ａ（Ａ）は、こども１２ｂ（１〜６）からの応募に対して、「５＞６＞１＞２＞３＞４」の順に利得が設定されている。
【００１７】
応募者情報１２には、子どもＩＤで識別されるこども１２ｂごとに、応募を希望する保育所１１ａの優先順序が設定されている。例えば、申請者１２ａ（III）におけるこども１２ｂ（３）については、Ｂ＞Ｃ＞Ｎ／Ａの順に保育所１１ａの優先順序が設定されている。なお、「Ｎ／Ａ」は申請なしを示すものとする。言い換えると、こども１２ｂ（３）は、保育所１１ａそれぞれへの応募について、Ｂ＞Ｃ＞Ｎ／Ａの順に利得を有する。
【００１８】
また、応募者情報１２において、同じ申請者１２ａが複数のこども１２ｂの応募を申請する場合は、例えばきょうだい（兄弟、兄妹、姉弟、姉妹）関係を有する子ども同士の申請であり、子ども同士でのカップリング要求があるものとする。カップリング要求とは、組みになった形で応募対象（保育所１１ａ）への割り当て（マッチング）を要求するものである。
【００１９】
例えば、申請者１２ａ（Ｉ）のこども１２ｂ（１）、（４）は、互いにきょうだい関係があり、お互いのカップリングを要求する応募者（カップリング応募者）であるものとする。同様に、申請者１２ａ（ＩＩ）のこども１２ｂ（２）、（５）は、互いにきょうだい関係があり、お互いのカップリングを要求するカップリング応募者であるものとする。
【００２０】
こども１２ｂ（１）、（４）と、こども１２ｂ（２）、（５）とは、組みになった形での応募対象（保育所１１ａ）への割り当て（マッチング）が応募者情報１２である保護者により希望されている。例えば、申請者１２ａ（Ｉ）における子どもＩＤが（１，４）の二人のこども１２ｂそれぞれついては、（Ａ，Ａ）＞（Ｂ，Ｂ）＞（Ｃ，Ｃ）＞（Ａ，Ｎ／Ａ）＞（Ｂ，Ｎ／Ａ）＞（Ｎ／Ａ，Ｎ／Ａ）の順に選好順序が設定されている。言い換えると、カップリング応募者である申請者１２ａ（１，４）は、保育所１１ａそれぞれへの応募について、（Ａ，Ａ）＞（Ｂ，Ｂ）＞（Ｃ，Ｃ）＞（Ａ，Ｎ／Ａ）＞（Ｂ，Ｎ／Ａ）＞（Ｎ／Ａ，Ｎ／Ａ）の順に利得を有する。
【００２１】
図１に戻り、演算データ１３は、マッチング処理部３０および応募状況更新部４０による、複数の応募者と複数の応募対象とのマッチング処理の演算時におけるデータである。例えば、演算データ１３には、ゲーム木（詳細は後述する）の探索にかかるデータが含まれる。また、演算データ１３には、複数の応募者それぞれが複数の応募対象それぞれに応募した場合の応募の集合を示す応募情報が含まれる。
【００２２】
結果データ１４は、マッチング処理部３０および応募状況更新部４０によるマッチング処理で算出された、応募者（子ども）の応募対象（保育所）への割り当て結果を示すデータである。
【００２３】
図３は、結果データ１４を説明する説明図である。図３に示すように、結果データ１４では、こども１２ｂを示す子どもＩＤ（１〜６）と、子どもの割り当て先の保育所１１ａを示す保育所ＩＤ（Ａ〜Ｃ）とが対応付けられている。
【００２４】
図１に戻り、入力部２０は、例えばマウスやキーボードなどの入力装置より、応募対象情報１１および応募者情報１２等のマッチング処理にかかる入力情報を受け付ける。入力部２０は、受け付けた応募対象情報１１および応募者情報１２を記憶部１０に格納する。
【００２５】
マッチング処理部３０は、応募対象情報１１および応募者情報１２をもとに、それぞれに優先順位が付された複数の応募者と複数の応募対象とのマッチング処理を行う。このマッチング処理において、マッチング処理部３０は、複数の応募者と複数の応募対象とのマッチングに対応した展開型ゲームを仮想する。そして、マッチング処理部３０は、複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求めて、部分ゲーム完全均衡の結果に基づくマッチングを行う。
【００２６】
展開型ゲームとは、ゲーム理論におけるゲームの表現形式の一つであり、各プレイヤーの手番の系列がゲーム木と呼ばれる木構造で表現されたものである。ゲーム木は、節点（ノード）と枝（ブランチ）と、葉（リーフ（ノード））とで表現される。節点は、プレイヤーごとの手番（ゲームの局面）を示す。枝は、プレイヤーの選択肢（戦略）を示す。葉は、ゲームの終了局面である。展開型ゲームでは、トップの節点から枝を経て葉に至る終了局面までの各プレイヤーの選択により、各プレイヤーの利得が与えられる。
【００２７】
図４は、展開型ゲームを説明する説明図である。より具体的には、図４では、図２に例示した応募対象情報１１および応募者情報１２のケースを展開型ゲームのゲーム木１５で表したものである。
【００２８】
図４に示すように、ゲーム木１５は、応募者情報１２における申請者１２ａ（Ｉ）〜（ＩＶ）の手番（こども１２ｂ（１，４）、（２，５）、（３）、（６））の系列を木構造で示している。例えば、申請者１２ａ（ＩＩＩ）の手番（こども１２ｂ（３））では、Ｂ、Ｃ、Ｎ／Ａの選好順序がブランチとして表現される。
【００２９】
また、申請者１２ａ（ＩＶ）の手番（こども１２ｂ（６））でＣ、Ａ、Ｎ／Ａのいずれかを選択したところで、ゲームの終了局面となる。この終了局面まで至る過程で保育所１１ａのＡ〜Ｃを選択した内容が戦略結果１６である。
【００３０】
なお、保育所１１ａのそれぞれには定員（図２の例では各々２名）が設定されている。したがって、定員以上の選択がある場合は、応募対象情報１１における保育所１１ａごとの選好順序に従って受理された上位のものが戦略結果１６として格納される。例えば、こども１２ｂ（１，４）〜（６）に至る過程で（Ａ，Ａ）、（Ａ，Ａ）、（Ｂ）、（Ｃ）と選択した場合（図示例では一番左下の終了局面）、保育所１１ａ（Ａ）には定員以上の応募があることとなる。このような場合、応募対象情報１１の保育所１１ａ（Ａ）における選好順序（５＞６＞１＞２＞３＞４）より、上位のこども１２ｂ（５）、（１）が受理される。
【００３１】
部分ゲームとは、元の展開型ゲームの全体または一部分であり、それ自身も展開型ゲームである。部分ゲーム完全均衡とは、全ての部分ゲームにおいてナッシュ均衡となるような（どのプレイヤーも他のプレイヤーの戦略に対する最善の戦略を選んでいる）選択肢が選ばれている状況である。
【００３２】
具体的には、部分ゲーム完全均衡については、次のようにプレイヤー（こども１２ｂ）の戦略を決め、その戦略における効用（利得）を評価することで最適戦略を求める。たとえば、プレイヤー（こども１２ｂ）の戦略は、選好順序のリストにある要素（個別の保育所１１ａまたは保育所１１ａの組み合わせ）の一つを選んで応募することとする。プレイヤーの効用（利得）は、応募どおりに入所できなければ戦略失敗となり、効用を最低とする。また、応募どおりに入所できれば戦略成功であり、選好順序が高いほど効用（利得）も高いものとして評価する。
【００３３】
図５〜図９は、部分ゲーム完全均衡を説明する説明図である。図５に示すように、申請者１２ａ（ＩＶ）におけるこども１２ｂ（６）の戦略（戦略結果１６の網掛け部分）は、選好順序のリストにある要素（Ｃ、Ａ、Ｎ／Ａ）の一つである。このこども１２ｂ（６）の戦略における効用については、選好順序（Ｃ＞Ａ＞Ｎ／Ａ）の高い順に順位付けが行われる。なお、図中の太線矢印は、効用の最も高い最適戦略を示す。
【００３４】
また、図６に示すように、申請者１２ａ（ＩＩＩ）におけるこども１２ｂ（３）の戦略における効用も、選好順序（Ｂ＞Ｃ＞Ｎ／Ａ）の高い順に順位付けが行われる。
【００３５】
また、図７に示すように、申請者１２ａ（ＩＩ）におけるこども１２ｂ（２，５）の戦略における効用も、選好順序（（Ａ，Ａ）＞（Ｂ，Ｂ）＞（Ｃ，Ｃ）＞（Ｂ，Ａ）＞（Ｎ／Ａ，Ｎ／Ａ））の高い順に順位付けが行われる。なお、応募どおりに入所できなければ戦略失敗となり、効用を最低とする。例えば、左端の戦略などは、応募どおりに入所できないことから、戦略失敗となる。
【００３６】
また、図８に示すように、申請者１２ａ（Ｉ）におけるこども１２ｂ（１，４）の戦略における効用も、選好順序（（Ａ，Ａ）＞（Ｂ，Ｂ）＞（Ｃ，Ｃ）＞（Ａ、Ｎ／Ａ）＞（Ｂ，Ｎ／Ａ）＞（Ｎ／Ａ，Ｎ／Ａ））の高い順に順位付けが行われる。ここで、申請者１２ａ（Ｉ）における３位の戦略が、どのプレイヤーも他のプレイヤーの戦略に対する最善の戦略（全てが太線矢印）を選んでいる状況である。
【００３７】
よって、図９に示すように、申請者１２ａ（Ｉ）のこども１２ｂ（１，４）については、（Ｃ、Ｃ）の保育所１１ａを選ぶ。申請者１２ａ（ＩＩ）のこども１２ｂ（２，５）については、（Ｂ、Ａ）の保育所１１ａを選ぶ。申請者１２ａ（ＩＩＩ）のこども１２ｂ（３）については、（Ｂ）の保育所１１ａを選ぶ。申請者１２ａ（ＩＶ）のこども１２ｂ（６）については、（Ａ）の保育所１１ａを選ぶ。このように選ぶ戦略が部分ゲーム完全均衡である。
【００３８】
マッチング処理部３０は、応募者情報１２における複数の応募者（こども１２ｂ）それぞれを、各自の選好に対応した利得を有する独立した複数のプレイヤーとし、順に１回ずつプレイ（保育所１１ａの選択）する完全情報ゲームを仮想する。完全情報ゲームとは、全ての節点において、そこに至るまでの状態や選択肢が全て与えられている展開型ゲームを示す。すなわち、全てのプレイヤーは、ゲーム（割り当て）にかかる全ての情報（応募先および応募者の優先順位、きょうだい関係（カップリング要求の有無）および保育所１１ａの定員など）を知っているものとする。
【００３９】
次いで、マッチング処理部３０は、応募対象情報１１および応募者情報１２をもとに、申請順と同じ順序（Ｉ→ＩＩ→ＩＩＩ→ＩＶ）で各プレイヤーのプレイ（選択肢の選択）を行い、前のプレイヤーへのバックトラックを行いながらゲーム木１５を探索して部分ゲーム完全均衡を求める。
【００４０】
図１０は、バックトラックを説明する説明図である。図１０に示すように、マッチング処理部３０は、次のとおりにゲーム木１５を探索する。
・各節点（プレイヤーの手番）では、利益が上位の戦略から順に試す。
・保育所１１ａの定員からあふれるこども１２ｂが出なければ下位の節点（次の手番）へ移る。
・保育所１１ａの定員からあふれるこども１２ｂが出た場合、利益が最も下位の対応するプレイヤーまで戻って戦略を変更する。
・保育所１１ａの定員からあふれるこども１２ｂ無しでゲーム木１５の葉に到達した場合、ゲーム木１５の根から葉に至るパスを部分ゲーム完全均衡とする。
【００４１】
具体的には、保育所１１ａの定員からあふれるこども１２ｂが生じて失敗したパス１５ａでは、利益が最も下位の対応するプレイヤーまで戻る（バックトラックする）。そして、マッチング処理部３０は、戻ったプレイヤーにおいて、戦略を変更して探索を継続する。次いで、マッチング処理部３０は、ゲーム木１５の葉に到達する戦略結果１６が得られたパス１５ｂを、部分ゲーム完全均衡とする。
【００４２】
応募状況更新部４０は、マッチング処理部３０が部分ゲーム完全均衡を求める際に、応募者情報１２および応募対象情報１１をもとに、応募者（こども１２ｂ）が応募対象（保育所１１ａ）に応募する応募状況の先読みを行う応募状況更新処理を実行する。部分ゲーム完全均衡を求める際に応募状況の先読みを行うことで、マッチング装置１では、応募者と応募対象との双方で選好順序が決まっている場合であっても、その選好順序を考慮した適切な応募対象への割り当てを実施できる。また、応募状況の先読みにより、ゲーム木１５の選択肢の枝刈りが行われることから、マッチング装置１は、部分ゲーム完全均衡を求める際に探索するパス数を削減でき、計算量を抑えて部分ゲーム完全均衡を求めることができる。
【００４３】
具体的には、応募状況の先読みでは、それぞれのこども１２ｂが入所する可能性のある全ての保育所１１ａに応募した後、全体の応募状況を観察して入所の可能性が消えた保育所１１ａへの応募をキャンセルしていく。
【００４４】
図１１は、応募状況更新の概要を説明する説明図である。図１１に示すように、応募状況更新部４０は、それぞれのこども１２ｂが入所する可能性のある全ての保育所１１ａに応募した場合の応募の集合を求める応募最大化を行う（Ｓ２０１）。すなわち、最大化した応募の集合は、それぞれの保育所１１ａへの最終的な入所者を確実に含む集合である。例えば、選好順序のリストに保育所１１ａを含む全てのこども１２ｂの集合でもよい。
【００４５】
ここで、応募の集合について説明する。応募の集合には、応募者集合（Ａｑ）と、確定応募者集合（Ｆｑ）とがある。応募状況更新部４０は、応募状況として、応募者集合（Ａｑ）および確定応募者集合（Ｆｑ）を応募状況更新処理で求める。
【００４６】
応募者集合（Ａｑ）は、保育所１１ａ（ｑ）に応募している（＝入園する可能性のある）こども１２ｂの集合である。応募者集合（Ａｑ）の中で、保育所１１ａ（ｑ）における優先順位の上位から定員以内に入ることを「保育所１１ａ（ｑ）に受理される」と言う。応募した全ての保育所１１ａが受理される戦略は成功確定とする。
【００４７】
確定応募者集合（Ｆｑ）は、応募者集合（Ａｑ）の部分集合であり、保育所１１ａ（ｑ）への応募をキャンセルしないこども１２ｂの集合である。確定応募者集合（Ｆｑ）の中で、保育所１１ａ（ｑ）における優先順位の上位から定員以内に入らないことを「保育所１１ａ（ｑ）に拒絶される」と言う。一人以上のこども１２ｂが保育所１１ａに拒絶される戦略は失敗確定とする。
【００４８】
応募状況更新部４０は、応募対象情報１１における各保育所１１ａの定員および優先順位をもとに、応募最大化により求めた応募者集合（Ａｑ）から成功確定の戦略を判別する。これにより成功確定が判明する（Ｓ２０２）。
【００４９】
次いで、応募状況更新部４０は、応募者集合（Ａｑ）より保育所１１ａ（ｑ）への応募をキャンセルしないこども１２ｂの確定応募者集合（Ｆｑ）を求め、応募の確定を行う。
【００５０】
具体的には、応募状況更新部４０は、あるこども１２ｂを含む応募者集合（Ａｑ）が一つ（こども１２ｂの応募先が一つ）の場合は、キャンセルしないものとして応募を確定する。例えば、応募中の戦略が一つの場合、応募中の複数の戦略全てにおいて応募先が同じ場合も同様に、応募を確定する。
【００５１】
また、応募状況更新部４０は、カップリング応募者ではない単独のこども１２ｂ（きょうだいを持たないこども１２ｂ）の最善の応募先をキャンセルしないものとして応募を確定する。これは、最善であることが他のきょうだいの入所可能性に影響されないため確定可能である。ただし、この確定が間接的に他のプレイヤーの行動に影響を与える場合があり、まれに、割り当て結果が部分ゲーム完全均衡とは異なる近似解になることがある。この確定は行わなくても良く、その場合には処理時間が増えるが、結果は必ず部分ゲーム完全均衡になる。
【００５２】
また、応募状況更新部４０は、残っている（失敗確定でない）戦略の間において、きょうだいの選好順序が論理的に独立であるときの、それぞれの最善の応募先をキャンセルしないものとして応募を確定する。
【００５３】
図１２は、互いの選好順序が論理的に独立であるケースを説明する説明図である。図１２に示すように、ケースＣ１では、二人のきょうだいが上下で示すような選好順序である。このような、ケースＣ１では、上のきょうだいの選好順序（Ａ＞Ｂ＞Ｎ／Ａ）と、下のきょうだいの選好順序（Ｃ＞Ｄ＞Ｎ／Ａ）とが論理的に独立している。このような場合、応募状況更新部４０は、それぞれの最善の応募先（Ａ、Ｃ）を確定する。
【００５４】
この応募の確定により、最善戦略の成功が確定したプレイヤーなどが応募を確定していく（Ｓ２０３）。この応募の確定により、応募者集合（Ａｑ）の中では失敗確定が増加する（Ｓ２０４）。
【００５５】
応募状況更新部４０は、応募者集合（Ａｑ）を参照して、失敗確定の戦略に関する応募をキャンセルする。これにより、戦略の失敗が確定したプレイヤー（こども１２ｂ）がその応募をキャンセルし（Ｓ２０５）、応募者集合（Ａｑ）の中では成功確定が増加する（Ｓ２０６）。
【００５６】
次いで、応募状況更新部４０は、応募者集合（Ａｑ）を参照して、戦略の成功が確定したプレイヤー（こども１２ｂ）を特定し、不要となった低利得の応募（優先順位の低い応募）をキャンセルする（Ｓ２０７）。これにより、応募者集合（Ａｑ）の中では成功確定が増加することから（Ｓ２０８）、応募状況更新部４０は、さらに不要となった低利得の応募をキャンセルすることとなる。
【００５７】
ここで、上記の応募状況更新を含む、マッチング装置１における処理の詳細を説明する。図１３は、実施形態にかかるマッチング装置１の動作例を示すフローチャートである。図１３に示すように、処理が開始されると、応募状況更新部４０は、応募状況更新処理を行う（Ｓ１）。
【００５８】
図１４は、応募状況更新処理の一例を示すフローチャートである。図１４に示すように、応募状況更新処理が開始されると、応募状況更新部４０は、応募の最大化を行う（Ｓ１０）。
【００５９】
図１５は、応募最大化処理の一例を示すフローチャートである。図１５に示すように、応募状況更新部４０は、各園（保育所１１ａ）の応募者集合（Ａａ）を空に設定する（Ｓ２０）。
【００６０】
次いで、応募状況更新部４０は、応募者情報１２におけるこども１２ｂ（プレイヤー）の中で、成功確定の応募済み戦略を持たないプレイヤー（ｐ）が存在するか否かを判定する（Ｓ２１）。成功確定の応募済み戦略を持たないプレイヤー（ｐ）が存在する場合（Ｓ２１：ＹＥＳ）、応募状況更新部４０は、応募者情報１２における選好順序をもとに、プレイヤー（ｐ）のまだ応募していない最も利得の高い戦略について応募し（Ｓ２２）、Ｓ２１へ処理を戻す。成功確定の応募済み戦略を持たないプレイヤー（ｐ）が存在しない場合（Ｓ２１：ＮＯ）、応募最大化が完了したことから、応募状況更新部４０は処理を終了する。
【００６１】
図１４に戻り、Ｓ１０に次いで、応募状況更新部４０は、応募者集合（Ａｑ）より前述した応募確定の条件にマッチする応募を探索し、応募者集合（Ａｑ）に含まれる応募の中で新たに応募確定が可能か否かを判定する（Ｓ１１）。新たに応募確定が可能でない場合（Ｓ１１：ＮＯ）、応募状況更新部４０は、応募状況更新処理をリターンする。
【００６２】
新たに応募確定が可能である場合（Ｓ１１：ＹＥＳ）、応募状況更新部４０は、応募確定の条件にマッチする応募を確定し、確定した応募を確定応募者集合（Ｆｑ）に加える（Ｓ１２）。
【００６３】
次いで、応募状況更新部４０は、応募者集合（Ａｑ）の中で前述した失敗確定の条件にマッチする応募を探索し、失敗確定の戦略に関する応募をキャセルする（Ｓ１３）。
【００６４】
次いで、応募状況更新部４０は、応募者集合（Ａｑ）の中で前述した成功確定の条件にマッチする応募を探索し、新たな成功確定が発生したか否かを判定する（Ｓ１４）。新たな成功確定が発生していない場合（Ｓ１４：ＮＯ）、応募状況更新部４０は、Ｓ１１へ処理を戻す。
【００６５】
新たな成功確定が発生した場合（Ｓ１４：ＹＥＳ）、応募状況更新部４０は、応募者集合（Ａｑ）の中で、新たに成功確定した戦略を持つプレイヤー（こども１２ｂ）の応募の全てを特定する。次いで、応募状況更新部４０は、応募者情報１２における選好順序をもとに、成功確定した戦略よりも利得の低い戦略に関する全ての応募をキャンセルし（Ｓ１５）、応募者集合（Ａｑ）から該当する応募を削除してＳ１４へ処理を戻す。
【００６６】
図１３に戻り、Ｓ１に次いで、マッチング処理部３０は、応募者情報１２におけるプレイヤー（１２ｂ）の選好順序をもとに、戦略が決まっていない最初のプレイヤー（ｐ）の探索ノードを作成する（Ｓ２）。
【００６７】
次いで、マッチング処理部３０は、応募者集合（Ａｑ）を参照し、プレイヤー（ｐ）の失敗確定でない最善の戦略（選好順序のより高いもの）を選択する。次いで、マッチング処理部３０は、選択した応募を確定として、確定応募者集合（Ｆｑ）に加え、プレイヤー（ｐ）の他の応募をキャンセルして応募者集合（Ａｑ）から削除する（Ｓ３）。
【００６８】
次いで、応募状況更新部４０は、前述した応募状況更新処理を再び行う（Ｓ４）。次いで、マッチング処理部３０は、あるプレイヤー（ｐ’）が選んだ戦略が前述した失敗確定の条件にマッチするか否かをもとに、プレイヤー（ｐ’）の戦略の失敗が確定したか否かを判定する（Ｓ５）。
【００６９】
プレイヤー（ｐ’）の戦略の失敗が確定した場合（Ｓ５：ＹＥＳ）、マッチング処理部３０は、プレイヤー（ｐ’）の探索ノードまでバックトラックし（Ｓ６）、Ｓ３へ処理を戻す。
【００７０】
プレイヤー（ｐ’）の戦略の失敗が確定しない場合（Ｓ５：ＮＯ）、マッチング処理部３０は、全プレイヤーの戦略が決定したか否かを判定する（Ｓ７）。
【００７１】
全プレイヤーの戦略が決定した場合（Ｓ７：ＹＥＳ）、マッチング処理部３０は、探索ノードがゲーム木１５の葉まで達して部分ゲーム完全均衡を求めたことから、処理を終了する。全プレイヤーの戦略が決定していない場合（Ｓ７：ＮＯ）、マッチング処理部３０は、Ｓ２へ処理を戻す。
【００７２】
図１に戻り、出力部５０は、記憶部１０に格納された結果データ１４をもとに、マッチング処理部３０および応募状況更新部４０によるマッチング結果、すなわち、複数の応募対象への複数の応募者の割り当て結果を表示装置への表示、印刷装置への印字、ファイル出力などにより出力する。例えば、出力部５０は、結果データ１４をもとに、子どもごとに割り当てる保育所の表示を行う。これにより、ユーザは、保育所への子どもの割り当てを行うことができる。
【００７３】
ここで、応募状況の具体例などを示しながら、マッチング装置１における処理の説明を行う。
【００７４】
図１６−１〜図１６−７、図１８−１〜図１８−４、図２０−１〜図２０−５は、応募状況の具体例を説明する説明図である。なお、応募状況の具体例を説明する説明図において、こども１２ｂから保育所１１ａを結ぶ線は応募を示し、点線である場合は応募者集合（Ａｑ）に含まれる応募、実線である場合は確定応募者集合（Ｆｑ）に含まれる応募であることを示す。
【００７５】
図１７−１、図１７−２、図１９−１、図１９−２は、ノードの探索を説明する説明図である。図２１は、部分ゲーム完全均衡の探索結果を説明する説明図である。
【００７６】
これらの図面（図１６−１〜図２１）は、図２に例示した応募対象情報１１および応募者情報１２のケースをもとに、部分ゲーム完全均衡の探索結果が得られるまでの過程（Ｓ１０１〜Ｓ１５１）を説明している。
【００７７】
図１６−１〜図１６−５に示すように、まず、応募状況更新部４０は、応募対象情報１１および応募者情報１２をもとに、応募の最大化を行う（Ｓ１０１〜Ｓ１０５）。
【００７８】
具体的には、図１６−１に示すように、応募状況更新部４０は、こども１２ｂ（１，４）から順に、成功確定の応募済み戦略を持たないプレイヤーについて、最も利得の高い戦略について応募していく（Ｓ１０１〜Ｓ１０５）。
【００７９】
図１６−２に示すように、Ｓ１０２では、こども１２ｂ（２，５）が保育所１１ａ（Ａ）へ応募したことから、保育所１１ａの定員（２名）の上位の応募（５、１）が受理される。したがって、こども１２ｂ（１，４）の応募（Ａ，Ａ）の成功確定がキャンセルとなり、応募状況更新部４０は、こども１２ｂ（１，４）の次の応募を行うこととなる。
【００８０】
図１６−３に示すように、Ｓ１０３では、こども１２ｂ（１，４）、（２，５）まで成功確定の応募済み戦略を持つプレイヤーとなっている。よって、応募状況更新部４０は、成功確定の応募済み戦略を持たないこども１２ｂ（３）、（６）の応募を行う。
【００８１】
図１６−４に示すように、Ｓ１０４では、再びこども１２ｂ（１，４）が成功確定の応募済み戦略を持たないプレイヤーであることから、応募状況更新部４０は、こども１２ｂ（１，４）の次の応募を行う。これにより、最終的には、図１６−５の点線に示すように、それぞれのこども１２ｂが入所する可能性のある全ての保育所１１ａに応募した応募者集合（Ａｑ）が得られる。
【００８２】
次いで、応募状況更新部４０は、応募者集合（Ａｑ）より前述した応募確定の条件にマッチする応募を探索し、応募の確定を行う。具体的には、図１６−６に示すように、Ｓ１０６では、カップリング応募者ではない単独のこども１２ｂ（３、６）の応募が確定する。具体的には、こども１２ｂ（３）は応募（Ｂ）と、こども１２ｂ（６）の応募は（Ｃ）と確定する。
【００８３】
次いで、応募状況更新部４０は、応募の確定に伴う、戦略の失敗をキャンセルする。具体的には、図１６−７に示すように、Ｓ１０７では、こども１２ｂ（１，４）における応募（Ｂ，Ｂ）と、こども１２ｂ（２，５）における応募（Ｂ，Ｂ）とがキャンセルとなる。これにより、こども１２ｂ（４）、（５）から保育所１１ａ（Ｂ）に向かう点線（応募）が消去となる。
【００８４】
次いで、応募状況更新処理がリターンされ、マッチング処理部３０は、応募者情報１２におけるプレイヤー（１２ｂ）の選好順序をもとに、戦略が決まっていない最初のプレイヤーのノードを探索する。
【００８５】
具体的には、図１７−１に示すように、Ｓ１１１では、申請者１２ａ（Ｉ）のこども１２ｂ（１，４）をプレイヤーとして、選好順序に従ったノードの探索を行う。ここで、前の応募状況更新処理により、こども１２ｂ（３）は応募（Ｂ）と、こども１２ｂ（６）の応募は（Ｃ）とする応募状況１７が得られている。なお、応募状況１７は、確定応募者集合（Ｆｑ）に対応する。
【００８６】
こども１２ｂ（１，４）の選好順序は（Ａ，Ａ）が最も高いことから、図１７−２に示すように、Ｓ１１２では、こども１２ｂ（１，４）から（Ａ，Ａ）を選択するノードが探索される。これにより、応募状況１７は、こども１２ｂ（１，４）による保育所１１ａ（Ａ）の応募を確定とする。
【００８７】
次いで、応募状況更新部４０は、応募状況更新処理を行う。具体的には、図１８−１に示すように、応募状況更新処理の開始時（Ｓ１２１）では、こども１２ｂ（１，４）による保育所１１ａ（Ａ）の応募、こども１２ｂ（３）による保育所１１ａ（Ｂ）の応募およびこども１２ｂ（６）による保育所１１ａ（Ｃ）の応募を確定としている。
【００８８】
次いで、応募状況更新部４０は、Ｓ１２１の応募状況から応募の最大化を行う。具体的には、図１８−２に示すように、Ｓ１２２では、成功確定の応募済み戦略を持たないプレイヤー（２、５、６）について、応募を行い、応募者集合（Ａｑ）に加える。
【００８９】
次いで、応募状況更新部４０は、応募者集合（Ａｑ）より前述した応募確定の条件にマッチする応募を探索し、応募の確定を行う。具体的には、図１８−３に示すように、Ｓ１２３では、応募中の戦略が一つの場合に当てはまることから、こども１２ｂ（２，５）における保育所１１ａ（Ｃ）への応募が確定する。
【００９０】
次いで、応募状況更新部４０は、新たな成功確定による応募の確定を行う。具体的には、図１８−４に示すように、Ｓ１２４では、こども１２ｂ（６）における保育所１１ａ（Ａ）への応募が確定する。
【００９１】
次いで、応募状況更新処理がリターンされると、マッチング処理部３０は、こども１２ｂ（６）における保育所１１ａ（Ａ）への応募が確定により、プレイヤーであるこども１２ｂ（１，４）の戦略（Ａ，Ａ）が失敗したことから、バックトラックを行う。具体的には、図１９−１に示すように、Ｓ１３１では、こども１２ｂ（１，４）の戦略（Ａ，Ａ）が失敗したことでバックトラックが行われている。
【００９２】
次いで、マッチング処理部３０は、こども１２ｂ（１，４）における選好順序をもとに、別のノードを探索する。具体的には、図１９−２に示すように、Ｓ１３２では、申請者１２ａ（Ｉ）のこども１２ｂ（１，４）をプレイヤーとして、選好順序に従った次のノード（Ｃ，Ｃ）の探索を行う。
【００９３】
次いで、応募状況更新部４０は、応募状況更新処理を行う。具体的には、図２０−１に示すように、応募状況更新処理の開始時（Ｓ１４１）では、こども１２ｂ（１，４）による保育所１１ａ（Ｃ）の応募、こども１２ｂ（３）による保育所１１ａ（Ｂ）の応募およびこども１２ｂ（６）による保育所１１ａ（Ｃ）の応募を確定としている。
【００９４】
次いで、応募状況更新部４０は、Ｓ１２１の応募状況から応募の最大化を行う。具体的には、図２０−２に示すように、Ｓ１４２では、成功確定の応募済み戦略を持たないプレイヤー（２、５、６）について、応募を行い、応募者集合（Ａｑ）に加える。
【００９５】
次いで、応募状況更新部４０は、応募者集合（Ａｑ）より前述した応募確定の条件にマッチする応募を探索し、応募の確定を行う。具体的には、図２０−３に示すように、Ｓ１４３では、こども１２ｂ（２，６）における保育所１１ａ（Ａ）への応募が確定する。
【００９６】
次いで、応募状況更新部４０は、応募の確定に伴う、戦略の失敗をキャンセルする。具体的には、図２０−４に示すように、Ｓ１４４では、こども１２ｂ（２）における応募（Ａ）がキャンセルとなる。これにより、こども１２ｂ（２）から保育所１１ａ（Ａ）に向かう点線（応募）が消去となる。
【００９７】
次いで、応募状況更新部４０は、新たに応募確定が可能か否かを探索し、応募を確定する。具体的には、図２０−５に示すように、Ｓ１４５では、こども１２ｂ（２）における応募（Ｂ）が確定する。これにより、こども１２ｂ（２）から保育所１１ａ（Ｂ）に向かう点線が実線となる。
【００９８】
次いで、マッチング処理部３０は、得られた応募状況１７（確定応募者集合（Ｆｑ））をもとに、部分ゲーム完全均衡の探索を続ける。具体的には、図２１に示すように、Ｓ１５１では、部分ゲーム完全均衡となる応募状況１７が得られていることから、応募状況１７に沿って探索することで、容易に部分ゲーム完全均衡を求めることができる。
【００９９】
以上のように、マッチング装置１は、マッチング処理部３０、応募状況更新部４０を有し、それぞれに優先順位が付された複数の応募者（こども１２ｂ）と、複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象（保育所１１ａ）とのマッチングを実行する。マッチング処理部３０は、マッチングに対応した展開型ゲームであって、複数の応募者それぞれの選好に対応した利得を有する独立した複数のプレイヤーに関し、複数の応募者それぞれの優先順位をプレイの順番と対応づけられ、かつ、複数のプレイヤーそれぞれは複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求める。そして、マッチング処理部３０は、部分ゲーム完全均衡の結果に基づくマッチングを行い、結果データ１４を得る。応募状況更新部４０は、特定の他の応募者と組になった形での利得を持つカップリング応募者それぞれ、および、個別の応募者に対応する応募者それぞれについて、利得が設定された各応募対象へ応募させ、複数の応募対象それぞれについての応募の集合を示す応募情報を生成する。また、応募状況更新部４０は、生成された応募情報の集合の中から、複数の応募者に対する優先順位に従い、複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定する第１処理を行う。また、応募状況更新部４０は、応募確定に伴い失敗が確定する他の応募者の応募を特定する第２処理を行う。また、応募状況更新部４０は、他の応募者の失敗確定に対応した応募をキャンセルさせるとともに、キャンセルにより成功が確定する応募を特定する第３処理を行う。また、応募状況更新部４０は、成功確定した応募者の、当該成功確定した応募より利得が低い応募をキャンセルさせる第４処理を行う。そして、応募状況更新部４０は、第１処理から第４処理を応募の集合の中から確定する応募が無くなるまで繰り返す。これにより、マッチング装置１は、例えば、子どもなどの応募者と、保育所などの応募対象との双方で選好順序が決まっている場合であっても、その選好順序を考慮した適切な応募対象への割り当てを行うことができる。
【０１００】
また、応募状況更新部４０は、マッチング処理部３０による展開型ゲームの部分ゲーム完全均衡を求める処理に先立って、または、部分ゲーム完全均衡を求める処理の途中で、応募情報を生成して第１処理から第４処理を応募の集合の中から確定する応募が無くなるまで繰り返す処理を行う。このように、マッチング装置１は、展開型ゲームの部分ゲーム完全均衡を求める処理に先立って、応募状況を更新することで、ゲーム木１５の選択肢の枝刈りを行うことができる。これにより、マッチング装置１は、部分ゲーム完全均衡を求める際に探索するパス数を削減でき、計算量を抑えて部分ゲーム完全均衡を求めることができる。
【０１０１】
ここで、本実施形態のマッチング装置１における次の設定条件での実験結果を表に示す。
［設定条件］
・保育所の数：２〜１０施設
・各保育所の年齢別クラスの数：６クラス
・各保育所の受け入れ人数：４人
・子どもの数：４８〜２４０人
・きょうだい関係を有する子どもの割合：０．４
・上記のパラメータ設定ごとに、１００個のランダム問題に対する実験結果の平均を求める。
【０１０２】
【表１】
2019067158.tif 000003
【０１０３】
実験結果の表に示すように、展開型ゲームの部分ゲーム完全均衡を求める処理に先立って応募状況を更新する先読みありの場合と、先読みなしの場合とを比較すると、先読みありの場合には、ゲーム木が大きくなる場合であっても長大な計算時間となることを抑止できる。
【０１０４】
なお、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１０５】
マッチング装置１で行われる各種処理機能は、ＣＰＵ（またはＭＰＵ、ＭＣＵ（Micro  Controller  Unit）等のマイクロ・コンピュータ）上で、その全部または任意の一部を実行するようにしてもよい。また、各種処理機能は、ＣＰＵ（またはＭＰＵ、ＭＣＵ等のマイクロ・コンピュータ）で解析実行されるプログラム上、またはワイヤードロジックによるハードウエア上で、その全部または任意の一部を実行するようにしてもよいことは言うまでもない。また、マッチング装置１で行われる各種処理機能は、クラウドコンピューティングにより、複数のコンピュータが協働して実行してもよい。
【０１０６】
ところで、上記の実施形態で説明した各種の処理は、予め用意されたプログラムをコンピュータで実行することで実現できる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータ（ハードウエア）の一例を説明する。図２２は、実施形態にかかるマッチング装置１のハードウエア構成例を説明する説明図である。
【０１０７】
図２２に示すように、マッチング装置１は、各種演算処理を実行するＣＰＵ１０１と、データ入力を受け付ける入力装置１０２と、モニタ１０３と、スピーカ１０４とを有する。また、マッチング装置１は、記憶媒体からプログラム等を読み取る媒体読取装置１０５と、各種装置と接続するためのインタフェース装置１０６と、有線または無線により外部機器と通信接続するための通信装置１０７とを有する。また、マッチング装置１は、各種情報を一時記憶するＲＡＭ１０８と、ハードディスク装置１０９とを有する。また、マッチング装置１内の各部（１０１〜１０９）は、バス１１０に接続される。
【０１０８】
ハードディスク装置１０９には、上記の実施形態で説明した各種の処理を実行するためのプログラム１１１が記憶される。また、ハードディスク装置１０９には、プログラム１１１が参照する各種データ１１２が記憶される。入力装置１０２は、例えば、マッチング装置１の操作者から操作情報の入力を受け付ける。モニタ１０３は、例えば、操作者が操作する各種画面を表示する。インタフェース装置１０６は、例えば印刷装置等が接続される。通信装置１０７は、ＬＡＮ（Local  Area  Network）等の通信ネットワークと接続され、通信ネットワークを介した外部機器との間で各種情報をやりとりする。
【０１０９】
ＣＰＵ１０１は、ハードディスク装置１０９に記憶されたプログラム１１１を読み出して、ＲＡＭ１０８に展開して実行することで、各種の処理を行う。なお、プログラム１１１は、ハードディスク装置１０９に記憶されていなくてもよい。例えば、マッチング装置１が読み取り可能な記憶媒体に記憶されたプログラム１１１を、マッチング装置１が読み出して実行するようにしてもよい。マッチング装置１が読み取り可能な記憶媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢ（Universal  Serial  Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ等に接続された装置にこのプログラムを記憶させておき、マッチング装置１がこれらからプログラムを読み出して実行するようにしてもよい。
【０１１０】
以上の実施形態に関し、さらに以下の付記を開示する。
【０１１１】
（付記１）それぞれに優先順位が付された複数の応募者と、前記複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象とのマッチングをコンピュータに実行させるマッチングプログラムであって、
前記マッチングに対応した展開型ゲームであって、前記複数の応募者それぞれの選好に対応した利得を有する独立した複数のプレイヤーに関し、前記複数の応募者それぞれの優先順位をプレイの順番と対応づけられ、かつ、前記複数のプレイヤーそれぞれは前記複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求め、
前記部分ゲーム完全均衡の結果に基づくマッチングを行い、
特定の他の応募者と組になった形での利得を持つカップリング応募者それぞれ、および、個別の応募者に対応する応募者それぞれについて、利得が設定された各応募対象へ応募させ、前記複数の応募対象それぞれについての応募の集合を示す応募情報を生成し、
生成された前記応募情報の集合の中から、前記複数の応募者に対する前記優先順位に従い、前記複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定する第１処理と、
前記応募確定に伴い失敗が確定する他の応募者の応募を特定する第２処理と、
前記他の応募者の失敗確定に対応した応募をキャンセルさせるとともに、当該キャンセルにより成功が確定する応募を特定する第３処理と、
前記成功確定した応募者の、当該成功確定した応募より前記利得が低い応募をキャンセルさせる第４処理との前記第１処理から第４処理を前記集合の中から確定する応募が無くなるまで繰り返す、
処理をコンピュータに実行させることを特徴とするマッチングプログラム。
【０１１２】
（付記２）前記生成して繰り返す処理は、前記成功確定から失敗確定となる応募の応募者について、利得が設定された各応募対象へ応募させて別の応募を行う、
ことを特徴とする付記１に記載のマッチングプログラム。
【０１１３】
（付記３）前記生成して繰り返す処理は、前記部分ゲーム完全均衡を求める処理に先立って、または、前記部分ゲーム完全均衡を求める処理の途中で行う、
ことを特徴とする付記１または２に記載のマッチングプログラム。
【０１１４】
（付記４）前記特定の他の応募者と組になった形での利得を持つカップリング応募者とは、互いにきょうだい関係を有する応募者である、
ことを特徴とする付記１乃至３のいずれか一に記載のマッチングプログラム。
【０１１５】
（付記５）前記マッチングは、優先順位が付された複数の子どもと、当該複数の子どもそれぞれに対する優先順がそれぞれ付された複数の保育所とのマッチングである、
ことを特徴とする付記１乃至４のいずれか一に記載のマッチングプログラム。
【０１１６】
（付記６）それぞれに優先順位が付された複数の応募者と、前記複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象とのマッチングをコンピュータが実行するマッチング方法であって、
前記マッチングに対応した展開型ゲームであって、前記複数の応募者それぞれの選好に対応した利得を有する独立した複数のプレイヤーに関し、前記複数の応募者それぞれの優先順位をプレイの順番と対応づけられ、かつ、前記複数のプレイヤーそれぞれは前記複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求め、
前記部分ゲーム完全均衡の結果に基づくマッチングを行い、
特定の他の応募者と組になった形での利得を持つカップリング応募者それぞれ、および、個別の応募者に対応する応募者それぞれについて、利得が設定された各応募対象へ応募させ、前記複数の応募対象それぞれについての応募の集合を示す応募情報を生成し、
生成された前記応募情報の集合の中から、前記複数の応募者に対する前記優先順位に従い、前記複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定する第１処理と、
前記応募確定に伴い失敗が確定する他の応募者の応募を特定する第２処理と、
前記他の応募者の失敗確定に対応した応募をキャンセルさせるとともに、当該キャンセルにより成功が確定する応募を特定する第３処理と、
前記成功確定した応募者の、当該成功確定した応募より前記利得が低い応募をキャンセルさせる第４処理との前記第１処理から第４処理を前記集合の中から確定する応募が無くなるまで繰り返す、
処理をコンピュータが実行することを特徴とするマッチング方法。
【０１１７】
（付記７）前記生成して繰り返す処理は、前記成功確定から失敗確定となる応募の応募者について、利得が設定された各応募対象へ応募させて別の応募を行う、
ことを特徴とする付記６に記載のマッチング方法。
【０１１８】
（付記８）前記生成して繰り返す処理は、前記部分ゲーム完全均衡を求める処理に先立って、または、前記部分ゲーム完全均衡を求める処理の途中で行う、
ことを特徴とする付記６または７に記載のマッチング方法。
【０１１９】
（付記９）前記特定の他の応募者と組になった形での利得を持つカップリング応募者とは、互いにきょうだい関係を有する応募者である、
ことを特徴とする付記６乃至８のいずれか一に記載のマッチング方法。
【０１２０】
（付記１０）前記マッチングは、優先順位が付された複数の子どもと、当該複数の子どもそれぞれに対する優先順がそれぞれ付された複数の保育所とのマッチングである、
ことを特徴とする付記６乃至９のいずれか一に記載のマッチング方法。
【０１２１】
（付記１１）それぞれに優先順位が付された複数の応募者と、前記複数の応募者それぞれに対する優先順位がそれぞれ付された複数の応募対象とのマッチングを実行するマッチング装置であって、
前記マッチングに対応した展開型ゲームであって、前記複数の応募者それぞれの選好に対応した利得を有する独立した複数のプレイヤーに関し、前記複数の応募者それぞれの優先順位をプレイの順番と対応づけられ、かつ、前記複数のプレイヤーそれぞれは前記複数のプレイヤーすべての利得を知っている展開型ゲームの部分ゲーム完全均衡を求め、前記部分ゲーム完全均衡の結果に基づくマッチングを行うマッチング処理部と、
特定の他の応募者と組になった形での利得を持つカップリング応募者それぞれ、および、個別の応募者に対応する応募者それぞれについて、利得が設定された各応募対象へ応募させ、前記複数の応募対象それぞれについての応募の集合を示す応募情報を生成し、生成された前記応募情報の集合の中から、前記複数の応募者に対する前記優先順位に従い、前記複数の応募者それぞれの利得に基づき選択された応募先より確定させる応募を特定する第１処理と、前記応募確定に伴い失敗が確定する他の応募者の応募を特定する第２処理と、前記他の応募者の失敗確定に対応した応募をキャンセルさせるとともに、当該キャンセルにより成功が確定する応募を特定する第３処理と、前記成功確定した応募者の、当該成功確定した応募より前記利得が低い応募をキャンセルさせる第４処理との前記第１処理から第４処理を前記集合の中から確定する応募が無くなるまで繰り返す応募状況更新部と、
を有することを特徴とするマッチング装置。
【０１２２】
（付記１２）前記応募状況更新部は、前記成功確定から失敗確定となる応募の応募者について、利得が設定された各応募対象へ応募させて別の応募を行う、
ことを特徴とする付記１１に記載のマッチング装置。
【０１２３】
（付記１３）前記応募状況更新部は、前記部分ゲーム完全均衡を求める処理に先立って、または、前記部分ゲーム完全均衡を求める処理の途中で、前記第１処理から第４処理を前記集合の中から確定する応募が無くなるまで繰り返す
ことを特徴とする付記１１に記載のマッチング装置。
【０１２４】
（付記１４）前記特定の他の応募者と組になった形での利得を持つカップリング応募者とは、互いにきょうだい関係を有する応募者である、
ことを特徴とする付記１１または１３に記載のマッチング装置。
【０１２５】
（付記１５）前記マッチングは、優先順位が付された複数の子どもと、当該複数の子どもそれぞれに対する優先順がそれぞれ付された複数の保育所とのマッチングである、
ことを特徴とする付記１１乃至１４のいずれか一に記載のマッチング装置。
【符号の説明】
【０１２６】
１…マッチング装置
１０…記憶部
１１…応募対象情報
１１ａ…保育所
１２…応募者情報
１２ａ…申請者
１２ｂ…こども
１３…演算データ
１４…結果データ
１５…ゲーム木
１５ａ、１５ｂ…パス
１６…戦略結果
１７…応募状況
２０…入力部
３０…マッチング処理部
４０…応募状況更新部
５０…出力部
１０１…ＣＰＵ
１０２…入力装置
１０３…モニタ
１０４…スピーカ
１０５…媒体読取装置
１０６…インタフェース装置
１０７…通信装置
１０８…ＲＡＭ
１０９…ハードディスク装置
１１０…バス
１１１…プログラム
１１２…各種データ
Ｃ１…ケース
【図１】
2019067158.tif 000004
【図２】
2019067158.tif 000005
【図３】
2019067158.tif 000006
【図４】
2019067158.tif 000007
【図５】
2019067158.tif 000008
【図６】
2019067158.tif 000009
【図７】
2019067158.tif 000010
【図８】
2019067158.tif 000011
【図９】
2019067158.tif 000012
【図１０】
2019067158.tif 000013
【図１１】
2019067158.tif 000014
【図１２】
2019067158.tif 000015
【図１３】
2019067158.tif 000016
【図１４】
2019067158.tif 000017
【図１５】
2019067158.tif 000018
【図１６−１】
2019067158.tif 000019
【図１６−２】
2019067158.tif 000020
【図１６−３】
2019067158.tif 000021
【図１６−４】
2019067158.tif 000022
【図１６−５】
2019067158.tif 000023
【図１６−６】
2019067158.tif 000024
【図１６−７】
2019067158.tif 000025
【図１７−１】
2019067158.tif 000026
【図１７−２】
2019067158.tif 000027
【図１８−１】
2019067158.tif 000028
【図１８−２】
2019067158.tif 000029
【図１８−３】
2019067158.tif 000030
【図１８−４】
2019067158.tif 000031
【図１９−１】
2019067158.tif 000032
【図１９−２】
2019067158.tif 000033
【図２０−１】
2019067158.tif 000034
【図２０−２】
2019067158.tif 000035
【図２０−３】
2019067158.tif 000036
【図２０−４】
2019067158.tif 000037
【図２０−５】
2019067158.tif 000038
【図２１】
2019067158.tif 000039
【図２２】
2019067158.tif 000040