JP6973746B2 - 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, a Serial dictatorship mechanism (hereinafter referred to as SD mechanism) is known in a matching process in which a large number of applicants (for example, children of parents who wish to have childcare) are assigned to application targets (for example, childcare institutions). In the SD mechanism, applicants are prioritized, and applicants with the highest priority are assigned to the remaining application targets at that time. This SD mechanism guarantees that priority inversion does not occur.

Svensson, Lars-Gunnar. "Strategy-proof allocation of indivisible goods." Social Choice and Welfare 16.4 (1999): 557-567.

However, in the above-mentioned conventional technique, there is a problem that it is difficult to appropriately assign to the application target when the applicant includes an applicant who requests coupling.

For example, when applying to multiple nursery schools, parents may request the coupling of siblings (brothers, siblings, siblings, sisters). Since the SD mechanism is not a mechanism that considers applicants with sibling coupling requests, appropriate matching results (assignments) may not be obtained when including applicants with sibling coupling requests. .. For example, one of the following problems 1 to 3 may occur in matching.

Problem 1: There is a person with a lower priority than me in the nursery school I want to enter (regardless of only child / sibling).
Problem 2: As a sibling, a person whose priority is lower than that of himself (not necessarily a sibling) is in the nursery school of his choice.
Problem 3: Even if the nursery school has a lower preference, it is better for the siblings to enter the same nursery school than to enter different nursery schools according to their individual priorities, but the siblings enter different nursery schools. ing.

19 to 21 are explanatory views illustrating the first to third cases. In the examples of FIGS. 19 to 21, the applicant 202a is matched with the application target 201a based on the same application target information 201 and the applicant information 202.

The application target information 201 is information about the application target 201a in which the number of people accepted in the application target 201a (nursery school in the illustrated example) is set in advance. In the illustrated example, the acceptance of two people is set at each of the nursery schools of "S1" to "S3".

The applicant information 202 is information preset for the applicant 202a (child in the illustrated example) for each parental application. Specifically, the applicant information 202 is a score for determining the priority for each child ID that identifies the child to be applied in the application ID indicating the application, and a desired order indicating the order of the desired application target 201a. And are set. For example, the applicant 202a is given a priority in descending order of the score in the applicant information 202. When a plurality of child IDs are included in the same application ID, it is assumed that the children have a sibling relationship with each other and there is a coupling request between the children.

As shown in FIG. 19, in the first case C1, the sibling relationship (coupling request) is ignored, and the applicant 202a is applied to the application target 201a by the SD mechanism based on the application target information 201 and the applicant information 202. I will assign it to. Specifically, the application target 201a desired by the applicant 202a is assigned in order from the applicant 202a having the highest priority (in the order of I1, J1, K1, K2, L1, I2 in the illustrated example) (S201 to S206). ).

As described above, in the first case C1 in which the coupling request is ignored and the allocation is performed by the SD mechanism, the problem 3 occurs. Specifically, even in a nursery school with a low desired order (for example, S2), the siblings of K1 and K2 do not enter the same nursery school but enter different nursery schools.

As shown in FIG. 20, in the second case C2, allocation is performed in a form summarized by a sibling relationship (coupling request) (S211 to S214). In the second case C2, when summarized in a sibling relationship, the scores of the coupled children are matched to the higher score.

As shown in FIG. 21, the third case C3 is also assigned in the form of a sibling relationship (coupling request) (S221 to S224). In the third case C3, when summarized in a sibling relationship, the scores of the coupled children are matched to the lower score.

As described above, in the second case C2 and the third case C3 in which the allocation is performed in a form collectively according to the coupling request, the individual prioritization is distorted, which causes a problem 1. Specifically, in the second case C2, the applicant 202a of I2, which has a lower priority than L1, is assigned to the desired application target 201a (S1 in the illustrated example), and the priority is reversed. .. Further, in the third case C3, the applicants 202a of K1 and K2 having a lower priority than I1 are assigned to the desired application target 201a (S1 in the illustrated example), and the priority is reversed.

In this way, when the sibling relationship (coupling request) is ignored and the SD mechanism is used for allocation, problem 3 frequently occurs. In addition, when the siblings are assigned in the form of a collection (according to the coupling request), problem 1 frequently occurs.

In order to minimize these problems, if you try to search for matching in the form of siblings, if the preconditions for matching change, such as the number of applicants for each class by age is fixed. , It becomes difficult to obtain stable matching. In addition, the amount of calculation is enormous.

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 reduce the amount of calculation and request an appropriate allocation to an application target.

In the first plan, the matching program causes a computer to perform matching between a plurality of applicants each having a priority and a plurality of application targets. The matching program causes the computer to execute a process of performing matching and a process of determining. The matching process is an extensive game that supports matching, and priorities can be associated with the order of play for multiple independent players with gains corresponding to the preferences of each of the multiple applicants. Multiple players each know the gains of all of the multiple players. Find the subgame perfect equilibrium of an extensive game. In addition, the matching process performs matching based on the result of subgame perfect equilibrium. The gain of a player corresponding to a coupling request applicant who has a coupling request requesting matching in a pair with another specific applicant is set according to whether or not the coupling request is satisfied. The process of deciding is to determine whether or not to prun the options in the player's turn corresponding to the coupling request applicant for the game tree options corresponding to the partial game of the expansive game. Refer to and decide. In addition, the process of determining is to refer to the application target upper bound information and the application target lower bound information indicating the upper and lower bounds of the application target for which matching has not been established for each turn of the plurality of players. It is determined whether or not the matching is established in the above and whether or not the player can be matched. In addition, the process of determining updates the application target lower bound information when it is determined that there is a matching possibility, and updates the application target upper bound information and the application target lower bound information when it is determined that the matching is established.

According to one embodiment of the present invention, it is possible to reduce the amount of calculation and obtain 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 illustrating application target information and applicant information. FIG. 3 is an explanatory diagram illustrating the result data. FIG. 4 is an explanatory diagram illustrating a gain table. FIG. 5 is an explanatory diagram illustrating a game tree. FIG. 6 is an explanatory diagram illustrating subgame perfect equilibrium. FIG. 7 is a flowchart showing an example of the matching process. FIG. 8 is an explanatory diagram illustrating a specific example of the matching process. FIG. 9 is an explanatory diagram illustrating a specific example of the matching process. FIG. 10 is an explanatory diagram illustrating a specific example of the matching process. FIG. 11 is an explanatory diagram illustrating an example of the look-ahead process. FIG. 12 is an explanatory diagram illustrating a specific example of the matching process after the look-ahead process. FIG. 13 is an explanatory diagram illustrating a gain table according to the second embodiment. FIG. 14 is an explanatory diagram illustrating an example of the look-ahead processing according to the second embodiment. FIG. 15 is an explanatory diagram illustrating a specific example of the matching process according to the second embodiment. FIG. 16 is an explanatory diagram illustrating a comparative example of the look-ahead process. FIG. 17 is an explanatory diagram illustrating a comparative example of the matching process. FIG. 18 is an explanatory diagram illustrating a hardware configuration example of the matching device according to the embodiment. FIG. 19 is an explanatory diagram illustrating the first case. FIG. 20 is an explanatory diagram illustrating the second case. FIG. 21 is an explanatory diagram illustrating a third case.

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 do not limit the embodiments. 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 performs matching processing between a plurality of applicants each having a priority and a plurality of application targets, and outputs the obtained 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 the guest and the application target may be the 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, a selection determination 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 processing at the time of calculation by the matching processing unit 30 and the option determination unit 40. The result data 14 showing the matching result calculated by the unit 30 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 input by the input unit 20 and set in advance.

