A reinforcement learning based bipartite matching system

• Main Author: Khairul Amiru Ahmad Mohr
• Other Authors: Cheng Long
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
• Online Access: https://hdl.handle.net/10356/148067
• Institution: Nanyang Technological University

Reinforcement learning is an area of machine learning that pertains to how intelligent agents should respond to the constantly changing aspects of the environment with the objective to maximize the notion of cumulative reward. Reinforcement learning has been a widely used tool in various disciplines such as resource management, multi-agent systems, games, etc. The scope of this project aims to utilize RL to tackle the problem of bipartite matching, which is a form of matching where the set of edges are chosen such that no two edges share the same endpoint. Many real-world problems can be modeled as bipartite matching very naturally. For instance, consider a subset of applicants and a subset of job vacancies. Each job vacancy can only accept one applicant and one applicant can only be appointed one job. The relations between the subset of applicants and the subset of job vacancies accurately describe a bipartite matching problem when we try to maximize the number of matches that can be made within those subsets. If we extend this perspective towards other use-cases, tackling the problem of bipartite matching becomes largely relevant. This FYP is based on the study done by a Ph.D. student under the same supervisor on his algorithm: Adaptive Holding for Online Bottleneck Matching with Delays. It is geared towards developing a tool that aids visualization of the algorithm for better comprehension and grasp of the inner workings of the algorithm.