You are here

Constrainedness in Stable Matching

Publication Type: 
Refereed Conference Meeting Proceeding
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.
Conference Name: 
ICTAI 2018
Digital Object Identifer (DOI): 
10.1109/ICTAI.2018.00112
Publication Date: 
06/11/2018
Pages: 
710-717
Conference Location: 
Greece
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
Yes
Publication document: