Necessarily Optimal One-Sided Matchings
Keywords:Social Choice / Voting, Other Foundations of Game Theory & Economic Parad, Imperfect Information
AbstractWe 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.
How to Cite
Hosseini, H., Menon, V., Shah, N., & Sikdar, S. (2021). Necessarily Optimal One-Sided Matchings. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5481-5488. https://doi.org/10.1609/aaai.v35i6.16690
AAAI Technical Track on Game Theory and Economic Paradigms