Research

Aiming to solve complex combinatorial problems

Research on matching people and organizations

Demand for finding desirable matchings is widespread in society. Examples include assignment of resident physicians to hospitals, course allocation in educational institutes, and allocating airport departure and arrival slots. I am working on matching theory, a mathematical framework searching for methodology to find structurally stable matchings that satisfy specific conditions reflecting preferences of these kinds of people and organizations.

I find it interesting to theoretically formulate concepts of social norms, such as fairness, and to think mathematically about matchings that satisfy every participant. When I look at algorithms worked out by predecessors, I am frequently impressed by their excellent structures and rich implications.

How to analyze the complex situations of real problems

Matching theory began in the 1960s, and it has grown into an interdisciplinary field involving researchers from various fields such as economics, computer science, and mathematics. For standard models, there have been proposed efficient algorithms that always find stable matchings (fair matchings capable of satisfying everyone), such as the Gale-Shapley algorithm.

However, when realistic constraints are introduced, it often becomes impossible to find a clear solution theoretically. For example, while a solution can be found efficiently for the simple hospitals/residents matching problem, the problem becomes quite complicated if hospitals have constraints related to diversity or set lower quotas on the number of allocated residents. Then it is computationally difficult to find a stable solution. In my research, I attempt to design algorithms to find desirable matchings in such complicated models making use of knowledge of combinatorial optimization.

Also, for these difficult problems, I would like to consider various approaches including relaxing the solution concepts and designing approximate algorithms.

Aiming for combinatorial optimization theory that benefits society

The topic of matching problems includes various fields such as economics, operations research, and AI, and extends across a wide range of disciplines. The fields of application are extremely diverse. I am most interested in theory construction, and I aim to contribute to the field by analyzing structures and designing algorithms.

Hereafter, I would like to expand my research area to include more various combinatorial problems in addition to matching problems. Also, partnering with experts on, for example, big data analysis is expected to enable the construction of new theories related to social issues requiring combinatorial optimization. If such an opportunity presents itself, I would like to contribute to society by also working on applications.

* The standard stable matching model