Constrainedness in stable matching

Loading...
Thumbnail Image
Date
2018-12-17
Authors
Escamocher, Guillaume
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Research Projects
Organizational Units
Journal Issue
Abstract
In constraint satisfaction problems, constrainedness provides a way to predict the number of solutions: for instances of a same size, the number of constraints is inversely correlated with the number of solutions. However, there is no obvious equivalent metric for stable matching problems. We introduce the contrarian score, a simple metric that is to matching problems what constrainedness is to constraint satisfaction problems. In addition to comparing the contrarian score against other potential tightness metrics, we test it for different instance sizes as well as extremely distinct versions of the stable matching problem. In all cases, we find that the correlation between contrarian score and number of solutions is very strong.
Description
Keywords
Constraint handling , Constraint satisfaction problems , Contrarian score , Stable matching problem , Constrainedness , Matching problems , Tightness metrics , Measurement , Switches , Tools , Data analysis , Correlation , Conferences , Artificial intelligence , Stable matching
Citation
Escamocher, G. and O'Sullivan, B. (2018) 'Constrainedness in stable matching', 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), Volos, Greece, 5-7 November, pp. 710-717. doi:10.1109/ICTAI.2018.00112
Copyright
© 2018, IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.