logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro