Necessarily Optimal One-Sided Matchings

No. 6: AAAI-21 Technical Tracks 6

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Game Theory and Economic Paradigms

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.

10.1609/aaai.v35i6.16690