Estabilidad, optimalidad y manipulación en problemas de emparejamiento con preferencias ponderadas
Autores: Pini, Maria Silvia; Rossi, Francesca; Venable, K. Brent; Walsh, Toby
Idioma: Inglés
Editor: MDPI
Año: 2013
Acceso abierto
Artículo científico
2013
Estabilidad, optimalidad y manipulación en problemas de emparejamiento con preferencias ponderadas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Problema de emparejamiento
Problema de matrimonio estable
Preferencias ponderadas
Matrimonios estables
Propiedades de manipulabilidad
Algoritmos existentes
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 25
Citaciones: Sin citaciones
El problema de emparejamiento estable (también conocido como problema de matrimonio estable) es un problema conocido de emparejar hombres con mujeres, de modo que ningún hombre y mujer, que no estén casados entre sí, se prefieran mutuamente. Tal problema tiene una amplia variedad de aplicaciones prácticas, que van desde emparejar médicos residentes con hospitales, hasta emparejar estudiantes con escuelas o, más generalmente, con cualquier mercado de dos lados. En el problema clásico de matrimonio estable, tanto hombres como mujeres expresan un orden de preferencia estricto sobre los miembros del otro sexo, de manera cualitativa. Aquí, consideramos problemas de matrimonio estable con preferencias ponderadas: cada hombre (respectivamente, mujer) proporciona una puntuación para cada mujer (respectivamente, hombre). Tales problemas son más expresivos que los problemas clásicos de matrimonio estable. Además, en algunas situaciones de la vida real, es más natural expresar puntuaciones (para modelar, por ejemplo, ganancias o costos) en lugar de una ordenación de preferencia cualitativa. En este contexto, definimos nuevas nociones de estabilidad y optimalidad, y proporcionamos algoritmos para encontrar matrimonios que sean estables y/o óptimos según estas nociones. Aunque la expresividad aumenta significativamente al adoptar preferencias ponderadas, mostramos que, en la mayoría de los casos, las soluciones deseadas pueden encontrarse adaptando algoritmos existentes para el problema clásico de matrimonio estable. También consideramos las propiedades de manipulabilidad de los procedimientos que devuelven tales matrimonios estables. Aunque sabemos que todos los procedimientos son manipulables al modificar las listas de preferencias o al truncarlas, aquí consideramos si la manipulación también puede ocurrir simplemente modificando los pesos mientras se preserva el orden y se evita la truncación. Resulta que, al agregar pesos, en algunos casos, podemos aumentar la posibilidad de manipulación, y esto no puede evitarse mediante ninguna restricción razonable sobre los pesos.
Descripción
El problema de emparejamiento estable (también conocido como problema de matrimonio estable) es un problema conocido de emparejar hombres con mujeres, de modo que ningún hombre y mujer, que no estén casados entre sí, se prefieran mutuamente. Tal problema tiene una amplia variedad de aplicaciones prácticas, que van desde emparejar médicos residentes con hospitales, hasta emparejar estudiantes con escuelas o, más generalmente, con cualquier mercado de dos lados. En el problema clásico de matrimonio estable, tanto hombres como mujeres expresan un orden de preferencia estricto sobre los miembros del otro sexo, de manera cualitativa. Aquí, consideramos problemas de matrimonio estable con preferencias ponderadas: cada hombre (respectivamente, mujer) proporciona una puntuación para cada mujer (respectivamente, hombre). Tales problemas son más expresivos que los problemas clásicos de matrimonio estable. Además, en algunas situaciones de la vida real, es más natural expresar puntuaciones (para modelar, por ejemplo, ganancias o costos) en lugar de una ordenación de preferencia cualitativa. En este contexto, definimos nuevas nociones de estabilidad y optimalidad, y proporcionamos algoritmos para encontrar matrimonios que sean estables y/o óptimos según estas nociones. Aunque la expresividad aumenta significativamente al adoptar preferencias ponderadas, mostramos que, en la mayoría de los casos, las soluciones deseadas pueden encontrarse adaptando algoritmos existentes para el problema clásico de matrimonio estable. También consideramos las propiedades de manipulabilidad de los procedimientos que devuelven tales matrimonios estables. Aunque sabemos que todos los procedimientos son manipulables al modificar las listas de preferencias o al truncarlas, aquí consideramos si la manipulación también puede ocurrir simplemente modificando los pesos mientras se preserva el orden y se evita la truncación. Resulta que, al agregar pesos, en algunos casos, podemos aumentar la posibilidad de manipulación, y esto no puede evitarse mediante ninguna restricción razonable sobre los pesos.