FIG. 2 is an explanatory diagram illustrating application target information 11 and applicant information 12. As shown in FIG. 2, the application target information 11 is set with the number of people accepted for each nursery school (application target) identified by the nursery school ID. At each nursery school, the number of people accepted is set for each age-specific class (0-year-old class, 1-year-old class).

In the applicant information 12, a preference list showing the order of the desired nursery school, an age, and a priority for assignment are set for each child (applicant) identified by the child ID.

If the same application ID includes a plurality of child IDs in the applicant information 12, for example, the children have a sibling (brother, brother / sister, sibling, sister) relationship, and the coupling request between the children. Suppose there is. The coupling request is a request for allocation (matching) to the application target (nursery school) in a bundled form.

For example, it is assumed that a1 and a0 and b1 and b0 have a sibling relationship with each other and are applicants who request each other's coupling (coupling request applicant). A1 and a0 and b1 and b0 are desired to be assigned (matched) to the application target (nursery school) in a combined form by the guardian who is the applicant.

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 option determination unit 40. For example, the arithmetic data 13 includes a gain table, data related to a search for a game tree (details will be described later), and the like.

The result data 14 is data showing the assignment result of the applicant (child) to the application target (nursery school) calculated by the matching process by the matching processing unit 30 and the option determination 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 ID indicating the child and the nursery school ID indicating the nursery school 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 process 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.

An extensive game is 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.

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 are Nash equilibrium in all partial games (every player chooses the best strategy for the strategies of other players).

The matching processing unit 30 makes each of the plurality of applicants (children) 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 a nursery school). Virtualize an 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 the nodes. That is, all players know all the information about the game (assignment) (mutual priority, age, sibling relationship (whether or not there is a coupling request), preference list and number of people accepted in each nursery / age class). It is assumed that it is.

First, the matching processing unit 30 sets a gain table according to the strategy for each player (child) corresponding to the applicant based on the applicant information 12. This gain table is set according to the preference list in the applicant information 12 and the presence / absence of a coupling request.

Specifically, for each player's strategy (option), the gain is set higher in the order of the preference list. Further, for a coupling request applicant having a coupling request requesting matching in a paired form, a high gain is set when the coupling request is satisfied.

FIG. 4 is an explanatory diagram illustrating a gain table. As shown in FIG. 4, for applicants (c0, d1) who do not have a coupling request, gain tables 15B and 15C with higher gains are set in the order of preference list. In addition, N / A indicates the case where the nursery school in the preference list could not be reserved.

Further, for the coupling request applicants (a1, a0, b1, b0), the gain table 15A in which the gain is increased in the order according to the following cases 1 to 3 is set.
1. 1. If the siblings select the same nursery school (in addition, the selected nursery school will be ranked higher in the preference list).
2. 2. If the siblings select a different nursery school (further, the selected nursery school will be ranked higher in the preference list).
3. 3. If you could not book a nursery school in your preference list

For example, when siblings select the same nursery school, the gain values are set to "6", "5", and "4" in the order of preference list (s → t → u). Next, when different siblings are selected, the gain values are set to "3", "2", and "1" in the order of preference list (s → t → u). Next, when the nursery school in the preference list cannot be reserved (N / A), the gain value is set to "0".

Next, the matching processing unit 30 plays (selects an option) for each player in the same order as the priority of the child (in the order of a1, b1, c0, b0, a0, d1 in the example of FIG. 4). The strategy of each player is that the number of nursery schools in the application target information 11 has not reached the capacity from the nursery schools in their preference list (the number of selections of the players with the highest order has not reached the number of accepted numbers). Is to choose. However, if any desired nursery school (all nursery schools included in the preference list) has reached the capacity, nothing will be done.

At this time, the matching processing unit 30 selects, based on the gain tables 15A to 15C, the option having the highest gain value and achieving Nash equilibrium in each player's play. As a result, the matching processing unit 30 is the first path to reach the leaves (end phase) along the tree structure of the game tree, and searches for a path that is in Nash equilibrium (hereinafter, equilibrium path), that is, the subgame perfect equilibrium. Find the equilibrium.

FIG. 5 is an explanatory diagram illustrating a game tree. As shown in FIG. 5, the game tree 16 uses the aspects of each player (a1, b1, c0, b0, a0, d1) as nodes in the same order as the priority of the children, and each player's choices (s, t). , U) is a tree structure with branches. That is, the game tree 16 corresponds to a partial game of an extensive game corresponding to matching between a plurality of applicants (a1, b1, c0, b0, a0, d1) and a plurality of application targets (s, t, u). It is a game tree.

FIG. 6 is an explanatory diagram illustrating subgame perfect equilibrium. As shown in FIG. 6, the matching processing unit 30 searches for an equilibrium path (thick line) that is Nash equilibrium among the paths from the top node (a1) in the game tree 16 to the leaves (d1). Subgame perfect equilibrium is sought.

Here, playing in the same order as the child's priority corresponds to assigning the nursery school from the child with the highest priority in the SD mechanism. And for children without siblings (no coupling requirements), the choice to maximize gain is always made (matching the behavior of the SD mechanism). In addition, for children who have a relationship with each other (coupling request applicants), the gain table 15A, which sets the gain value corresponding to the presence or absence of the coupling, reflects the preference regarding the coupling as the gain value of the game. Then, the selection for maximum gain is made.

In this way, the selection that maximizes the gain of each player contributes to the stable matching between a plurality of applicants and a plurality of application targets. Then, the matching processing unit 30 searches for an equilibrium path (thick line) that becomes a Nash equilibrium, and finds a subgame perfect equilibrium, which is appropriate according to the preferences of a plurality of applicants (preference list, presence / absence of coupling). The result (result data 14) of assigning applicants to the application target can be obtained.

Returning to FIG. 1, the option determination unit 40 determines whether or not the option of the game tree of the extensive game in the matching process of the matching process unit 30 is pruned in the turn of the player corresponding to the coupling request applicant. Ring request Determined by referring to the content of the applicant's coupling request. That is, the option determination unit 40 is an example of the determination unit.

