Constrainedness in stable matching

Guillaume Escamocher; Barry O'Sullivan

doi:10.1109/ICTAI.2018.00112

Constrainedness in stable matching

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

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.

Original language	English
Title of host publication	Proceedings - 2018 IEEE 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018
Publisher	IEEE Computer Society
Pages	710-717
Number of pages	8
ISBN (Electronic)	9781538674499
DOIs	https://doi.org/10.1109/ICTAI.2018.00112
Publication status	Published - 13 Dec 2018
Event	30th International Conference on Tools with Artificial Intelligence, ICTAI 2018 - Volos, Greece Duration: 5 Nov 2018 → 7 Nov 2018

Publication series

Name	Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
Volume	2018-November
ISSN (Print)	1082-3409

Conference

Conference	30th International Conference on Tools with Artificial Intelligence, ICTAI 2018
Country/Territory	Greece
City	Volos
Period	5/11/18 → 7/11/18

Keywords

Constrainedness
Contrarian score
Stable matching

Access to Document

10.1109/ICTAI.2018.00112

Cite this

Escamocher, G., & O'Sullivan, B. (2018). Constrainedness in stable matching. In Proceedings - 2018 IEEE 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018 (pp. 710-717). Article 8576110 (Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI; Vol. 2018-November). IEEE Computer Society. https://doi.org/10.1109/ICTAI.2018.00112

@inproceedings{a83db504a6394b169204f053f12797bd,

title = "Constrainedness in stable matching",

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.",

keywords = "Constrainedness, Contrarian score, Stable matching",

author = "Guillaume Escamocher and Barry O'Sullivan",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018 ; Conference date: 05-11-2018 Through 07-11-2018",

year = "2018",

month = dec,

day = "13",

doi = "10.1109/ICTAI.2018.00112",

language = "English",

series = "Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI",

publisher = "IEEE Computer Society",

pages = "710--717",

booktitle = "Proceedings - 2018 IEEE 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018",

address = "United States",

}

Escamocher, G & O'Sullivan, B 2018, Constrainedness in stable matching. in Proceedings - 2018 IEEE 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018., 8576110, Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI, vol. 2018-November, IEEE Computer Society, pp. 710-717, 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018, Volos, Greece, 5/11/18. https://doi.org/10.1109/ICTAI.2018.00112

Constrainedness in stable matching. / Escamocher, Guillaume ; O'Sullivan, Barry.
Proceedings - 2018 IEEE 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018. IEEE Computer Society, 2018. p. 710-717 8576110 (Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI; Vol. 2018-November).

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

TY - GEN

T1 - Constrainedness in stable matching

AU - Escamocher, Guillaume

AU - O'Sullivan, Barry

PY - 2018/12/13

Y1 - 2018/12/13

N2 - 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.

AB - 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.

KW - Constrainedness

KW - Contrarian score

KW - Stable matching

UR - https://www.scopus.com/pages/publications/85060815469

U2 - 10.1109/ICTAI.2018.00112

DO - 10.1109/ICTAI.2018.00112

M3 - Conference proceeding

AN - SCOPUS:85060815469

T3 - Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI

SP - 710

EP - 717

BT - Proceedings - 2018 IEEE 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018

PB - IEEE Computer Society

T2 - 30th International Conference on Tools with Artificial Intelligence, ICTAI 2018

Y2 - 5 November 2018 through 7 November 2018

ER -

Constrainedness in stable matching

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this