An AI-based matching technology that uses game theory to automatically calculate an optimal matching of children to nurseries has been developed by Fujitsu, Fujitsu Laboratories, and the Fujitsu Social Mathematics Division of the Institute of Mathematics for Industry at Kyushu University. Using this technology, a complicated nursery admissions screening that had previously required several days by hand took only seconds.
The admissions process of matching children to nurseries seeks to fulfill as many of the applicants' preferences as possible based on complex requirements, including applicant priority criteria set by each local government and requests for siblings to be admitted to the same nursery. This has made it difficult to automate the matching process in a way that would satisfy all applicants. As a result, many local governments have, until now, manually conducted trial and error to as much as possible accommodate preferences for siblings to attend the same nursery, but this meant that seat assignment by the local government could take several weeks, requiring some time before the applicants could be notified of the results. There were also issues such as siblings being admitted to different nurseries due to applicant preferences not being accepted.
Now, this newly developed technology has made it possible to match children to nurseries, meeting as many preferences as possible, following a priority ranking. This is done by modeling the dependency relationships of complex requirements, including parents who prioritise siblings going to the same nursery, or parents who do not mind if their children go to different nurseries as long as both children get a seat, using a mathematical model based on game theory, which rationally resolves the relationships between people having differing values. When this technology was evaluated using anonymised data from about 8,000 children in the city of Saitama, it successfully calculated an optimal assignment result in just a few seconds.
Fujitsu plans to offer this technology as an optional service for MICJET MISALIO Child-Rearing Support, a childcare support system for local governments, during fiscal 2017. The company will also work to apply this technology to a variety of matching problems as part of Fujitsu Human Centric AI Zinrai, Fujitsu's approach to artificial intelligence.
In recent years, a number of measures have been undertaken to slow the declining birth rate in Japan, including enacting the 'Act on Child and Childcare Support'. Many issues still remain, however, in the childcare situation in many regions, such as the number of children waiting for places at nurseries. One of these issues is the increasing complexity of nursery admissions screening due to the need to maintain fairness. This poses difficulties in the admissions screening, in which children are matched to a limited number of places while taking into consideration the various circumstances of each family, requiring a great deal of staff and time.
There have also been many cases, depending on the local government, where the result of efforts to accommodate preferences was that siblings ended up in different nurseries despite the results of numerous consultations. From the perspective of supporting working women, an important government policy, as well, handling the admissions assignment process quickly, carefully, and appropriately has become an urgent need in society.
When trying to incorporate complex requirements into admissions rules, such as parents who prioritise siblings going to the same nursery, and parents who do not mind if siblings go to separate nurseries but who will pull out if only one child gets a place, there are cases where either there are multiple matching patterns that satisfy all rules, or times when each matching pattern violates some rules. This makes it difficult to automatically select the matching pattern that satisfies applicants to the maximum extent possible.
In Saitama, for example, to carefully handle the matching of applicants, the local government undertook their own admissions screening that considered sibling admissions as well as the timing of the siblings' admissions, the facilities they would be admitted to, their age, and their priority ranking. In order to match 7,959 children to 311 nurseries while considering these complex requirements, however, the task required numerous days of work by 20 to 30 employees.
About the newly developed technology
Fujitsu, Fujitsu Laboratories, and Kyushu University have now developed matching technology that can automatically determine the assignment pattern that will fulfill the preferences of as many applicants as possible, according to priority ranking, by creating a model of the relationships that meet the individual preferences of multiple applicants, in consideration of complex requirements that are determined by human trial and error. Game theory, which is used to create the model in this technology, is a mathematical approach that rationally handles conflicts and cooperation between people in society where interests are not necessarily aligned. Mathematical research based on the game theory is primarily ongoing in the field of economics. By applying this theory to the matching problem of nursery admissions, this technology successfully finds the optimal assignment pattern that prioritises applicants having the highest priority, even in cases of multiple patterns that fulfill all rules, or no patterns fulfill all rules.
As an example, one can consider assigning two sets of siblings (a total of four children) to two nurseries (daycares A and B) that can take two children each. Considering the number of seats in each nursery, there are six possible patterns (Figure 1). In this example, the parents of each child have requested nursery A over nursery B, but have also expressed that they would prefer that both siblings go to nursery B rather than be split up. In this situation, the rule is to fulfil these preferences as much as possible in determining admission assignment while also respecting the priority ranking of the children.
Figure 1: Admissions decision using the rule (assignment 3 is optimal)
If the preferences for child 2, for example, cannot be met due to the preferences for child 1, who has higher priority, then that must be accepted, but if they cannot be met due to the preferences for child 3, who has lower priority, this would be a violation of the rule. In this way, it is necessary to check if the rule is being violated while considering both the priority of the children and their preferences. In addition, in cases where siblings have different priority rankings, there are cases where there may be multiple assignments that fulfill the rule. In this case, where seat assignments 3 and 4 both fulfill the rules, assignment 3 is considered optimal, because it can meet the preferences of child 1, who has the highest priority ranking.
Figure 1 is a simple example, but as the number of nurseries and children increase, the table can become massive. If five nursery preferences are listed for each of 8,000 children, there will be five to the power of 8,000 possible combinations. Even using computers, it would be difficult to calculate each of those one by one in any realistic amount of time. In addition, even if an assignment that fulfilled the rules was found by devising the method in which possible assignments are checked, it would be difficult to guarantee an even better assignment was not possible.
Now Fujitsu, Fujitsu Laboratories, and Kyushu University have developed technology in which, using a model based on game theory, the payoff (desirability) from an admissions assignment is converted to a score, and that score is used to find the optimal assignment pattern. This makes it possible to rapidly calculate the one assignment pattern that maximises the scores for the applicants having highest priority.
This technology was evaluated using anonymised data for about 8,000 children in Saitama. The result was that this technology was able to calculate in just seconds seat assignments that fulfilled the complex and detailed requirements unique to Saitama, which had previously taken 20 to 30 people quite a few days. When this technology is commercialised, it is expected that it will not only dramatically reduce the burden of seat assignment tasks on local government personnel, it will also enable decision notifications to be sent to applicants earlier, improving services to residents. Moreover, it is expected that this will enable the process to incorporate more detailed requirements without increasing the amount of work or the chance of overlooking something, improving applicant satisfaction.