For example, whether or not the final gain determined for one strategy (option) selected by the applicant for the coupling request satisfies the coupling request (for example, when the sibling strategies are the same / different). There are two ways. Therefore, the other can be classified according to whether or not the gain is expected to satisfy the coupling requirement. After dividing the case, the gain is determined in one way. Utilizing this, the option determination unit 40 selects an option having a gain expected to satisfy the coupling requirement on the other side. Then, the option determination unit 40 backtracks and removes the disappointing option when the expected gain is not obtained and the expectation is disappointing. In this way, after the gain is determined in one way, the option determination unit 40 determines that the option is pruned in the player's turn corresponding to the coupling request applicant.

For example, the option determination unit 40 initially determines the option with the maximum gain among those expected to satisfy the coupling request in the turn of the player corresponding to the coupling request applicant. Next, in the turn of the player corresponding to the other low-priority coupling request applicant, there may be no option to satisfy the coupling request depending on the conditions such as the number of people accepted by the nursery school.

In such a case, it turns out that the option selected in anticipation of satisfying the coupling request in the turn of the player corresponding to the high priority coupling request applicant is disappointing. Therefore, if the option determination unit 40 cannot select an option that satisfies the coupling request in the turn of the player corresponding to the other coupling request applicant having a low priority, the option determination unit 40 responds to the coupling request applicant having a high priority. Backtrack to the player's turn and remove the disappointing options.

In this way, the option determination unit 40 prunes the options in the game tree 16. Since the number of paths to be searched can be reduced by this pruning, the matching processing unit 30 can reduce the calculation cost for obtaining the subgame perfect equilibrium.

Here, the details of the matching process will be described by the matching processing unit 30 and the option determination unit 40. FIG. 7 is a flowchart showing an example of the matching process.

As shown in FIG. 7, when the processing is started, the matching processing unit 30 initializes the variable (i) corresponding to the player order of the matching processing (i ← 1) (S1).

Next, the matching processing unit 30 selects a strategy in which the player i may bring the maximum gain to himself / herself based on the gain tables 15A to 15C (S2). Here, in the turn of the player corresponding to the coupling request applicant, the strategy of the gain expected to satisfy the coupling request is selected.

Next, the option determination unit 40 determines whether or not it is determined that the player j (j <i) having a higher priority than the player i cannot achieve the expected gain (S3). For example, if the player i's turn corresponding to the other low-priority coupling request applicant cannot select an option that satisfies the coupling request, the player j corresponding to the high-priority coupling request applicant is expected. It is determined that the desired gain cannot be achieved.

When it is determined that the expected gain cannot be achieved by the player j (S3: YES), the option determination unit 40 backtracks the matching process in the matching process unit 30 to the node of the player j (S7). Then, the option determination unit 40 removes the strategy (option) determined that the expected gain cannot be achieved, sets i ← j (S8), and returns the process to S2. As a result, the matching processing unit 30 selects the strategy after removing the disappointing strategy from the turn of the player who backtracked and returned the turn.

When it is not determined that the expected gain cannot be achieved by the player j (S3: NO), the matching processing unit 30 determines whether or not the player i is the last player (the lowest priority applicant). Judgment (S4).

In the case of the last player (S4: YES), since the equilibrium path leading to the leaf (end phase) along the tree structure of the game tree is found, the matching processing unit 30 ends the processing.

If it is not the last player (S4: NO), the matching processing unit 30 creates a node of the player (i + 1) whose priority corresponds to the next applicant (S5), sets i ← i + 1 (S6), and goes to S2. Return the process.

Here, a specific example of the above matching process will be described. The sample data of the specific example described below shall be based on the values of the application target information 11 and the applicant information 12 in FIG. The game tree and subgame perfect equilibrium in the sample data shall be in accordance with FIGS. 5 and 6.

8 to 10 are explanatory views illustrating a specific example of the matching process. In addition, in the application target information 11 corresponding to each step (S10 to S14, S20 to S23, S30 to S35) in FIGS. 8 to 10, the 0-year-old class and the 1-year-old class at each nursery school (s, t, u). By selecting the player, the number of acceptances shall be reduced.

As shown in FIG. 8, the matching processing unit 30 also includes gain tables 15A to 15C in order from the player corresponding to the applicant with the highest priority (in the order of a1, b1, c0, b0, a0, d1). In addition, the player selects a strategy that may bring the maximum gain to himself (S10 to S13).

Specifically, in the turn of the player of a1, aiming for a maximum gain of 6 (selection of s) in the expectation of selecting a strategy that satisfies the coupling requirement with the turn of a0, which is related to the sibling (S10). .. Next, in the turn of the player of b1, the player aims for a maximum gain of 5 (selection of t) in the expectation of selecting a strategy that satisfies the coupling requirement with the turn of b0, which is related to the sibling (S11).

Next, in the turn of the player of c0, the optimum strategy (selection of s) is determined on the spot because there is no sibling relationship (S12). Then, in the turn of the player of b0, the strategy (selection of t) as expected of b1 can be performed. Therefore, it is determined that b1 can obtain the gain "5". Further, up to this point, it is determined that the subgames in the order of b1 or less are equilibrium paths (S13).

Next, in the turn of a0, the strategy (selection of s) as expected of a1 cannot be performed. In this case, it is determined that the player of a1 cannot obtain the gain "6". Therefore, the option determination unit 40 excludes the strategy of acquiring the gain “6” (selection of s) from the strategy of the player of a1, and backtracks to the turn of the player of a1 (S14).

As shown in FIG. 9, the matching processing unit 30 selects a strategy in which the player may bring the maximum gain to himself / herself from the turn of the player a1 after backtracking (S20 to S22). However, in the turn of the player of a1, the strategy (selection of s) for acquiring the gain "6" is excluded.

Specifically, in the turn of the player of a1, aiming for a maximum gain of 5 (selection of t) in the expectation of selecting a strategy that satisfies the coupling requirement with the turn of a0, which is related to the sibling (S20). .. Next, in the turn of the player of b1, the player aims for a maximum gain of 6 (selection of s) in the expectation of selecting a strategy that satisfies the coupling requirement with the turn of b0, which is related to the sibling (S21).

Next, in the turn of the player of c0, the optimum strategy (selection of s) is determined on the spot because there is no sibling relationship (S22).

Next, in the turn of the player of b0, the strategy (selection of s) as expected of b1 cannot be performed. In this case, it is determined that the player of b1 cannot obtain the gain "6". Therefore, the option determination unit 40 excludes the strategy of acquiring the gain “6” (selection of s) from the strategy of the player of b1 and backtracks to the turn of the player of b1 (S23).

As shown in FIG. 10, the matching processing unit 30 selects a strategy in which the player may bring the maximum gain to himself / herself from the turn of the player of b1 after backtracking (S30 to S35). However, in the turn of the player of b1, the strategy (selection of s) for acquiring the gain "6" is excluded.

Specifically, in the turn of the player of b1, aiming for a maximum gain of 4 (selection of u) in the expectation of selecting a strategy that satisfies the coupling requirement with the turn of b0, which is related to the sibling (S30). .. Next, in the turn of the player of c0, the optimum strategy (selection of s) is determined on the spot because there is no sibling relationship (S31). In the turn of the player of b0, the strategy (selection of u) as expected of b1 can be performed. Therefore, it is determined that b1 can obtain the gain "4". Further, up to this point, it is determined that the subgames in the order of b1 or less are equilibrium paths (S32).

