Preference elicitation in matching markets via interviews: a study of offline benchmarks (extended abstract)

Baharak Rastegari, Paul Goldberg, David Manlove

Research output: Contribution to conferenceConference Abstractpeer-review

65 Downloads (Pure)

Abstract

In this paper we study two-sided matching markets in which the participants do not fully know their preferences and need to go through some costly deliberation process in order to learn their preferences. We assume that such deliberations are carried out via interviews, thus the problem is to find a good strategy for interviews to be carried out in order to minimize their use, whilst leading to a stable matching. One way to evaluate the performance of an interview strategy is to compare it against a nave ïalgorithm that conducts all interviews. We argue however that a more meaningful comparison would be against an optimal offline algorithm that has access to agents' preference orderings under complete information. We show that, unless P=NP, no offline algorithm can compute the optimal interview strategy in polynomial time. If we are additionally aiming for a particular stable matching, we provide restricted settings under which efficient optimal offline algorithms exist.
Original languageEnglish
Pages1393-1394
Number of pages2
Publication statusPublished - 9 May 2016

Keywords

  • Two-sided matching
  • preferences
  • interviews

Fingerprint Dive into the research topics of 'Preference elicitation in matching markets via interviews: a study of offline benchmarks (extended abstract)'. Together they form a unique fingerprint.

Cite this