Rank Gaps and the Size of the Core for Roommate Problems

This paper deals with roommate problems (Gale and Shapley, 1962) that are solvable, i.e., have a non-empty core (set of stable matchings). We study the assortativeness of stable matchings and the size of the core by means of maximal and average rank gaps. We provide upper bounds in terms of maximal...

Descripción completa

Detalles Bibliográficos
Autores Principales: Jaramillo, Paula, Kayi, Cagatay, Klijn, Flip
Otros Autores: Grupo de investigaciones. Facultad de Economía. Universidad del Rosario
Formato: Documento de trabajo (Working Paper)
Lenguaje:Español (Spanish)
Publicado: Universidad del Rosario 2017
Materias:
C78
Acceso en línea:http://repository.urosario.edu.co//handle/10336/13229
id ir-10336-13229
recordtype dspace
spelling ir-10336-132292019-09-19T12:37:01Z Rank Gaps and the Size of the Core for Roommate Problems Jaramillo, Paula Kayi, Cagatay Klijn, Flip Grupo de investigaciones. Facultad de Economía. Universidad del Rosario Teoría de búsqueda y emparejamiento Teoría de los juegos Matching Roommate problem Stability Core Rank gap Bound C78 This paper deals with roommate problems (Gale and Shapley, 1962) that are solvable, i.e., have a non-empty core (set of stable matchings). We study the assortativeness of stable matchings and the size of the core by means of maximal and average rank gaps. We provide upper bounds in terms of maximal and average disagreements in the agents’ rankings. Finally, we show that most of our bounds are tight. 2017-02 2017-04-03T22:03:26Z info:eu-repo/semantics/workingPaper info:eu-repo/semantics/publishedVersion http://repository.urosario.edu.co//handle/10336/13229 spa info:eu-repo/semantics/openAccess application/pdf Universidad del Rosario Facultad de Economía reponame:Repositorio Institucional EdocUR instname:Universidad del Rosario
institution EdocUR - Universidad del Rosario
collection DSpace
language Español (Spanish)
topic Teoría de búsqueda y emparejamiento
Teoría de los juegos
Matching
Roommate problem
Stability
Core
Rank gap
Bound
C78
spellingShingle Teoría de búsqueda y emparejamiento
Teoría de los juegos
Matching
Roommate problem
Stability
Core
Rank gap
Bound
C78
Jaramillo, Paula
Kayi, Cagatay
Klijn, Flip
Rank Gaps and the Size of the Core for Roommate Problems
description This paper deals with roommate problems (Gale and Shapley, 1962) that are solvable, i.e., have a non-empty core (set of stable matchings). We study the assortativeness of stable matchings and the size of the core by means of maximal and average rank gaps. We provide upper bounds in terms of maximal and average disagreements in the agents’ rankings. Finally, we show that most of our bounds are tight.
author2 Grupo de investigaciones. Facultad de Economía. Universidad del Rosario
author_facet Grupo de investigaciones. Facultad de Economía. Universidad del Rosario
Jaramillo, Paula
Kayi, Cagatay
Klijn, Flip
format Documento de trabajo (Working Paper)
author Jaramillo, Paula
Kayi, Cagatay
Klijn, Flip
author_sort Jaramillo, Paula
title Rank Gaps and the Size of the Core for Roommate Problems
title_short Rank Gaps and the Size of the Core for Roommate Problems
title_full Rank Gaps and the Size of the Core for Roommate Problems
title_fullStr Rank Gaps and the Size of the Core for Roommate Problems
title_full_unstemmed Rank Gaps and the Size of the Core for Roommate Problems
title_sort rank gaps and the size of the core for roommate problems
publisher Universidad del Rosario
publishDate 2017
url http://repository.urosario.edu.co//handle/10336/13229
_version_ 1645141101222297600
score 10,762304