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.
翻译：在本文中,我们研究了在住房分配模式中吸引代理人偏好的问题。 为此,我们借鉴了最近Hosseini et al.[AAAI'21] 的模型,并侧重于寻求偏好以找到必然是最佳的匹配,即在获得的偏好的所有可能完成情况下最理想的匹配。我们特别遵循Hosseini et al. 的方法,调查必然是Pareto最佳匹配(NPO)和一定的等级最大匹配(NRM)的吸引问题。最重要的是,我们回答他们的开放问题,并给出在线算法,用于在3/2-竞争性的下一个最佳查询模式中获取NRM匹配,也就是说,它将最多3/2的查询作为最佳算法。此外,我们扩展了这一研究领域,采用了两种新的自然引力模型,并研究了确定这些模型中是否存在一定最佳匹配的复杂性,以及对这些模型提供在线算法。
相关内容
微信扫码咨询专知VIP会员