Next, in the turn of the player of a0, the strategy (selection of t) as expected of a1 can be performed. Therefore, it is determined that a1 can obtain the gain “5”. Further, up to this point, it is determined that the subgames in the order of a1 or less are equilibrium paths (S33).

Next, in the turn of the player of d1, since there is no sibling relationship, the optimum strategy (selection of s) is determined on the spot (S34). Since d1 is the last player, the equilibrium path of the entire game is determined (S35).

The option determination unit 40 may perform a look-ahead process of pre-reading the behavior of a player whose optimal strategy is clear, and may perform pruning of the options in the game tree 16 based on the pre-reading action result of the player. This look-ahead process may be executed prior to the search for the balanced path in the matching processing unit 30, or may be executed during the search for the balanced path.

For example, applicants other than coupling request applicants can simply seek their own gain, so that the optimal strategy becomes clear. Therefore, the option determination unit 40 executes the turn of the player corresponding to the applicant other than the coupling request applicant before the player corresponding to the coupling request applicant. Then, the option determination unit 40 excludes the strategy that the coupling request applicant cannot select due to the strategy of the player corresponding to the applicant other than the coupling request applicant.

FIG. 11 is an explanatory diagram illustrating an example of the look-ahead process. FIG. 12 is an explanatory diagram illustrating a specific example of the matching process after the look-ahead process.

In the example of the pre-reading process and the matching process after the pre-reading process described below, the values of the application target information 11 and the applicant information 12 in FIG. 4 are used as samples. The game tree and subgame perfect equilibrium shall be in accordance with FIGS. 5 and 6. Further, in the application target information 11 corresponding to each step (S40 to S43, S50 to S56) in FIGS. 11 and 12, the player selects a 0-year-old class and a 1-year-old class at each nursery school (s, t, u). By doing so, the number of acceptances shall be reduced.

As shown in FIG. 11, the option determination unit 40 is the turn of the player corresponding to the applicant (c0, d1) other than the coupling request applicant than the player (a1, b1) corresponding to the coupling request applicant. Is executed first (S40 to S43).

Specifically, the option determination unit 40 skips the turn of the player (a1, b1) corresponding to the coupling request applicant (S40). Next, the option determination unit 40 executes the turn of c0. Here, since c0 should be selected if there is a vacancy in the 0-year-old frame of the strategy (s), when the upper bound (acceptance number) of the 0-year-old class of the nursery school (s) is 1 or more. Decreases by 1 (S41).

From the execution result of the turn of c0, it is certain that the strategy (s) cannot be selected in the turns of b0 and a0 (S42). Therefore, the option determination unit 40 excludes the selection of the strategy (s) in the turns of b0 and a0 based on the execution result of the turn of c0.

Then, the option determination unit 40 executes the turn of d1. Here, d1 should select if there is a vacancy in the 1-year-old frame of the strategy (s), so when the upper bound (acceptance number) of the 1-year-old class of the nursery school (s) is 1 or more. Decreases by 1 (S43).

As shown in FIG. 12, the above-mentioned look-ahead process prunes the options in the game tree 16. Specifically, the selection of the strategy (s) in the turn of b0 and a0 is excluded. Due to this exclusion, in the gain table 15Aa of a1 and b1, s is not included in the strategy of siblings (b0, a0). Further, in the gain table 15Ab of b0 and a0, s is not included in one's strategy.

Therefore, in the matching process after the look-ahead process, the process is started with s excluded from the strategies of b0 and a0. Specifically, the matching processing unit 30 performs the gain tables 15Aa, 15Ab, 15B, 15C in order from the player corresponding to the applicant with the highest priority (in the order of a1, b1, c0, b0, a0, d1). Based on the above, the player selects a strategy that may bring the maximum gain to himself (S50 to S56).

In the turn of the player of a1, aiming for a maximum gain of 5 (selection of t) in the expectation of selecting a strategy that satisfies the coupling requirement with the turn of a0, which is related to the sibling (S50). Next, in the turn of the player of b1, the player aims for a maximum gain of 4 (selection of u) in the expectation of selecting a strategy that satisfies the coupling requirement with the turn of b0, which is related to the sibling (S51).

Next, in the turn of the player of c0, the optimum strategy (selection of s) is determined on the spot because there is no sibling relationship (S52). Then, in the turn of the player of b0, the strategy (selection of u) as expected of b1 can be performed. Therefore, it is determined that b1 can obtain the gain "4". Further, up to this point, it is determined that the subgames in the order of b1 or less are equilibrium paths (S53).

Next, in the turn of the player of a0, the strategy (selection of t) as expected of a1 can be performed. Therefore, it is determined that a1 can obtain the gain “5”. Further, up to this point, it is determined that the subgames in the order of a1 or less are equilibrium paths (S54).

Next, in the turn of the player of d1, since there is no sibling relationship, the optimum strategy (selection of s) is determined on the spot (S55). Since d1 is the last player, the equilibrium path of the entire game is determined (S56).

In this way, by performing the look-ahead process by the option determination unit 40, the number of passes to be searched for when obtaining the subgame perfect equilibrium can be further reduced, and the amount of calculation can be suppressed.

Returning to FIG. 1, the output unit 50 has a matching result by the matching processing unit 30 and the option determination unit 40 based on the result data 14 stored in the storage unit 10, that is, a plurality of applicants to a plurality of application targets. The allocation result of is output by display on the display device, printing on the printing device, file output, etc. 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.

As described above, the matching device 1 is a device that executes matching between a plurality of applicants each having a priority and a plurality of application targets, and has a matching processing unit 30 and an option determination unit 40. The matching processing unit 30 is an extensive game corresponding to matching, and the priority is associated with the order of play with respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants. Multiple players each know the gains of all of the multiple players. Find the subgame perfect equilibrium of an extensive game. Then, the matching processing unit 30 performs matching based on the result of the subgame perfect equilibrium, and obtains the result data 14. Further, the matching processing unit 30 has a coupling request for matching with a specific other applicant. The gain of the player corresponding to the coupling request applicant is whether or not the coupling request is satisfied. Set according to. The option determination unit 40 determines whether or not the option is pruned in the player's turn corresponding to the coupling request applicant for the game tree options corresponding to the partial game of the extensive game in the matching processing unit 30. Determined by referring to the content of the coupling request in.

In this way, the matching device 1 applies for an appropriate application target according to the preferences of a plurality of applicants (preference list, presence / absence of coupling) by obtaining the subgame perfect equilibrium of the expanded game corresponding to the matching. The result (result data 14) to which the person is assigned can be obtained. Further, the matching device 1 can reduce the number of paths to be searched when obtaining the subgame perfect equilibrium by pruning the options of the game tree, and can obtain the subgame perfect equilibrium by 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 a relationship Ratio: 0.4
・ Preference list length: 2-10
-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, in the matching quality of the present embodiment, it is possible to obtain a stable matching result in which the occurrence of the problems 2 and 3 is suppressed as much as possible without causing the above-mentioned problem 1. Moreover, even if the game tree becomes large, it is possible to prevent the calculation time from becoming long. Further, when the look-ahead processing is performed, the calculation time can be further shortened even when the game tree becomes large as compared with the case where the look-ahead processing is not performed.

