Matched about 8,000 children in Saitama to daycare centers in just seconds
TOKYO, Aug 30, 2017 – Fujitsu Limited, Fujitsu Laboratories Ltd., and the Fujitsu Social Mathematics Division of the Institute of Mathematics for Industry at Kyushu University(1) have developed an AI-based matching technology that uses game theory to automatically calculate an optimal matching of children to daycare centers. Using this technology, a complicated daycare admissions screening that had previously required several days by hand took only seconds.
The admissions process of matching children to daycare centers 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 daycare center. 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 daycare center, 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 daycare centers due to applicant preferences not being accepted.
Now, this newly developed technology has made it possible to match children to daycare centers, meeting as many preferences as possible, following a priority ranking. This is done by modeling the dependency relationships of complex requirements, including parents who prioritize siblings going to the same daycare center, or parents who do not mind if their children go to different daycare centers as long as both children get a seat, using a mathematical model(2) based on game theory, which rationally resolves the relationships between people having differing values. When this technology was evaluated using anonymized 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.
Background
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 daycare centers. One of these issues is the increasing complexity of daycare 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 daycares 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.
Issues
When trying to incorporate complex requirements into admissions rules, such as parents who prioritize siblings going to the same daycare center, and parents who do not mind if siblings go to separate daycare centers 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 daycare centers 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 daycare admissions, this technology successfully finds the optimal assignment pattern that prioritizes 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 daycares (A and B) that can take two children each. Considering the number of seats in each daycare, there are six possible patterns (figure 1). In this example, the parents of each child have requested daycare A over daycare B, but have also expressed that they would prefer that both siblings go to daycare 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.
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 daycares and children increase, the table can become massive. If five daycare preferences are listed for each of 8,000 children, there will be 5 to the power of 8000 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 maximizes the scores for the applicants having highest priority.
Effects
This technology was evaluated using anonymized 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 commercialized, 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.
Future Plans
By the end of this fiscal year, Fujitsu plans to offer this technology as an optional service in its MICJET MISALIO Child-Rearing Support module, a childcare support system for local governments.
In addition, as part of its Fujitsu Human Centric AI Zinrai artificial intelligence technology, Fujitsu will aim to adopt this technology beyond daycare admissions, to encompass a variety of matching applications, such as the fair matching of personnel deployments within an organization and employee schedule matching.
(1) Fujitsu Social Mathematics Division of the Institute of Mathematics for Industry at Kyushu University
Institute of Mathematics for Industry: Asia’s first mathematics research center focused on industrial technology. In addition to carrying out mathematical theory research for industry, it also contains the Laboratory of Advanced Software in Mathematics, which implements and publishes theories as software. Fujitsu Social Mathematics Division: A mathematical technology research and development unit aimed at resolving social issues, established in September 2014, as part of the Institute of Mathematics for Industry by Kyushu University, Fujitsu Limited, and Fujitsu Laboratories Ltd.
(2) Modeling….using a mathematical model
This research was partially supported by JST PRESTO Grant Number JPMJPR14E1, Japan.
