A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences

Cseh, Ágnes; Escamocher, Guillaume; Genç, Begüm; Quesada, Luis

A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences

dc.contributor.author	Cseh, Ágnes
dc.contributor.author	Escamocher, Guillaume
dc.contributor.author	Genç, Begüm
dc.contributor.author	Quesada, Luis
dc.contributor.funder	Science Foundation Ireland	en
dc.contributor.funder	European Regional Development Fund	en
dc.date.accessioned	2021-10-20T14:47:18Z
dc.date.available	2021-10-20T14:47:18Z
dc.date.issued	2021-10-15
dc.date.updated	2021-10-20T14:35:34Z
dc.description.abstract	We introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been proposed for variants of the two-dimensional stable matching problem, we are the first to present constraint models for a higher number of dimensions. We show for all five models how to capture two different stability notions, namely weak and strong stability. Additionally, we translate some well-known fairness notions (i.e. sex-equal, minimum regret, egalitarian) into 3-dimensional matchings, and present how to capture them in each model. Our tests cover dozens of problem sizes and four different instance generation methods. We explore two levels of commitment in our models: one where we have an individual variable for each agent (individual commitment), and another one where the determination of a variable involves pairing the three agents at once (group commitment). Our experiments show that the suitability of the commitment depends on the type of stability we are dealing with. Our experiments not only led us to discover dependencies between the type of stability and the instance generation method, but also brought light to the role that learning and restarts can play in solving this kind of problems.	en
dc.description.sponsorship	Science Foundation Ireland (12/RC/2289-P2, 16/SP/3804 and 16/RC/3918)	en
dc.description.status	Peer reviewed	en
dc.description.version	Published Version	en
dc.format.mimetype	application/pdf	en
dc.identifier.articleid	22	en
dc.identifier.citation	Cseh, Á, Escamocher, G., Genç, B. and Quesada, L. (2021) 'A collection of Constraint Programming models for the three-dimensional stable matching problem with cyclic preferences', 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), Montpellier, France, 25 - 29 October, 22 (19pp). doi: 10.4230/LIPIcs.CP.2021.22	en
dc.identifier.doi	10.4230/LIPIcs.CP.2021.22	en
dc.identifier.endpage	19	en
dc.identifier.isbn	978-3-95977-211-2
dc.identifier.issn	1868-8969
dc.identifier.startpage	1	en
dc.identifier.uri	https://hdl.handle.net/10468/12115
dc.language.iso	en	en
dc.publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik	en
dc.relation.ispartof	27th International Conference on Principles and Practice of Constraint Programming (CP 2021), Montpellier, France, 25 - 29 October 2021
dc.relation.ispartof	Leibniz International Proceedings in Informatics (LIPIcs)
dc.relation.ispartofseries	Leibniz International Proceedings in Informatics (LIPIcs);
dc.relation.uri	https://doi.org/10.5281/zenodo.5156119
dc.rights	© 2021, Ágnes Cseh, Guillaume Escamocher, Begüm Genç, and Luis Quesada. Licensed under Creative Commons License CC-BY 4.0	en
dc.rights.uri	https://creativecommons.org/licenses/by/4.0/	en
dc.subject	Three-dimensional stable matching with cyclic preferences	en
dc.subject	3DSM-cyc	en
dc.subject	Constraint Programming	en
dc.subject	Fairness	en
dc.title	A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences	en
dc.type	Conference item	en