JP6896254B2 - Matching program, matching method and matching device - Google Patents

Description

Embodiments of the present invention relate to matching programs, matching methods and matching devices.

Conventionally, Deferred-Acceptance (Gale-Shapley) is known in the matching process of assigning a large number of applicants (for example, children of parents who wish to have childcare) to application targets (for example, childcare institutions such as nursery schools).

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.

However, in the above-mentioned conventional technique, when the preference order of applicants is determined by the application target side such as a nursery school, there is a problem that it is difficult to appropriately assign the applicants to the application target in consideration of the preference order. is there.

In one aspect, it is an object of the present invention to provide a matching program, a matching method, and a matching device that can request an appropriate assignment to an application target.

In the first proposal, the matching program causes the computer to perform matching between a plurality of applicants each having a priority and a plurality of application targets each having a priority for each of the plurality of applicants. Further, the matching program causes the computer to execute a process of obtaining the subgame perfect equilibrium, a process of performing matching, a process of generating, and a process of repeating. The required process is an extensive game that supports matching, and for multiple independent players who have gains corresponding to the preferences of each of the multiple applicants, the priority of each of the multiple applicants is associated with the order of play. And each of the multiple players knows the gains of all of the multiple players. The matching process performs matching based on the result of subgame perfect equilibrium. The process to generate is for each coupling applicant who has a gain in the form of a pair with a specific other applicant, and for each applicant for which a gain is set for each applicant corresponding to an individual applicant. And generate application information showing a set of applications for each of multiple application targets. The repeating process repeats the first process to the fourth process until there are no more applications to be confirmed from the set. The first process identifies an application to be confirmed from the applicants selected based on the gains of each of the plurality of applicants according to the priority for the plurality of applicants from the generated set of application information. The second process identifies the applications of other applicants whose failures are confirmed as the applications are confirmed. The third process cancels the application corresponding to the failure confirmation of other applicants, and identifies the application whose success is confirmed by the cancellation. The fourth process cancels the applicant whose success is confirmed and whose gain is lower than that of the successful application.

According to one embodiment of the present invention, it is possible to request an appropriate allocation to an application target.

FIG. 1 is a block diagram showing a functional configuration example of the matching device according to the embodiment. FIG. 2 is an explanatory diagram for explaining the application target information and the applicant information. FIG. 3 is an explanatory diagram for explaining the result data. FIG. 4 is an explanatory diagram illustrating an extensive game. FIG. 5 is an explanatory diagram illustrating subgame perfect equilibrium. FIG. 6 is an explanatory diagram illustrating subgame perfect equilibrium. FIG. 7 is an explanatory diagram illustrating subgame perfect equilibrium. FIG. 8 is an explanatory diagram illustrating subgame perfect equilibrium. FIG. 9 is an explanatory diagram illustrating subgame perfect equilibrium. FIG. 10 is an explanatory diagram illustrating backtracking. FIG. 11 is an explanatory diagram for explaining the outline of the application status update. FIG. 12 is an explanatory diagram illustrating a case where the preference order of each other is logically independent. FIG. 13 is a flowchart showing an operation example of the matching device according to the embodiment. FIG. 14 is a flowchart showing an example of the application status update process. FIG. 15 is a flowchart showing an example of the application maximization process. FIG. 16-1 is an explanatory diagram illustrating a specific example of the application status. FIG. 16-2 is an explanatory diagram illustrating a specific example of the application status. FIG. 16-3 is an explanatory diagram illustrating a specific example of the application status. FIG. 16-4 is an explanatory diagram illustrating a specific example of the application status. FIG. 16-5 is an explanatory diagram illustrating a specific example of the application status. FIG. 16-6 is an explanatory diagram illustrating a specific example of the application status. FIG. 16-7 is an explanatory diagram illustrating a specific example of the application status. FIG. 17-1 is an explanatory diagram illustrating the search for a node. FIG. 17-2 is an explanatory diagram illustrating the search for a node. FIG. 18-1 is an explanatory diagram illustrating a specific example of the application status. FIG. 18-2 is an explanatory diagram illustrating a specific example of the application status. FIG. 18-3 is an explanatory diagram illustrating a specific example of the application status. FIG. 18-4 is an explanatory diagram illustrating a specific example of the application status. FIG. 19-1 is an explanatory diagram illustrating the search for a node. FIG. 19-2 is an explanatory diagram illustrating the search for a node. FIG. 20-1 is an explanatory diagram illustrating a specific example of the application status. FIG. 20-2 is an explanatory diagram illustrating a specific example of the application status. FIG. 20-3 is an explanatory diagram illustrating a specific example of the application status. FIG. 20-4 is an explanatory diagram illustrating a specific example of the application status. FIG. 20-5 is an explanatory diagram illustrating a specific example of the application status. FIG. 21 is an explanatory diagram illustrating a search result of subgame perfect equilibrium. FIG. 22 is an explanatory diagram illustrating a hardware configuration example of the matching device according to the embodiment.

Hereinafter, the matching program, the matching method, and the matching apparatus according to the embodiment will be described with reference to the drawings. Configurations having the same function in the embodiment are designated by the same reference numerals, and duplicate description will be omitted. The matching program, matching method, and matching device described in the following embodiments are merely examples, and the embodiments are not limited. In addition, the following embodiments may be appropriately combined within a consistent range.

FIG. 1 is a block diagram showing a functional configuration example of the matching device according to the embodiment. The matching device 1 shown in FIG. 1 is an information processing device such as a PC (personal computer). Based on the input information, the matching device 1 executes matching between a plurality of applicants each having a priority and a plurality of application targets each having a priority for each of the plurality of applicants. , Output the matching result. Based on this matching result, the user assigns the applicant to the application target.

In this embodiment, the application target is a nursery school, and the applicant is a child of a guardian who wishes to have childcare at the nursery school, but the application target and the applicant are not limited to the example of the embodiment. For example, the applicant may be a guest and the application target may be a guest room, which may be applied to the room allocation of the guest at the inn.

As shown in FIG. 1, the matching device 1 includes a storage unit 10, an input unit 20, a matching processing unit 30, an application status update unit 40, and an output unit 50.

The storage unit 10 stores various types of information in a storage device such as a RAM (Random Access Memory) or an HDD (Hard Disk Drive). Specifically, the storage unit 10 includes input information such as application target information 11 and applicant information 12 input from the input unit 20, calculation data 13 and matching at the time of calculation by the matching processing unit 30 and the application status update unit 40. The result data 14 indicating the result is stored.