(Second embodiment)
In the above embodiment (first embodiment), the number of applicants (nursery school) accepted in the turn in the look-ahead process of pre-reading the behavior of the player whose optimal strategy is clear for each turn of the plurality of players. The upper bound was used to determine whether or not to prun the options. On the other hand, in the second embodiment, in the look-ahead process of each of the plurality of players, the upper bound of the application target and the lower bound of the application target are used to determine whether or not to prun the options.

Here, the upper bound of the application target is the upper limit of the number of accepted applications (vacant number) estimated in each turn of the plurality of players. In other words, in each of the multiple players' turns, there is at most a vacancy in the upper bound of the application target. The lower bound of the application target is the lower limit of the number of accepted applications (vacant number) estimated in each turn of the plurality of players. In other words, in each of the multiple players' turns, there is at least a vacancy in the lower world of the application target.

In the second embodiment, the option determination unit 40 manages the application target upper bound information indicating the upper bound of the application target and the application target lower bound information indicating the lower bound of the application target in a memory or the like. Then, the option determination unit 40 refers to the upper bound information of the application target and the lower limit information of the application target in the look-ahead processing of each of the plurality of players, and determines whether or not matching is established in the turn and whether or not there is a possibility of matching of the players. judge.

Specifically, the option determination unit 40 has 0 upper and lower bounds for the application in each of the plurality of players, and if there is no vacant space for the application, the application target (nursery school) in the turn. It is judged that there is no possibility of matching with. That is, the option determination unit 40 determines that there is no possibility of admission to a nursery school where there is no vacancy in both the upper and lower bounds in the turn.

In addition, the option determination unit 40 is not certain to apply for an application target with an upper bound of 1 or more and a lower bound of 0 in each turn of a plurality of players, but there is a possibility of application, so matching possibility is possible. Judge as yes. Further, the option determination unit 40 determines that the application is certain for the application target having one or more upper and lower bounds in the turn of each of the plurality of players.

In addition, if the option determination unit 40 is certain to apply for the application target with the highest gain among the strategies (application targets) in which the possibility of applying according to the conditions remains, the application target is the optimum strategy. It is determined that the matching is established. In addition, the option determination unit 40 determines that matching is not established when there is no application target to be the optimum strategy, such as when there are a plurality of strategies in which the possibility of application according to the conditions remains.

For example, the option determination unit 40 determines that the application to the application target is the optimum strategy when there is only one application target for which the application is certain, and determines that the matching is established. In addition, if there are a plurality of application targets for which the application is certain, the option determination unit 40 is certain to apply for any of the application targets, but the optimal strategy is undecided (however, there is a possibility of matching). Therefore, it is determined that the matching is not established.

Next, when the option determination unit 40 determines that the player may select (matching possibility) in each of the plurality of players' turns, the lower bound in the application target lower bound information regarding the application target having matching possibility. Update the number of. For example, the option determination unit 40 reduces the lower bound corresponding to the number of turns (for example, one corresponding to one turn of one player) and updates the number of lower bounds in the lower bound information to be applied.

Further, when the option determination unit 40 determines that the matching is established in each of the turns of the plurality of players, the number of lower bounds in the application target lower bound information and the number of upper bounds in the application target upper bound information are obtained for the application target for which matching is established. To update. For example, the option determination unit 40 reduces the upper and lower bounds corresponding to the number of turns (for example, one corresponding to one turn of one player), and the application target upper bound information and the application target lower bound information. Update the number of upper and lower bounds in.

Here, the details of the process according to the second embodiment will be described with reference to a specific example. FIG. 13 is an explanatory diagram illustrating a gain table according to the second embodiment.

As shown in FIG. 13, in the application target information 11, the number of people accepted in each class for each application target (nursery school) identified by the nursery school ID is set. The number of people accepted in the application target information 11 is the initial value in the application target upper bound information and the application target lower bound information.

Further, in the applicant information 12, a preference list, age, priority, and the like are set for each child (applicant) identified by the child ID (a1 to d1). Similar to the first embodiment, the matching processing unit 30 sets the gain tables 15D, 15E, and 15F according to the strategy for each player (child) corresponding to the applicant.

Next, the option determination unit 40 refers to the application target upper bound information and the application target lower bound information, determines whether or not matching is established in the player's turn, and determines whether or not the player is possible to match, and the optimal strategy is clear for the player. Performs look-ahead processing to look ahead to actions. Then, the option determination unit 40 prunes the options in the game tree 16 based on the pre-read action result of the player. This look-ahead process may be executed prior to the search for the balanced path in the matching processing unit 30, or may be executed during the search for the balanced path.

FIG. 14 is an explanatory diagram illustrating an example of the look-ahead processing according to the second embodiment. FIG. 15 is an explanatory diagram illustrating a specific example of the matching process according to the second embodiment. Specifically, FIG. 15 is a diagram illustrating a matching process after the look-ahead process illustrated in FIG. 14.

As shown in FIG. 14, the option determination unit 40 performs the application target upper bound information 301 and the application target lower bound information 302 for each turn of the play order (a1 → b0 → c0 → b1 → a0 → d1) according to the priority. With reference to this, it is determined whether or not matching is possible and whether or not the player is possible to match (S60 to S64). The initial values of the upper and lower bounds in the application target upper bound information 301 and the application target lower bound information 302 are the number of people accepted in the application target information 11.

Specifically, in the turn of the child (a1) who is a player, the option determination unit 40 has a vacancy even in the lower bound of the application target (s · 1 year old, t · 1 year old) in the application target lower bound information 302. Judge that admission is certain. Here, since there are a plurality of application targets for which admission is certain, the option determination unit 40 determines that there is a possibility of matching and no matching is established for the application targets (s · 1 year old, t · 1 year old). Therefore, the option determination unit 40 reduces the lower bound of the application target lower bound information 302 in the application target (s · 1 year old, t · 1 year old) by 1, and updates the application target lower bound information 302. The minimum value of the upper bound of the application target upper bound information 301 and the lower bound of the application target lower bound information 302 is 0, and it shall not be 0 or less at the time of updating.

Similarly, in the turn of the child (b0), the option determination unit 40 determines that admission is certain because there is a vacancy in the lower bound of the application target (s.0 years old, t.0 years old) in the application target lower bound information 302. do. Here, since there are a plurality of application targets for which admission is certain, the option determination unit 40 determines that there is a possibility of matching and no matching is established for the application targets (s.0 years old, t.0 years old). Therefore, the option determination unit 40 reduces the lower bound of the application target lower bound information 302 in the application target (s.0 years old, t.0 years old) by 1, and updates the application target lower bound information 302 (S60).

