Necessarily Optimal One-Sided Matchings
Hadi Hosseini, Vijay Menon, Nisarg Shah, Sujoy Sikdar
Abstract
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.
BibTeX
@inproceedings{aaai2021_necessarilyoptim,
title = {Necessarily Optimal One-Sided Matchings},
author = {Hadi Hosseini and Vijay Menon and Nisarg Shah and Sujoy Sikdar},
booktitle = {AAAI 2021},
year = {2021}
}