The application target information 11 is information about the application target input and preset by the input unit 20. The applicant information 12 is information about the applicant that is input and preset by the input unit 20.

FIG. 2 is an explanatory diagram for explaining the application target information and the applicant information. It is assumed that the applicant 12a is assigned the Greek numerals "I to IV" as the applicant ID. Hereinafter, when the applicant 12a is referred to separately, the Greek numeral assigned as the applicant ID such as the applicant 12a (I) shall be described. In addition, it is assumed that the child 12b who is the applicant is assigned the number enclosed in "1 to 6" as the child ID. Hereinafter, when the child 12b is referred to separately, the enclosed number assigned as the child ID such as the child 12b (1) shall be described. Further, it is assumed that the characters "A to C" are assigned as the nursery school ID to the nursery school 11a to be applied. Hereinafter, when the nursery school 11a is referred to separately, the enclosing number assigned as the nursery school ID such as the nursery school 11a (A) shall be described.

As shown in FIG. 2, in the application target information 11, the number of people accepted (capacity) for each nursery school 11a to be applied and the preference order (priority) of the child 12b who is the applicant are set. For example, the preference order is shown in the order of the child IDs. As an example, the nursery school 11a (A) has a capacity of two people, and the preference order of children 12b is set in the order of "5> 6> 1> 2> 3> 4". In other words, in the nursery school 11a (A), gains are set in the order of "5> 6> 1> 2> 3> 4" for applications from children 12b (1 to 6).

In the applicant information 12, the priority order of the nursery school 11a to which the application is desired is set for each child 12b identified by the child ID. For example, for the child 12b (3) in the applicant 12a (III), the priority order of the nursery school 11a is set in the order of B> C> N / A. In addition, "N / A" shall indicate that there is no application. In other words, the child 12b (3) has a gain in the order of B> C> N / A for each application to the nursery school 11a.

Further, in the applicant information 12, when the same applicant 12a applies for the application of a plurality of children 12b, for example, it is an application between children having a sibling (brother, brother and sister, sibling, sister) relationship, and the application is between children. Suppose there is a coupling request in. The coupling request is a request for allocation (matching) to the application target (nursery school 11a) in a combined form.

For example, it is assumed that the children 12b (1) and (4) of the applicant 12a (I) are applicants (coupling applicants) who have a sibling relationship with each other and request each other's coupling. Similarly, the children 12b (2) and (5) of the applicant 12a (II) are assumed to be coupling applicants who have a sibling relationship with each other and request each other's coupling.

The applicant information 12 is assigned (matching) to the application target (nursery school 11a) in the form of a combination of the children 12b (1) and (4) and the children 12b (2) and (5). Requested by parents. For example, for each of the two children 12b whose child ID is (1,4) in the applicant 12a (I), (A, A)> (B, B)> (C, C)> (A, N / A) )> (B, N / A)> (N / A, N / A). In other words, the applicant 12a (1,4) who is a coupling applicant has (A, A)> (B, B)> (C, C)> (A, N) for each application to the nursery school 11a. It has gains in the order of / A)> (B, N / A)> (N / A, N / A).

Returning to FIG. 1, the calculation data 13 is data at the time of calculation of matching processing between a plurality of applicants and a plurality of application targets by the matching processing unit 30 and the application status update unit 40. For example, the calculation data 13 includes data related to the search of the game tree (details will be described later). Further, the calculation data 13 includes application information indicating a set of applications when each of the plurality of applicants applies for each of the plurality of application targets.

The result data 14 is data showing the allocation result of the applicant (child) to the application target (nursery school) calculated by the matching process by the matching processing unit 30 and the application status updating unit 40.

FIG. 3 is an explanatory diagram illustrating the result data 14. As shown in FIG. 3, in the result data 14, the child IDs (1 to 6) indicating the child 12b and the nursery school IDs (A to C) indicating the nursery school 11a to which the child is assigned are associated with each other. ..

Returning to FIG. 1, the input unit 20 receives input information related to matching processing such as application target information 11 and applicant information 12 from an input device such as a mouse or a keyboard. The input unit 20 stores the received application target information 11 and the applicant information 12 in the storage unit 10.

The matching processing unit 30 performs matching processing between a plurality of applicants each having a priority and a plurality of application targets based on the application target information 11 and the applicant information 12. In this matching process, the matching processing unit 30 virtualizes an extensive game corresponding to matching between a plurality of applicants and a plurality of application targets. Then, the matching processing unit 30 obtains the subgame perfect equilibrium of the expanded game that knows the gains of all the plurality of players, and performs matching based on the result of the subgame perfect equilibrium.

Extensive-form games are one of the game expression formats in game theory, and the sequence of each player's turn is expressed by a tree structure called a game tree. A game tree is represented by nodes (nodes), branches (branches), and leaves (leafs (nodes)). The node indicates the turn (phase of the game) for each player. The branches indicate the player's choices (strategies). The leaves are the end of the game. In extensive games, each player's choice from the top node to the end of the branch through the branches gives each player a gain.

FIG. 4 is an explanatory diagram illustrating an extensive game. More specifically, in FIG. 4, the cases of the application target information 11 and the applicant information 12 illustrated in FIG. 2 are represented by the game tree 15 of the extensive game.

As shown in FIG. 4, the game tree 15 is the turn of the applicants 12a (I) to (IV) in the applicant information 12 (children 12b (1,4), (2,5), (3), ( The series of 6)) is shown in a tree structure. For example, in the turn of applicant 12a (III) (children 12b (3)), the preference order of B, C, N / A is expressed as a branch.

Further, when any one of C, A, and N / A is selected in the turn of the applicant 12a (IV) (children 12b (6)), the game ends. The content of selecting A to C of the nursery school 11a in the process leading up to this end phase is the strategic result 16.

In addition, each of the nursery schools 11a has a capacity (two people each in the example of FIG. 2). Therefore, when there is a selection of more than the capacity, the higher-ranked ones accepted according to the preference order for each nursery school 11a in the application target information 11 are stored as the strategy result 16. For example, when (A, A), (A, A), (B), (C) are selected in the process of reaching children 12b (1,4) to (6) (in the illustrated example, the lower left end phase). ), The nursery school 11a (A) will have more applications than the capacity. In such a case, the higher-ranking children 12b (5) and (1) are accepted from the preference order (5> 6> 1> 2> 3> 4) in the nursery school 11a (A) of the application target information 11.