Next, in the turn of the child (c0), the option determination unit 40 determines that admission is certain because there is a vacancy even in the lower bound of the application target (t.0 years old) in the application target lower bound information 302. Here, since there is only one application target for which admission is certain, it is confirmed that the option determination unit 40 selects the application target (t.0 years old) in the turn of the child (c0), and the matching is established. Judge as yes. Therefore, the option determination unit 40 reduces the upper bound of the application target upper bound information 301 and the lower bound of the application target lower bound information 302 in the application target (t.0 years old) by 1, and the application target upper bound information 301 and the application target lower bound. Information 302 is updated (S61).

Next, in the turn of the child (b1), the option determination unit 40 determines that admission is certain because there is a vacancy even in the lower bound of the application target (s. 1 year old) in the application target lower bound information 302. Here, since there is only one application target for which admission is certain, it is confirmed that the option determination unit 40 selects the application target (s, 1 year old) in the turn of the child (b1), and the matching is established. Judge as yes. Also, for children (b0), it is confirmed that the application target (s.0 years old) will be selected from the application targets (s.0 years old, t.0 years old). Therefore, the option determination unit 40 reduces the upper bound of the application target upper bound information 301 and the lower bound of the application target lower bound information 302 in the application target (s.0 years old, s.1 year old,) by 1, and the application target upper bound. Information 301 and lower bound information 302 to be applied are updated (S62).

Next, in the turn of the child (a0), the option determination unit 40 selects the application target (s.0 years old) because there is no vacancy even in the upper bound of the application target (s.0 years old) in the application target upper bound information 301. It is confirmed not to select. Since there is a vacancy in the application target (t. 0 years old), the option determination unit 40 determines that there is a possibility of matching for the application target (t. 0 years old) (S63). In the option determination unit 40, since the lower bound of the application target lower bound information 302 in the application target (t. 0 years old) has decreased to 0, the lower bound of the application target lower bound information 302 is set as it is.

Next, in the turn of the child (d1), the option determination unit 40 has a vacancy in the upper bound of the application target (s · 1 year old, t · 1 year old) in the application target upper bound information 301, so that the application target (s)・ It is determined that there is a possibility of matching for both 1 year old and t ・ 1 year old (S64). In the option determination unit 40, since the lower bound of the application target lower bound information 302 in the application target (s · 1 year old, t · 1 year old) has decreased to 0, the lower bound of the application target lower bound information 302 is the value as it is. And.

As shown in FIG. 15, by the above-mentioned look-ahead processing, the pruning of options is performed based on the application target confirmed in each player's turn. Specifically, the selection of strategy (s) in the turn of a0 is excluded. Further, the selection of the strategy (t) in the turn of b1 and b0 is excluded. Due to these exclusions, s is not included in the strategy of siblings (a0) in the gain table 15Da of a1. Further, in the gain table 15Db of a0, s is not included in one's strategy. Further, in the gain table 15Dc of b1 and b0, t is not included in one's strategy.

Therefore, in the matching process after the look-ahead process, s is excluded from the strategy of a0, and the process is started with t excluded from b1 and b0. Specifically, the matching processing unit 30 performs the gain tables 15Da, 15Db, 15Dc, and 15Ea in order from the player corresponding to the applicant with the highest priority (in the order of a1 → b0 → c0 → b1 → a0 → d1). , 15F, the player selects a strategy that may bring the maximum gain to himself (S70-S74).

For example, in the turn of the player of a1, the maximum gain of 3 (selection of t) is aimed at in the expectation that a strategy that satisfies the coupling requirement is selected by the turn of a0, which is related to the sibling (S70). Next, in the turn of the players b0, c0, and b1, a fixed strategy is selected (S71).

Next, in the turn of the player of a0, the strategy (selection of t) as expected of a0 can be performed. Therefore, it is determined that a1 can also obtain the gain “3”. Further, up to this point, it is determined that the subgames in the order of a0 or less are equilibrium paths (S72).

Next, in the turn of the player of d1, since there is no sibling relationship, the optimum strategy (selection of s) is determined on the spot (S73). Since d1 is the last player, the equilibrium path of the entire game is determined (S74).

In this way, the option determination unit 40 refers to the application target upper bound information 301 and the application target lower bound information 302, determines whether or not matching is established in the player's turn, and determines whether or not the player can match, and prunes the options. In some cases, the number of passes to be searched when finding the subgame perfect equilibrium can be further reduced. Moreover, since the number of paths to be searched can be reduced, an increase in the amount of calculation can be suppressed.

Here, it will be described that the number of paths to be searched when obtaining the subgame perfect equilibrium can be reduced by the look-ahead processing according to the second embodiment by comparing with the look-ahead processing (comparative example) in the first embodiment. ..

FIG. 16 is an explanatory diagram illustrating a comparative example of the look-ahead process. FIG. 17 is an explanatory diagram illustrating a comparative example of the matching process. Specifically, FIG. 17 is a diagram illustrating a matching process after the look-ahead process illustrated in FIG. 16.

As shown in FIG. 16, in the look-ahead process in the first embodiment, the option determination unit 40 skips the turn of the player (a1, b0) corresponding to the coupling request applicant (S80). Next, the option determination unit 40 executes the turn of c0. Here, c0 should select if there is a vacancy in the strategy (t. 0 years old). Therefore, when the upper bound (number of people accepted) of the application target (t.0 years old) in the application target upper bound information 301a is 1 or more, the option determination unit 40 reduces the upper bound by 1 and updates the upper bound (S81).

Next, the option determination unit 40 skips the turn of the player (b1, a0) corresponding to the coupling request applicant (S82). Next, the option determination unit 40 executes the turn of d1. Here, d1 should select if there is a vacancy in the strategy (s, 1 year old). Therefore, when the upper bound (number of people accepted) of the application target (s. 1 year old) in the application target upper bound information 301a is 1 or more, the option determination unit 40 reduces the upper bound by 1 and updates the upper bound (S83).

As described above, in the look-ahead processing in the first embodiment, there is no strategy that the coupling request applicant cannot select, and no strategy is determined, so there is no strategy to exclude. Therefore, the matching processing unit 30 performs matching processing for selecting a strategy in which the player may bring the maximum gain to himself / herself based on the gain tables 15D, 15E, and 15F exemplified in FIG.

Specifically, as shown in FIG. 17, the search for the path for selecting the strategy that maximizes the gain (the path for a1 to select (s)) is performed in order from the turn of the player of a1 (S90). .. Since the expected gain cannot be obtained with this pass, the option that is backtracked and disappointing (a1 selects (s)) is excluded. Next, the search for the path for which a1 selects (t) is performed, and the equilibrium path for the entire game is determined (S91).

As is clear from comparing this comparative example with the second embodiment (FIG. 15), in the second embodiment, the number of paths to be searched is reduced by the amount of the path on which the backtrack is performed in the comparative example. Therefore, in the second embodiment, the increase in the amount of calculation can be suppressed as compared with the comparative example.

