Online Elicitation of Necessarily Optimal Matchings

Authors

  • Jannik Peters TU Berlin

DOI:

https://doi.org/10.1609/aaai.v36i5.20451

Keywords:

Game Theory And Economic Paradigms (GTEP)

Abstract

In this paper, we study the problem of eliciting preferences of agents in the house allocation model. For this we build on a recently introduced model 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 investigate the elicitation of necessarily Pareto optimal (NPO) and necessarily rank-maximal (NRM) matchings. Most importantly, we answer an 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.

Downloads

Published

2022-06-28

How to Cite

Peters, J. (2022). Online Elicitation of Necessarily Optimal Matchings. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5164-5172. https://doi.org/10.1609/aaai.v36i5.20451

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms