Online Elicitation of Necessarily Optimal Matchings
AAAI• 2022
Abstract
In this paper, we study the problem of eliciting preferences of agents in the
house allocation model. For this we build on a recent model of Hosseini et
al.[AAAI'21] and focus on the task of eliciting preferences to find matchings
which are necessarily optimal, i.e., optimal under all possible completions of
the elicited preferences. In particular, we follow the approach of Hosseini et
al. and investigate the elicitation of necessarily Pareto optimal (NPO) and
necessarily rank-maximal (NRM) matchings. Most importantly, we answer their
open question and give an online algorithm for eliciting an NRM matching in the
next-best query model which is 3/2-competitive, i.e., it takes at most 3/2 as
many queries as an optimal algorithm. Besides this, we extend this field of
research by introducing two new natural models of elicitation and by studying
both the complexity of determining whether a necessarily optimal matching
exists in them, and by giving online algorithms for these models.