As described above, the matching device 1 is a device that executes matching between a plurality of applicants each having a priority and a plurality of application targets, and has a matching processing unit 30 and an option determination unit 40. The matching processing unit 30 is an extensive game corresponding to matching, and the priority is associated with the order of play with respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants. Multiple players each know the gains of all of the multiple players. Find the subgame perfect equilibrium of an extensive game. Then, the matching processing unit 30 performs matching based on the result of the subgame perfect equilibrium, and obtains the result data 14. Further, the matching processing unit 30 has a coupling request for matching with a specific other applicant. The gain of the player corresponding to the coupling request applicant is whether or not the coupling request is satisfied. Set according to. The option determination unit 40 applies for a coupling request for the options of the game tree 16 corresponding to the partial game of the extensive game in the matching processing unit 30 by determining whether or not the options are pruned in the turn of the player corresponding to the coupling request applicant. Determined by referring to the content of the coupling request of the person. Further, the option determination unit 40 refers to the application target upper bound information 301 and the application target lower bound information 302 indicating the upper and lower bounds of the application target for which matching has not been established, respectively, for each turn of the plurality of players. It is determined whether or not matching is established in the turn and whether or not the player can be matched. Further, the option determination unit 40 updates the application target upper bound information 301 when it is determined that there is a matching possibility, and when it is determined that the matching is established, the application target upper bound information 301 and the application target lower bound information 302 are updated. Update.

In this way, the matching device 1 uses the application target upper bound information 301 and the application target lower bound information 302 for each turn of the plurality of players when obtaining the subgame perfect equilibrium of the expanded game corresponding to the matching. To determine whether matching is possible or not. As a result, the matching device 1 can reduce the number of passes to be searched for when obtaining the subgame perfect equilibrium, and can obtain the subgame perfect equilibrium while suppressing the amount of calculation.

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 them may be 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 on the CPU (or a microcomputer such as an MPU or an MCU (Micro Controller Unit)) in whole or in any part thereof. In addition, 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. 18 is an explanatory diagram illustrating a hardware configuration example of the matching device 1 according to the embodiment.

As shown in FIG. 18, the matching device 1 includes a CPU 101 that executes various arithmetic processes, an input device 102 that accepts data input, a monitor 103, and a speaker 104. Further, the matching device 1 has 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 the program 111 into the RAM 108, and executes the program to perform various processes. The program 111 may not 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 corresponds to, 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 are further disclosed with respect to the above embodiments.

(Appendix 1) A matching program that causes a computer to perform matching between multiple applicants with priorities and multiple application targets.
With respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants in the expanded game corresponding to the matching, the priority is associated with the order of play, and the plurality of players are described. Each player knows the gains of all of the multiple players, and seeks the subgame perfect equilibrium of the extensive game.
Matching based on the result of the subgame perfect equilibrium is performed.
The gain of a player corresponding to a coupling request applicant who has a coupling request requesting matching in a pair with another specific applicant is set according to whether or not the coupling request is satisfied.
Regarding the choices of the game tree corresponding to the partial game of the expansion type game, refer to the coupling request contents of the coupling request applicant for the presence or absence of pruning of the choices in the turn of the player corresponding to the coupling request applicant. To make a decision, let the computer execute each process,
The process of determining is performed by referring to the application target upper bound information and the application target lower bound information indicating the upper and lower bounds of the application target for which matching has not been established for each turn of the plurality of players. Judging whether or not matching is possible in the turn and whether or not the player is likely to match,
If it is determined that there is a possibility of matching, the above-mentioned application target lower bound information is updated and
If it is determined that matching is established, the application target upper bound information and the application target lower bound information are updated.
A matching program characterized by that.

(Appendix 2) The process to be determined is the application target updated by executing the turn of the player corresponding to the applicant other than the coupling request applicant earlier than the player corresponding to the coupling request applicant. Based on the upper bound information and the lower bound information to be applied, it is determined whether or not to prun the options in the player's turn corresponding to the coupling request applicant.
The matching program according to Appendix 1, characterized in that.

(Appendix 3) The process of determining the above reduces the number of lower bounds indicated by the application target lower bound information when it is determined that there is a matching possibility, and when it is determined that matching is established, the application target upper bound information. And reduce the number of lower bounds indicated by the application target lower bound information,
The matching program according to Appendix 1 or 2, characterized in that.

(Appendix 4) A plurality of coupling request applicants associated with the coupling request 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 by the above.

(Appendix 5) The matching is a matching between a plurality of prioritized children and a plurality of nursery schools.
The matching program according to any one of Supplementary note 1 to 4, characterized in that.

(Appendix 6) 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.
With respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants in the expanded game corresponding to the matching, the priority is associated with the order of play, and the plurality of players are described. Each player knows the gains of all of the multiple players, and seeks the subgame perfect equilibrium of the extensive game.
Matching based on the result of the subgame perfect equilibrium is performed.
The gain of a player corresponding to a coupling request applicant who has a coupling request requesting matching in a pair with another specific applicant is set according to whether or not the coupling request is satisfied.
Regarding the choices of the game tree corresponding to the partial game of the expansion type game, refer to the coupling request contents of the coupling request applicant for the presence or absence of pruning of the choices in the turn of the player corresponding to the coupling request applicant. The computer executes each process to determine
The process of determining is performed by referring to the application target upper bound information and the application target lower bound information indicating the upper and lower bounds of the application target for which matching has not been established for each turn of the plurality of players. Judging whether or not matching is possible in the turn and whether or not the player is likely to match,
If it is determined that there is a possibility of matching, the above-mentioned application target lower bound information is updated and
If it is determined that matching is established, the application target upper bound information and the application target lower bound information are updated.
A matching method characterized by that.

(Appendix 7) The process to be determined is the application target updated by executing the turn of the player corresponding to the applicant other than the coupling request applicant earlier than the player corresponding to the coupling request applicant. Based on the upper bound information and the lower bound information to be applied, it is determined whether or not to prun the options in the player's turn corresponding to the coupling request applicant.
The matching method according to Appendix 6, characterized in that.

(Appendix 8) The process of determining the above reduces the number of lower bounds indicated by the application target lower bound information when it is determined that there is a matching possibility, and when it is determined that matching is established, the application target upper bound information. And reduce the number of lower bounds indicated by the application target lower bound information,
The matching method according to Appendix 6 or 7, characterized in that.

(Appendix 9) A plurality of coupling request applicants associated with the coupling request are applicants who have a sibling relationship with each other.
The matching method according to any one of Supplementary Provisions 6 to 8, characterized in that.

