Elicitation and Approximately Stable Matching with Partial Preferences
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 97-104.
Abstract
Algorithms for stable marriage and related matching problems typically assume that full preference information is available. While the Gale-Shapley algorithm can be viewed as a means of eliciting preferences incrementally, it does not prescribe a general means for matching with incomplete information, nor is it designed to minimize elicitation. We propose the use of maximum regret to measure the (inverse) degree of stability of a matching with partial preferences; minimax regret to find matchings that are maximally stable in the presence of partial preferences; and heuristic elicitation schemes that use max regret to determine relevant preference queries. We show that several of our schemes find stable matchings while eliciting considerably less preference information than Gale-Shapley and are much more appropriate in settings where approximate stability is viable.
@inproceedings{ijcai2013p26,
title = {Elicitation and Approximately Stable Matching with Partial Preferences},
author = {Drummond, Joanna and Boutilier, Craig},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {97--104},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/26},
}
TY - CPAPER TI - Elicitation and Approximately Stable Matching with Partial Preferences AU - Drummond, Joanna AU - Boutilier, Craig T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 97 EP - 104 UR - https://ijcai.org/proceedings/2013/26 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
