Necessarily Optimal One-Sided Matchings
This work addresses the challenge of reducing preference elicitation in matching problems for applications like school assignments or resource allocation, though it is incremental as it builds on classical matching theory with partial preferences.
The paper tackles the problem of learning desirable matchings from partial preferences in a one-sided matching setting, focusing on necessarily Pareto optimal (NPO) and necessarily rank-maximal (NRM) matchings under top-k preferences, and provides efficient algorithms for checking and existence, along with competitive ratio bounds for online elicitation.
We study the classical problem of matching $n$ agents to $n$ objects, where the agents have ranked preferences over the objects. We focus on two popular desiderata from the matching literature: Pareto optimality and rank-maximality. Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences, specifically a matching that is necessarily Pareto optimal (NPO) or necessarily rank-maximal (NRM) under any completion of the partial preferences. We focus on the top-$k$ model in which agents reveal a prefix of their preference rankings. We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-$k$ partial preferences. We also study online algorithms for eliciting partial preferences adaptively, and prove bounds on their competitive ratio.