(Appendix 10) The matching is a matching between a plurality of prioritized children and a plurality of nursery schools.
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.
With respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants in the expanded game corresponding to the matching, the priority is associated with the order of play, and the plurality of players are described. A matching processing unit that obtains the subgame perfect equilibrium of an extensive game in which each player knows the gains of all the plurality of players and performs matching based on the result of the subgame perfect equilibrium.
The gain of a player corresponding to a coupling request applicant who has a coupling request requesting matching in a pair with another specific applicant is set according to whether or not the coupling request is satisfied.
Regarding the choices of the game tree corresponding to the partial game of the expansion type game, refer to the coupling request contents of the coupling request applicant for the presence or absence of pruning of the choices in the turn of the player corresponding to the coupling request applicant. Has a decision-making part, and
The determination unit refers to the application target upper bound information and the application target lower bound information indicating the upper and lower bounds of the application target for which matching has not been established for each turn of the plurality of players. Judging whether or not matching is possible in, and whether or not the player is likely to match,
If it is determined that there is a possibility of matching, the above-mentioned application target lower bound information is updated and
If it is determined that matching is established, the application target upper bound information and the application target lower bound information are updated.
A matching device characterized by that.

(Appendix 12) The decision unit is updated by executing the turn of the player corresponding to the applicant other than the coupling request applicant earlier than the player corresponding to the coupling request applicant. Based on the boundary information and the application target lower bound information, it is determined whether or not to prun the options in the player's turn corresponding to the coupling request applicant.
The matching device according to Appendix 11, wherein the matching apparatus is characterized in that.

(Appendix 13) When the determination unit determines that there is a matching possibility, it reduces the number of lower bounds indicated by the application target lower bound information, and when it determines that matching is established, the application target upper bound information and the application target upper bound information. Decrease the number of lower bounds indicated by the application target lower bound information,
The matching apparatus according to Supplementary Note 11 or 12, wherein the matching apparatus is characterized in that.

(Appendix 14) A plurality of coupling request applicants associated with the coupling request are applicants who have a sibling relationship with each other.
The matching device according to any one of Supplementary note 11 to 13, wherein the matching apparatus is characterized in that.

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

1 ... Matching device 10 ... Storage unit 11, 201 ... Application target information 12, 202 ... Applicant information 13 ... Calculation data 14 ... Result data 15A, 15Aa, 15Ab, 15B, 15C, 15D, 15Da, 15Db, 15Dc, 15E, 15Ea, 15F ... Gain table 16 ... Game tree 20 ... Input unit 30 ... Matching processing unit 40 ... Option determination unit 50 ... Output unit 101 ... CPU
102 ... Input device 103 ... Monitor 104 ... Speaker 105 ... Medium reading device 106 ... Interface device 107 ... Communication device 108 ... RAM
109 ... Hard disk device 110 ... Bus 111 ... Program 112 ... Various data 301, 301a ... Application target upper bound information 302 ... Application target lower bound information C1 to C3 ... First to third cases

Claims (7)

It is a matching program that causes a computer to perform matching between multiple applicants with priorities and multiple application targets.
With respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants in the expanded game corresponding to the matching, the priority is associated with the order of play, and the plurality of players are described. Each player knows the gains of all of the multiple players, and seeks the subgame perfect equilibrium of the extensive game.
Matching based on the result of the subgame perfect equilibrium is performed.
The gain of a player corresponding to a coupling request applicant who has a coupling request requesting matching in a pair with another specific applicant is set according to whether or not the coupling request is satisfied.
Regarding the choices of the game tree corresponding to the partial game of the expansion type game, refer to the coupling request contents of the coupling request applicant for the presence or absence of pruning of the choices in the turn of the player corresponding to the coupling request applicant. To make a decision, let the computer execute each process,
The process of determining is performed by referring to the application target upper bound information and the application target lower bound information indicating the upper and lower bounds of the application target for which matching has not been established for each turn of the plurality of players. It is determined whether or not matching is established in the turn, and whether or not the player can be matched in the turn after the turn.
If it is determined that there is a possibility of matching in the turn after the turn , the application target lower bound information is updated.
If it is determined that the matching in the turn is established, the application target upper bound information and the application target lower bound information are updated.
A matching program characterized by that. The process of determining is the application target upper bound information updated by executing the turn of the player corresponding to the applicant other than the coupling request applicant earlier than the player corresponding to the coupling request applicant. Based on the application target lower bound information, it is determined whether or not to prun the options in the player's turn corresponding to the coupling request applicant.
The matching program according to claim 1. The process of determining reduces the number of lower bounds indicated by the application target lower bound information when it is determined that there is a matching possibility, and when it is determined that matching is established, the application target upper bound information and the application target. Decrease the number of lower bounds indicated by lower bound information,
The matching program according to claim 1 or 2. The plurality of coupling request applicants associated with the coupling request 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.
The matching program according to any one of claims 1 to 4, wherein the matching program is characterized in that. It is a matching method in which a computer performs matching between multiple applicants with priorities and multiple application targets.
With respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants in the expanded game corresponding to the matching, the priority is associated with the order of play, and the plurality of players are described. Each player knows the gains of all of the multiple players, and seeks the subgame perfect equilibrium of the extensive game.
Matching based on the result of the subgame perfect equilibrium is performed.
The gain of a player corresponding to a coupling request applicant who has a coupling request requesting matching in a pair with another specific applicant is set according to whether or not the coupling request is satisfied.
Regarding the choices of the game tree corresponding to the partial game of the expansion type game, refer to the coupling request contents of the coupling request applicant for the presence or absence of pruning of the choices in the turn of the player corresponding to the coupling request applicant. The computer executes each process to determine
The process of determining is performed by referring to the application target upper bound information and the application target lower bound information indicating the upper and lower bounds of the application target for which matching has not been established for each turn of the plurality of players. It is determined whether or not matching is established in the turn, and whether or not the player can be matched in the turn after the turn.
If it is determined that there is a possibility of matching in the turn after the turn , the application target lower bound information is updated.
If it is determined that the matching in the turn is established, the application target upper bound information and the application target lower bound information are updated.
A matching method characterized by that. It is a matching device that executes matching between multiple applicants with priorities and multiple application targets.
With respect to a plurality of independent players having a gain corresponding to the preference of each of the plurality of applicants in the expanded game corresponding to the matching, the priority is associated with the order of play, and the plurality of players are described. A matching processing unit that obtains the subgame perfect equilibrium of an extensive game in which each player knows the gains of all the plurality of players and performs matching based on the result of the subgame perfect equilibrium.
The gain of a player corresponding to a coupling request applicant who has a coupling request requesting matching in a pair with another specific applicant is set according to whether or not the coupling request is satisfied.
Regarding the choices of the game tree corresponding to the partial game of the expansion type game, refer to the coupling request contents of the coupling request applicant for the presence or absence of pruning of the choices in the turn of the player corresponding to the coupling request applicant. Has a decision-making part, and
The determination unit refers to the application target upper bound information and the application target lower bound information indicating the upper and lower bounds of the application target for which matching has not been established for each turn of the plurality of players. Whether or not the matching is established in, and whether or not the player can be matched in the turn after the relevant turn is determined.
If it is determined that there is a possibility of matching in the turn after the turn , the application target lower bound information is updated.
If it is determined that the matching in the turn is established, the application target upper bound information and the application target lower bound information are updated.
A matching device characterized by that.

Images