A subgame is an entire or part of the original extensive game, and is itself an extensive game. Subgame perfect equilibrium is a situation in which options are selected that provide Nash equilibrium in all subgames (every player chooses the best strategy for the strategies of other players).

Specifically, for the subgame perfect equilibrium, the strategy of the player (children 12b) is determined as follows, and the optimum strategy is obtained by evaluating the utility (gain) in the strategy. For example, the strategy of the player (children 12b) is to select and apply for one of the elements (individual nursery school 11a or combination of nursery school 11a) in the list of preference order. As for the utility (gain) of the player, if the player cannot enter as applied, the strategy will fail and the utility will be the lowest. In addition, if you can enter as you applied, the strategy will be successful, and the higher the preference order, the higher the utility (gain) will be evaluated.

5 to 9 are explanatory views illustrating subgame perfect equilibrium. As shown in FIG. 5, the strategy of the child 12b (6) in the applicant 12a (IV) (the shaded portion of the strategy result 16) is one of the elements (C, A, N / A) in the list of preference order. It is one. The utility of this child 12b (6) strategy is ranked in descending order of preference (C> A> N / A). The thick arrow in the figure indicates the optimal strategy with the highest utility.

Further, as shown in FIG. 6, the utility of the child 12b (3) in the strategy of the applicant 12a (III) is also ranked in descending order of preference order (B> C> N / A).

Further, as shown in FIG. 7, the utility of the child 12b (2,5) in the strategy of the applicant 12a (II) is also the preference order ((A, A)> (B, B)> (C, C)>. Ranking is performed in descending order of (B, A)> (N / A, N / A)). If you cannot enter as you applied, your strategy will fail and the utility will be the lowest. For example, the strategy on the far left is a strategy failure because it cannot be entered as applied.

Further, as shown in FIG. 8, the utility of the child 12b (1,4) in the strategy of the applicant 12a (I) is also the preference order ((A, A)> (B, B)> (C, C)>. Ranking is performed in descending order of (A, N / A)> (B, N / A)> (N / A, N / A)). Here, the third-place strategy in the applicant 12a (I) is a situation in which every player selects the best strategy (all are thick arrows) with respect to the strategies of other players.

Therefore, as shown in FIG. 9, for the child 12b (1,4) of the applicant 12a (I), the nursery school 11a of (C, C) is selected. For the child 12b (2, 5) of the applicant 12a (II), the nursery school 11a of (B, A) is selected. For the child 12b (3) of the applicant 12a (III), the nursery school 11a of (B) is selected. For the child 12b (6) of the applicant 12a (IV), the nursery school 11a of (A) is selected. The strategy chosen in this way is subgame perfect equilibrium.

The matching processing unit 30 makes each of the plurality of applicants (children 12b) in the applicant information 12 into a plurality of independent players having a gain corresponding to their own preferences, and plays once in order (selection of the nursery school 11a). Virtualize a perfect information game. A perfect information game is an extensive game in which all the states and options up to that point are given at all nodes. That is, all players must know all the information related to the game (assignment) (priority of applicants and applicants, sibling relationships (whether or not there is a coupling request), capacity of nursery school 11a, etc.). To do.

Next, the matching processing unit 30 plays each player (selection of options) in the same order as the application order (I → II → III → IV) based on the application target information 11 and the applicant information 12, and then performs the previous Search the game tree 15 while backtracking to the player, and find the subgame perfect equilibrium.

