Necessarily Optimal One-Sided Matchings

Authors

  • Hadi Hosseini Penn State University
  • Vijay Menon University of Waterloo
  • Nisarg Shah University of Toronto
  • Sujoy Sikdar Binghamton University

Keywords:

Social Choice / Voting, Other Foundations of Game Theory & Economic Parad, Imperfect Information

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.

Downloads

Published

2021-05-18

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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16690

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms