A Social Needs Marketplace Matching Problem
J. Christopher Beck
An instance of the social needs marketplace matching problem consists of a bipartite graph with seekers, donors, and a set of edges between them. Each donor has one item to donate, while each seeker has one request to make for the items offered by the donors. Each seeker has a preference over items donated by the donors, and ranks them based on its preference. For each seeker, we know the preference list of that seeker. The donors do not have any preference over seekers, which makes it an one-sided preference problem. A common example of an one-sided preference problem is the University residence allocation problem.
A seeker is unmatched if all its preferred donors are matched with other seekers. Donors and seekers are collectively referred to as the set of agents. Each agent arrives to the matching process online. All our agents stay in the matching process for a time before reneging (choosing to leave) from the process.
Agents do not stay in the matching process for the entire time interval, but rather stay for a time window, defined by a start and end time. We know the time window of an agent only upon its arrival (they are revealed online). The objective of the problem is to construct an effective methodology for solving the online matching problem, combining approaches from matching and queueing theory literature.
University of Toronto Fellowship
TIDEL Research Assistantship