FIG. 10 is an explanatory diagram illustrating backtracking. As shown in FIG. 10, the matching processing unit 30 searches for the game tree 15 as follows.
・ At each node (player's turn), try the strategies with the highest profits in order.
・ If the child 12b that overflows from the capacity of the nursery school 11a does not come out, move to the lower node (next turn).
・ If a child 12b overflows from the capacity of the nursery school 11a, return to the corresponding player with the lowest profit and change the strategy.
-If the leaves of the game tree 15 are reached without the children 12b overflowing from the capacity of the nursery school 11a, the path from the roots to the leaves of the game tree 15 is set as the subgame perfect equilibrium.

Specifically, in the pass 15a, which fails due to the overflow of children 12b from the capacity of the nursery school 11a, the player returns to the corresponding player with the lowest profit (backtracks). Then, the matching processing unit 30 changes the strategy and continues the search in the returning player. Next, the matching processing unit 30 sets the path 15b in which the strategy result 16 to reach the leaves of the game tree 15 is obtained as the subgame perfect equilibrium.

In the application status update unit 40, when the matching processing unit 30 seeks the subgame perfect equilibrium, the applicant (child 12b) becomes the application target (nursery school 11a) based on the applicant information 12 and the application target information 11. Performs the application status update process that pre-reads the application status to be applied. By pre-reading the application status when finding the subgame perfect equilibrium, even if the preference order is determined by both the applicant and the application target, the matching device 1 is appropriate in consideration of the preference order. Can be assigned to various application targets. Further, since the selection of the game tree 15 is pruned by pre-reading the application status, the matching device 1 can reduce the number of passes to be searched when obtaining the subgame perfect equilibrium, and can reduce the amount of calculation to perform the subgame. The perfect equilibrium can be found.

Specifically, in the look-ahead of the application status, after applying for all the nursery schools 11a where each child 12b may enter, the nursery school 11a where the possibility of admission disappeared by observing the entire application status. I will cancel the application to.

FIG. 11 is an explanatory diagram for explaining the outline of the application status update. As shown in FIG. 11, the application status update unit 40 maximizes the application for a set of applications when all the nursery schools 11a where each child 12b may enter is applied (S201). That is, the maximized set of applications is a set that surely includes the final residents of each nursery school 11a. For example, it may be a set of all children 12b including the nursery school 11a in the list of preference order.

Here, a set of applications will be described. The set of applications includes a set of applicants (Aq) and a set of confirmed applicants (Fq). The application status update unit 40 requests the applicant set (Aq) and the confirmed applicant set (Fq) as the application status by the application status update process.

The applicant set (Aq) is a set of children 12b who are applying for (= may enter the kindergarten) the nursery school 11a (q). In the group of applicants (Aq), entering within the capacity from the highest priority in the nursery school 11a (q) is said to be "accepted by the nursery school 11a (q)". The strategy in which all the applied nursery schools 11a are accepted will be confirmed as successful.

The final applicant set (Fq) is a subset of the applicant set (Aq), and is a set of children 12b who do not cancel the application to the nursery school 11a (q). In the finalized applicant set (Fq), it is said that the childcare center 11a (q) refuses to enter within the capacity from the highest priority in the nursery school 11a (q). The strategy in which one or more children 12b are rejected by the nursery school 11a is confirmed as a failure.

The application status update unit 40 determines the success determination strategy from the applicant set (Aq) obtained by maximizing the application based on the capacity and priority of each nursery school 11a in the application target information 11. As a result, success is confirmed (S202).

Next, the application status update unit 40 requests the finalized applicant set (Fq) of the child 12b who does not cancel the application to the nursery school 11a (q) from the applicant set (Aq), and confirms the application.

Specifically, if the application status update unit 40 has one applicant set (Aq) including a certain child 12b (one application destination for the child 12b), the application is confirmed as not being canceled. For example, if there is only one strategy being applied for, and the application destination is the same for all of the plurality of strategies being applied for, the application is confirmed in the same manner.

In addition, the application status update unit 40 confirms the application on the assumption that the best application destination of a single child 12b (child 12b without a sibling) who is not a coupling applicant is not canceled. This can be determined because the best is not affected by the admission of other siblings. However, this determination may indirectly affect the behavior of other players, and in rare cases, the allocation result may be an approximate solution different from the subgame perfect equilibrium. This confirmation does not have to be done, in which case the processing time will increase, but the result will always be subgame perfect equilibrium.

In addition, the application status update unit 40 applies on the assumption that the best applicants for each of the remaining strategies (which are not confirmed to fail) are not canceled when the sibling preference order is logically independent. Determine.

FIG. 12 is an explanatory diagram illustrating a case where the preference order of each other is logically independent. As shown in FIG. 12, in case C1, the preference order is as shown above and below by two siblings. In such case C1, the preference order of the upper siblings (A> B> N / A) and the preference order of the lower siblings (C> D> N / A) are logically independent. There is. In such a case, the application status update unit 40 determines the best application destination (A, C) for each.

By confirming this application, players who have confirmed the success of the best strategy will confirm the application (S203). Due to the confirmation of this application, the confirmation of failure increases in the applicant set (Aq) (S204).

The application status update unit 40 cancels the application related to the failure confirmation strategy with reference to the applicant set (Aq). As a result, the player (child 12b) whose strategy has been confirmed to fail cancels the application (S205), and the success confirmation increases in the applicant set (Aq) (S206).

Next, the application status update unit 40 refers to the applicant set (Aq), identifies the player (child 12b) whose strategy has been confirmed to be successful, and applies for a low gain that is no longer needed (application with a low priority). Is canceled (S207). As a result, the success confirmation increases in the applicant set (Aq) (S208), so that the application status update unit 40 cancels the unnecessary low-gain application.

Here, the details of the processing in the matching device 1 including the above-mentioned update of the application status will be described. FIG. 13 is a flowchart showing an operation example of the matching device 1 according to the embodiment. As shown in FIG. 13, when the process is started, the application status update unit 40 performs the application status update process (S1).

FIG. 14 is a flowchart showing an example of the application status update process. As shown in FIG. 14, when the application status update process is started, the application status update unit 40 maximizes the application (S10).

FIG. 15 is a flowchart showing an example of the application maximization process. As shown in FIG. 15, the application status update unit 40 sets the applicant set (Aa) of each kindergarten (nursery school 11a) to be empty (S20).

Next, the application status update unit 40 determines whether or not there is a player (p) who does not have an applied strategy for confirming success among the children 12b (players) in the applicant information 12 (S21). If there is a player (p) who does not have a successful applied strategy (S21: YES), the application status update unit 40 still applies for the player (p) based on the preference order in the applicant information 12. Apply for the strategy with the highest gain that has not been done (S22), and return the process to S21. If there is no player (p) who does not have an applied strategy for confirming success (S21: NO), the application status update unit 40 ends the process because the application maximization is completed.

Returning to FIG. 14, following S10, the application status update unit 40 searches for applications that match the above-mentioned application confirmation conditions from the applicant set (Aq), and among the applications included in the applicant set (Aq). It is determined whether or not a new application can be confirmed (S11). If it is not possible to confirm the application newly (S11: NO), the application status update unit 40 returns the application status update process.

When a new application can be confirmed (S11: YES), the application status update unit 40 confirms the application that matches the conditions for confirming the application, and adds the confirmed application to the confirmed applicant set (Fq) (S12). ..

Next, the application status update unit 40 searches for an application that matches the above-mentioned failure confirmation condition in the applicant set (Aq), and cancels the application related to the failure confirmation strategy (S13).

Next, the application status update unit 40 searches for an application that matches the above-mentioned success confirmation condition in the applicant set (Aq), and determines whether or not a new success confirmation has occurred (S14). If no new success confirmation has occurred (S14: NO), the application status update unit 40 returns the process to S11.

When a new success confirmation occurs (S14: YES), the application status update unit 40 identifies all the applications of the player (child 12b) having the newly successful confirmation strategy in the applicant set (Aq). To do. Next, the application status update unit 40 cancels all applications related to the strategy having a lower gain than the strategy whose success is confirmed based on the preference order in the applicant information 12 (S15), and corresponds from the applicant set (Aq). Delete the application to be done and return the process to S14.

Returning to FIG. 13, following S1, the matching processing unit 30 creates a search node for the first player (p) whose strategy has not been determined, based on the preference order of the player (12b) in the applicant information 12 ( S2).

Next, the matching processing unit 30 refers to the applicant set (Aq) and selects the best strategy (higher preference order) that does not confirm the failure of the player (p). Next, the matching processing unit 30 confirms the selected application, cancels other applications of the player (p) in addition to the confirmed applicant set (Fq), and deletes them from the applicant set (Aq) (S3).

Next, the application status update unit 40 performs the above-mentioned application status update process again (S4). Next, the matching processing unit 30 determines whether or not the failure of the player (p') strategy is confirmed based on whether or not the strategy selected by a certain player (p') matches the above-mentioned failure determination condition. (S5).

When the failure of the strategy of the player (p') is confirmed (S5: YES), the matching processing unit 30 backtracks to the search node of the player (p') (S6) and returns the processing to S3.

When the failure of the strategy of the player (p') is not confirmed (S5: NO), the matching processing unit 30 determines whether or not the strategies of all the players have been decided (S7).

When the strategies of all the players are decided (S7: YES), the matching processing unit 30 ends the processing because the search node reaches the leaves of the game tree 15 and seeks the subgame perfect equilibrium. When the strategies of all players have not been decided (S7: NO), the matching processing unit 30 returns the processing to S2.

Returning to FIG. 1, the output unit 50 uses the result data 14 stored in the storage unit 10 as a matching result by the matching processing unit 30 and the application status update unit 40, that is, a plurality of applications to a plurality of application targets. The result of the person's assignment is output by displaying it on a display device, printing it on a printing device, or outputting a file. For example, the output unit 50 displays the nursery school assigned to each child based on the result data 14. This allows the user to assign the child to the nursery school.

Here, the processing in the matching device 1 will be described while showing a specific example of the application status.

16-1 to 16-7, 18-1 to 18-4, and 20-1 to 20-5 are explanatory views for explaining a specific example of the application status. In the explanatory diagram explaining a specific example of the application status, the line connecting the child 12b to the nursery school 11a indicates the application, and if it is a dotted line, it is an application included in the applicant set (Aq), and if it is a solid line, it is confirmed. Indicates that the application is included in the applicant set (Fq).

17-1, 17-2, 19-1, and 19-2 are explanatory diagrams illustrating the search for a node. FIG. 21 is an explanatory diagram illustrating a search result of subgame perfect equilibrium.

These drawings (FIGS. 16-1 to 21) are the process (S101) until the search result of the subgame perfect equilibrium is obtained based on the cases of the application target information 11 and the applicant information 12 illustrated in FIG. ~ S151) is explained.

As shown in FIGS. 16-1 to 16-5, first, the application status update unit 40 maximizes the application based on the application target information 11 and the applicant information 12 (S101 to S105).

Specifically, as shown in FIG. 16-1, the application status update unit 40 applies for the strategy with the highest gain for the players who do not have the applied strategy for confirming success in order from the child 12b (1,4). (S101 to S105).

As shown in FIG. 16-2, in S102, since the child 12b (2, 5) applied for the nursery school 11a (A), the upper application (5, 1) of the capacity (2 people) of the nursery school 11a. Is accepted. Therefore, the success confirmation of the application (A, A) for the child 12b (1,4) is canceled, and the application status update unit 40 will make the next application for the child 12b (1,4).

As shown in FIG. 16-3, in S103, children 12b (1,4) and (2,5) are players who have applied strategies for confirming success. Therefore, the application status update unit 40 applies for children 12b (3) and (6) who do not have an applied strategy for confirming success.

As shown in FIG. 16-4, in S104, since the child 12b (1,4) is a player who does not have the applied strategy for confirming the success again, the application status update unit 40 is the child 12b (1,4). Make the next application. As a result, as shown by the dotted line in FIG. 16-5, a set of applicants (Aq) who applied for all the nursery schools 11a where each child 12b may enter is finally obtained.

Next, the application status update unit 40 searches for an application that matches the above-mentioned application confirmation condition from the applicant set (Aq), and confirms the application. Specifically, as shown in FIG. 16-6, in S106, the application of a single child 12b (3, 6) who is not a coupling applicant is confirmed. Specifically, the application for child 12b (3) is confirmed as application (B), and the application for child 12b (6) is confirmed as (C).

Next, the application status update unit 40 cancels the failure of the strategy due to the confirmation of the application. Specifically, as shown in FIG. 16-7, in S107, the application (B, B) in the child 12b (1,4) and the application (B, B) in the child 12b (2,5) are cancelled. It becomes. As a result, the dotted line (application) from the children 12b (4) and (5) to the nursery school 11a (B) is deleted.

Next, the application status update process is returned, and the matching process unit 30 searches for the node of the first player whose strategy has not been determined, based on the preference order of the player (12b) in the applicant information 12.

Specifically, as shown in FIG. 17-1, in S111, the child 12b (1,4) of the applicant 12a (I) is used as a player, and the nodes are searched according to the preference order. Here, by the previous application status update process, the application status 17 is obtained, in which the application for the child 12b (3) is the application (B) and the application for the child 12b (6) is (C). The application status 17 corresponds to the final applicant set (Fq).

Since (A, A) has the highest preference order for children 12b (1,4), as shown in FIG. 17-2, in S112, (A, A) is selected from children 12b (1,4). The node is searched. As a result, the application status 17 confirms the application for the nursery school 11a (A) by the child 12b (1,4).

Next, the application status update unit 40 performs the application status update process. Specifically, as shown in FIG. 18-1, at the start of the application status update process (S121), the child 12b (1,4) applies for the nursery school 11a (A), and the child 12b (3) applies for childcare. The application for the nursery school 11a (B) and the application for the nursery school 11a (C) by the child 12b (6) have been confirmed.

Next, the application status update unit 40 maximizes the application based on the application status of S121. Specifically, as shown in FIG. 18-2, in S122, players (2, 5, 6) who do not have an applied strategy for confirming success are applied and added to the applicant set (Aq).

Next, the application status update unit 40 searches for an application that matches the above-mentioned application confirmation condition from the applicant set (Aq), and confirms the application. Specifically, as shown in FIG. 18-3, in S123, since the strategy being applied for is applicable to one case, the application for the nursery school 11a (C) in the child 12b (2, 5) is confirmed. ..

Next, the application status update unit 40 confirms the application by newly confirming the success. Specifically, as shown in FIG. 18-4, in S124, the application for the nursery school 11a (A) in the child 12b (6) is confirmed.

Next, when the application status update process is returned, the matching processing unit 30 confirms the application to the nursery school 11a (A) in the child 12b (6), and the strategy of the child 12b (1,4) who is the player ( Since A and A) failed, backtracking is performed. Specifically, as shown in FIG. 19-1, in S131, backtracking is performed due to the failure of the strategies (A, A) of the child 12b (1,4).

Next, the matching processing unit 30 searches for another node based on the preference order in the children 12b (1,4). Specifically, as shown in FIG. 19-2, in S132, the child 12b (1,4) of the applicant 12a (I) is used as a player, and the search for the next node (C, C) according to the preference order is performed. I do.

Next, the application status update unit 40 performs the application status update process. Specifically, as shown in FIG. 20-1, at the start of the application status update process (S141), the child 12b (1,4) applies for the nursery school 11a (C), and the child 12b (3) applies for childcare. The application for the nursery school 11a (B) and the application for the nursery school 11a (C) by the child 12b (6) have been confirmed.

Next, the application status update unit 40 maximizes the application based on the application status of S121. Specifically, as shown in FIG. 20-2, in S142, players (2, 5, 6) who do not have an applied strategy for confirming success are applied and added to the applicant set (Aq).

Next, the application status update unit 40 searches for an application that matches the above-mentioned application confirmation condition from the applicant set (Aq), and confirms the application. Specifically, as shown in FIG. 20-3, in S143, the application for the nursery school 11a (A) in the child 12b (2, 6) is confirmed.

Next, the application status update unit 40 cancels the failure of the strategy due to the confirmation of the application. Specifically, as shown in FIG. 20-4, in S144, the application (A) in the child 12b (2) is cancelled. As a result, the dotted line (application) from the child 12b (2) to the nursery school 11a (A) is deleted.

Next, the application status update unit 40 searches for whether or not the application can be newly confirmed, and confirms the application. Specifically, as shown in FIG. 20-5, in S145, the application (B) in the child 12b (2) is confirmed. As a result, the dotted line from the child 12b (2) to the nursery school 11a (B) becomes a solid line.

Next, the matching processing unit 30 continues the search for the subgame perfect equilibrium based on the obtained application status 17 (fixed applicant set (Fq)). Specifically, as shown in FIG. 21, since the application status 17 that is the subgame perfect equilibrium is obtained in S151, the subgame perfect equilibrium can be easily obtained by searching along the application status 17. Can be sought.

As described above, the matching device 1 has a matching processing unit 30 and an application status update unit 40, and a plurality of applicants (children 12b) having priorities assigned to each, and priorities for each of the plurality of applicants. Matching with a plurality of application targets (nursery school 11a) with each is executed. The matching processing unit 30 is an extensive game that supports matching, and sets the priority of each of the plurality of applicants as the order of play with respect to a plurality of independent players having gains corresponding to the preferences of each of the plurality of applicants. Find the subgame perfect equilibrium of an extensive game that is associated and each of the multiple players knows the gains of all of the multiple players. Then, the matching processing unit 30 performs matching based on the result of the subgame perfect equilibrium, and obtains the result data 14. The application status update unit 40 has a gain set for each coupling applicant who has a gain in the form of a pair with a specific other applicant, and for each applicant corresponding to an individual applicant. Apply to the application target and generate application information showing a set of applications for each of the multiple application targets. In addition, the application status update unit 40 specifies an application to be confirmed from the applicants selected based on the gains of each of the plurality of applicants according to the priority order for the plurality of applicants from the generated set of application information. Perform the first process. In addition, the application status update unit 40 performs a second process of identifying the application of another applicant whose failure is confirmed as the application is confirmed. In addition, the application status update unit 40 cancels the application corresponding to the failure confirmation of other applicants, and performs the third process of identifying the application whose success is confirmed by the cancellation. In addition, the application status update unit 40 performs a fourth process of canceling an application whose gain is lower than that of the successful application of the successful applicant. Then, the application status update unit 40 repeats the first process to the fourth process until there are no more applications to be confirmed from the set of applications. As a result, even if the preference order is determined by both the applicant such as a child and the application target such as a nursery school, the matching device 1 becomes an appropriate application target in consideration of the preference order. Can be assigned.

Further, the application status update unit 40 generates application information before the process of obtaining the subgame perfect equilibrium of the expanded game by the matching processing unit 30, or in the middle of the process of obtaining the subgame perfect equilibrium. The process of repeating the process to the fourth process is performed until there are no more applications to be confirmed from the set of applications. In this way, the matching device 1 can prun the options of the game tree 15 by updating the application status prior to the process of obtaining the subgame perfect equilibrium of the expanded game. As a result, the matching device 1 can reduce the number of passes to be searched when obtaining the subgame perfect equilibrium, and can obtain the subgame perfect equilibrium while suppressing the amount of calculation.

Here, the experimental results under the following setting conditions in the matching device 1 of the present embodiment are shown in the table.
[Setting conditions]
・ Number of nursery schools: 2 to 10 facilities ・ Number of age-specific classes at each nursery school: 6 classes ・ Number of children accepted by each nursery school: 4 ・ Number of children: 48-240 ・ Children with sibling relationships Ratio: 0.4
-For each of the above parameter settings, calculate the average of the experimental results for 100 random problems.

As shown in the table of experimental results, comparing the case with pre-reading to update the application status prior to the process of finding the subgame perfect equilibrium of the extensive game and the case without pre-reading, the case with pre-reading Even if the game tree becomes large, it is possible to prevent it from becoming a long calculation time.

It should be noted that each component of each of the illustrated devices does not necessarily have to be physically configured as shown in the figure. That is, the specific form of distribution / integration of each device is not limited to the one shown in the figure, and all or part of the device is functionally or physically distributed / physically in arbitrary units according to various loads and usage conditions. Can be integrated and configured.

The various processing functions performed by the matching device 1 may be executed in whole or in any part on the CPU (or a microcomputer such as an MPU or a MCU (Micro Controller Unit)). Further, various processing functions may be executed in whole or in any part on a program analyzed and executed by a CPU (or a microcomputer such as an MPU or MCU) or on hardware by wired logic. Needless to say, it's good. Further, various processing functions performed by the matching device 1 may be executed by a plurality of computers in cooperation by cloud computing.

By the way, various processes described in the above-described embodiment can be realized by executing a program prepared in advance on a computer. Therefore, in the following, an example of a computer (hardware) that executes a program having the same function as that of the above embodiment will be described. FIG. 22 is an explanatory diagram illustrating a hardware configuration example of the matching device 1 according to the embodiment.

As shown in FIG. 22, the matching device 1 includes a CPU 101 that executes various arithmetic processes, an input device 102 that receives data input, a monitor 103, and a speaker 104. Further, the matching device 1 includes a medium reading device 105 for reading a program or the like from a storage medium, an interface device 106 for connecting to various devices, and a communication device 107 for communicating with an external device by wire or wirelessly. .. Further, the matching device 1 has a RAM 108 for temporarily storing various information and a hard disk device 109. Further, each part (101 to 109) in the matching device 1 is connected to the bus 110.

The hard disk device 109 stores a program 111 for executing various processes described in the above embodiment. Further, the hard disk device 109 stores various data 112 referred to by the program 111. The input device 102 receives, for example, input of operation information from the operator of the matching device 1. The monitor 103 displays, for example, various screens operated by the operator. For example, a printing device or the like is connected to the interface device 106. The communication device 107 is connected to a communication network such as a LAN (Local Area Network), and exchanges various information with an external device via the communication network.

The CPU 101 reads the program 111 stored in the hard disk device 109, expands it into the RAM 108, and executes it to perform various processes. The program 111 does not have to be stored in the hard disk device 109. For example, the matching device 1 may read and execute the program 111 stored in the storage medium that can be read by the matching device 1. The storage medium that can be read by the matching device 1 includes, for example, a portable recording medium such as a CD-ROM, a DVD disk, or a USB (Universal Serial Bus) memory, a semiconductor memory such as a flash memory, a hard disk drive, or the like. Further, the program may be stored in a device connected to a public line, the Internet, a LAN, or the like, and the matching device 1 may read the program from these and execute the program.

The following additional notes will be further disclosed with respect to the above embodiments.

(Appendix 1) A matching program that causes a computer to perform matching between a plurality of applicants each having a priority and a plurality of application targets each having a priority for each of the plurality of applicants.
In an extensive game corresponding to the matching, with respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants, the priority of each of the plurality of applicants can be associated with the order of play. And, each of the plurality of players knows the gains of all the plurality of players.
Matching based on the result of the subgame perfect equilibrium is performed.
For each coupling applicant who has a gain in the form of a pair with a specific other applicant, and for each applicant corresponding to an individual applicant, apply to each application target for which a gain is set, and the above Generate application information showing a set of applications for each of multiple application targets
From the generated set of application information, the first process of specifying an application to be confirmed from the applicants selected based on the gain of each of the plurality of applicants according to the priority for the plurality of applicants, and
The second process of identifying the applications of other applicants whose failures are confirmed as the application is confirmed, and
In addition to canceling the application corresponding to the failure confirmation of the other applicant, the third process of identifying the application whose success is confirmed by the cancellation, and
The first to fourth processes of the successful applicant, which is the fourth process for canceling the application whose gain is lower than that of the successful application, are repeated until there are no more applications to be confirmed from the set.
A matching program characterized by having a computer execute processing.

(Appendix 2) In the process of generating and repeating, the applicants of the application from the success confirmation to the failure confirmation are made to apply to each application target for which the gain is set, and another application is made.
The matching program according to Appendix 1, characterized in that.

(Appendix 3) The process of generating and repeating is performed prior to the process of obtaining the subgame perfect equilibrium or in the middle of the process of obtaining the subgame perfect equilibrium.
The matching program according to Appendix 1 or 2, characterized in that.

(Appendix 4) Coupling applicants who have a gain in the form of a pair with the other specific applicants are applicants who have a sibling relationship with each other.
The matching program according to any one of Supplementary note 1 to 3, wherein the matching program is characterized in that.

(Appendix 5) The matching is a matching between a plurality of prioritized children and a plurality of nursery schools with priorities for each of the plurality of children.
The matching program according to any one of Supplementary Provisions 1 to 4, wherein the matching program is characterized in that.

(Appendix 6) A matching method in which a computer executes matching between a plurality of applicants each having a priority and a plurality of application targets each having a priority for each of the plurality of applicants.
In an extensive game corresponding to the matching, with respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants, the priority of each of the plurality of applicants can be associated with the order of play. And, each of the plurality of players knows the gains of all the plurality of players.
Matching based on the result of the subgame perfect equilibrium is performed.
For each coupling applicant who has a gain in the form of a pair with a specific other applicant, and for each applicant corresponding to an individual applicant, apply to each application target for which a gain is set, and the above Generate application information showing a set of applications for each of multiple application targets
From the generated set of application information, the first process of specifying an application to be confirmed from the applicants selected based on the gain of each of the plurality of applicants according to the priority for the plurality of applicants, and
The second process of identifying the applications of other applicants whose failures are confirmed as the application is confirmed, and
In addition to canceling the application corresponding to the failure confirmation of the other applicant, the third process of identifying the application whose success is confirmed by the cancellation, and
The first to fourth processes of the successful applicant, which is the fourth process for canceling the application whose gain is lower than that of the successful application, are repeated until there are no more applications to be confirmed from the set.
A matching method characterized by the processing being performed by a computer.

(Appendix 7) In the process of generating and repeating, the applicants of the application whose success is confirmed to the failure is confirmed are applied to each application target for which the gain is set, and another application is made.
The matching method according to Appendix 6, characterized in that.

(Appendix 8) The process of generating and repeating is performed prior to the process of obtaining the subgame perfect equilibrium or in the middle of the process of obtaining the subgame perfect equilibrium.
The matching method according to Appendix 6 or 7, characterized in that.

(Appendix 9) Coupling applicants who have a gain in the form of a pair with the other specific applicants are applicants who have a sibling relationship with each other.
The matching method according to any one of Supplementary Provisions 6 to 8, wherein the matching method is characterized by the above.

(Appendix 10) The matching is a matching between a plurality of prioritized children and a plurality of nursery schools with priorities for each of the plurality of children.
The matching method according to any one of Supplementary Provisions 6 to 9, wherein the matching method is characterized by the above.

(Appendix 11) A matching device that executes matching between a plurality of applicants each having a priority and a plurality of application targets each having a priority for each of the plurality of applicants.
In an extensive game corresponding to the matching, with respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants, the priority of each of the plurality of applicants can be associated with the order of play. In addition, the matching processing unit that obtains the subgame perfect equilibrium of the expanded game in which each of the plurality of players knows the gains of all the plurality of players and performs matching based on the result of the subgame perfect equilibrium.
For each coupling applicant who has a gain in the form of a pair with a specific other applicant, and for each applicant corresponding to an individual applicant, apply to each application target for which a gain is set, and the above Application information indicating a set of applications for each of the plurality of application targets is generated, and from the generated set of application information, the gains of the plurality of applicants are obtained according to the priority for the plurality of applicants. For the first process of identifying the application to be confirmed from the applicants selected based on the application, the second process of specifying the application of another applicant whose failure is confirmed due to the application confirmation, and the failure confirmation of the other applicant. The third process of canceling the corresponding application and specifying the application whose success is confirmed by the cancellation, and the fourth process of canceling the application of the applicant whose success is confirmed and whose gain is lower than that of the application whose success is confirmed. The application status update unit that repeats the first to fourth processes of the above until there are no more applications to be confirmed from the set.
A matching device characterized by having.

(Appendix 12) The application status update department applies to each application target for which a gain has been set for applicants whose success is confirmed to failure is confirmed, and another application is made.
The matching device according to Appendix 11, wherein the matching device is characterized in that.

(Appendix 13) The application status update unit performs the first to fourth processes in the set prior to the process of obtaining the subgame perfect equilibrium or in the middle of the process of obtaining the subgame perfect equilibrium. The matching device according to Appendix 11, wherein the matching device is repeated until there are no more applications to be confirmed.

(Appendix 14) Coupling applicants who have a gain in the form of a pair with the specific other applicants are applicants who have a sibling relationship with each other.
The matching device according to Appendix 11 or 13, wherein the matching device is characterized in that.

(Appendix 15) The matching is a matching between a plurality of prioritized children and a plurality of nursery schools with priorities for each of the plurality of children.
The matching device according to any one of Supplementary note 11 to 14, wherein the matching device is characterized in that.

1 ... Matching device 10 ... Storage unit 11 ... Application target information 11a ... Nursery school 12 ... Applicant information 12a ... Applicant 12b ... Child 13 ... Calculation data 14 ... Result data 15 ... Game tree 15a, 15b ... Pass 16 ... Strategic result 17 ... Application status 20 ... Input unit 30 ... Matching processing unit 40 ... Application status update unit 50 ... Output unit 101 ... CPU
102 ... Input device 103 ... Monitor 104 ... Speaker 105 ... Media reader 106 ... Interface device 107 ... Communication device 108 ... RAM
109 ... Hard disk device 110 ... Bus 111 ... Program 112 ... Various data C1 ... Case

Claims (7)

It is a matching program that causes a computer to perform matching between a plurality of applicants each having a priority and a plurality of application targets each having a priority for each of the plurality of applicants.
In an extensive game corresponding to the matching, with respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants, the priority of each of the plurality of applicants can be associated with the order of play. And, each of the plurality of players knows the gains of all the plurality of players.
Matching based on the result of the subgame perfect equilibrium is performed.
For each coupling applicant who has a gain in the form of a pair with a specific other applicant, and for each applicant corresponding to an individual applicant, apply to each application target for which a gain is set, and the above Generate application information showing a set of applications for each of multiple application targets
From the generated set of application information, the first process of specifying an application to be confirmed from the applicants selected based on the gain of each of the plurality of applicants according to the priority for the plurality of applicants, and
The second process of identifying the applications of other applicants whose failures are confirmed as the application is confirmed, and
In addition to canceling the application corresponding to the failure confirmation of the other applicant, the third process of identifying the application whose success is confirmed by the cancellation, and
The first to fourth processes of the successful applicant, which is the fourth process for canceling the application whose gain is lower than that of the successful application, are repeated until there are no more applications to be confirmed from the set.
A matching program characterized by having a computer execute processing. In the process of generating and repeating, the applicants of the application from the success confirmation to the failure confirmation are made to apply to each application target for which the gain is set, and another application is made.
The matching program according to claim 1. The process of generating and repeating is performed prior to the process of obtaining the subgame perfect equilibrium or in the middle of the process of obtaining the subgame perfect equilibrium.
The matching program according to claim 1 or 2. Coupling applicants who have a gain in the form of a pair with the specific other applicants are applicants who have a sibling relationship with each other.
The matching program according to any one of claims 1 to 3, wherein the matching program is characterized in that. The matching is a matching between a plurality of prioritized children and a plurality of nursery schools with priorities for each of the plurality of children.
The matching program according to any one of claims 1 to 4, wherein the matching program is characterized in that. This is a matching method in which a computer executes matching between a plurality of applicants each having a priority and a plurality of application targets each having a priority for each of the plurality of applicants.
In an extensive game corresponding to the matching, with respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants, the priority of each of the plurality of applicants can be associated with the order of play. And, each of the plurality of players knows the gains of all the plurality of players.
Matching based on the result of the subgame perfect equilibrium is performed.
For each coupling applicant who has a gain in the form of a pair with a specific other applicant, and for each applicant corresponding to an individual applicant, apply to each application target for which a gain is set, and the above Generate application information showing a set of applications for each of multiple application targets
From the generated set of application information, the first process of specifying an application to be confirmed from the applicants selected based on the gain of each of the plurality of applicants according to the priority for the plurality of applicants, and
The second process of identifying the applications of other applicants whose failures are confirmed as the application is confirmed, and
In addition to canceling the application corresponding to the failure confirmation of the other applicant, the third process of identifying the application whose success is confirmed by the cancellation, and
The first to fourth processes of the successful applicant, which is the fourth process for canceling the application whose gain is lower than that of the successful application, are repeated until there are no more applications to be confirmed from the set.
A matching method characterized by the processing being performed by a computer. It is a matching device that executes matching between a plurality of applicants each having a priority and a plurality of application targets each having a priority for each of the plurality of applicants.
In an extensive game corresponding to the matching, with respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants, the priority of each of the plurality of applicants can be associated with the order of play. In addition, the matching processing unit that obtains the subgame perfect equilibrium of the expanded game in which each of the plurality of players knows the gains of all the plurality of players and performs matching based on the result of the subgame perfect equilibrium.
For each coupling applicant who has a gain in the form of a pair with a specific other applicant, and for each applicant corresponding to an individual applicant, apply to each application target for which a gain is set, and the above Application information indicating a set of applications for each of the plurality of application targets is generated, and from the generated set of application information, the gains of the plurality of applicants are obtained according to the priority for the plurality of applicants. For the first process of identifying the application to be confirmed from the applicants selected based on the application, the second process of specifying the application of another applicant whose failure is confirmed due to the application confirmation, and the failure confirmation of the other applicant. The third process of canceling the corresponding application and specifying the application whose success is confirmed by the cancellation, and the fourth process of canceling the application of the applicant whose success is confirmed and whose gain is lower than that of the application whose success is confirmed. The application status update unit that repeats the first to fourth processes of the above until there are no more applications to be confirmed from the set.
A matching device characterized by having.

Images