Rank gaps and the size of the core for roommate problems

Abstract

Este artículo trata con problemas de asignación de compañeros de cuarto (Gale and Shapley, 1962) que son solucionables, i.e., tienen un núcleo no vacío (conjuntos de asignaciones de emparejamiento estables). Nosotros estudiamos la selectividad de las asignaciones de emparejamiento estables y el tamaño del núcleo por medio de las brechas máximas y promedio en los rankings. Proveemos límites superiores en términos de los desacuerdos máximos y promedios de los rankings de los agentes. Finalmente, mostramos que la mayoría de nuestros límites son estrictos.

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.