En economía y teoría de la elección social , un emparejamiento de envidia no justificada es un emparejamiento en un mercado de dos lados , en el que ningún agente prefiere la asignación de otro agente y simultáneamente es preferido por esa asignación.
Consideremos, por ejemplo, la tarea de encontrar médicos para realizar residencias en hospitales. Cada médico tiene una relación de preferencia sobre los hospitales, clasificando los hospitales de mejor a peor. Cada hospital tiene una relación de preferencia sobre los médicos, clasificándolos de mejor a peor. Cada médico puede trabajar como máximo en un hospital, y cada hospital puede emplear como máximo un número fijo de médicos (llamado capacidad del hospital). El objetivo es vincular médicos con hospitales, sin transferencias monetarias.
La envidia es una situación en la que algún médico d 1 , empleado en algún hospital h 1 , prefiere algún otro hospital h 2 , que emplea a algún otro médico d 2 (decimos que d 1 envidia a d 2 ). La envidia está justificada si, al mismo tiempo, h 2 prefiere d 1 a d 2 . Tenga en cuenta que, si d 1 ha justificado la envidia frente a h 2 , entonces h 2 ha justificado la envidia frente a d 1 ( h 2 envidia h 1 ). En este caso, también decimos que d 1 y h 2 son un par de bloqueo . Una coincidencia sin pares de bloqueo se denomina coincidencia sin envidia justificada (NJE) , o coincidencia que elimina la envidia justificada . [1] [2]
El emparejamiento sin envidia justificada es una relajación de dos condiciones diferentes:
En un problema de coincidencia de muchos a uno, existen coincidencias estables que pueden encontrarse mediante el algoritmo de Gale-Shapley . Por lo tanto, también existen coincidencias NJE. En general, puede haber muchas coincidencias NJE diferentes. El conjunto de todas las coincidencias NJE es un entramado . El conjunto de coincidencias estables (que son un subconjunto de las coincidencias NJE) es un punto fijo de un operador Tarsky en esa red. [3]
A menudo, los hospitales no sólo tienen cuotas superiores (capacidades), sino también cuotas más bajas : a cada hospital se le debe asignar al menos un número mínimo de médicos. [4] En tales problemas, es posible que no existan coincidencias estables (aunque es fácil comprobar si existe una coincidencia estable, ya que según el teorema de los hospitales rurales , en todas las coincidencias estables, el número de médicos asignados a cada hospital es idéntico). En tales casos, es natural comprobar si existe una coincidencia NJE. Una condición necesaria es que la suma de todas las cuotas inferiores sea como máximo el número de médicos (de lo contrario, no existe ninguna correspondencia factible). En este caso, si todos los pares médico-hospital son aceptables (cada médico prefiere cualquier hospital al desempleo, y cualquier hospital prefiere cualquier médico a un puesto vacante), entonces siempre existe una coincidencia NJE. [4]
Si no todos los pares son aceptables, es posible que no exista una coincidencia NJE. Es posible decidir la existencia de un EFM de la siguiente manera. Cree una nueva instancia del problema, en la que las cuotas superiores sean las cuotas inferiores del problema original y las cuotas inferiores sean 0. En el nuevo problema, siempre existe una coincidencia estable y se puede encontrar de manera eficiente. El problema original tiene una coincidencia NJE si, y sólo si, en la coincidencia estable del nuevo problema, todos los hospitales están llenos. [5]
El algoritmo se puede mejorar para encontrar una coincidencia NJE máxima. [6]
Por definición, en una comparación NJE, puede haber un médico d y un hospital h tal que d prefiera h sobre su empleador actual, pero h no prefiera d sobre ninguno de sus empleados actuales. A esto se le puede llamar una "envidia injustificada". Sólo en el raro caso de que cada médico pueda ser emparejado con su primera elección, existe una coincidencia sin envidia alguna. Cuando no existe tal "combinación totalmente libre de envidia", sigue siendo razonable encontrar coincidencias que minimicen la "cantidad de envidia". Hay varias formas de medir la cantidad de envidia, por ejemplo: la cantidad total de instancias de envidia de todos los médicos o la cantidad máxima de instancias de envidia por médico. [7]
{{cite journal}}: Citar diario requiere |journal=( ayuda )