En economía y teoría de la elección social , un emparejamiento sin envidia justificada es un emparejamiento en un mercado bilateral en el que ningún agente prefiere la asignación de otro agente y al mismo tiempo es preferido por esa asignación.
Consideremos, por ejemplo, la tarea de emparejar médicos para realizar residencias en hospitales. Cada médico tiene una relación de preferencia con respecto a los hospitales, ordenando los hospitales del mejor al peor. Cada hospital tiene una relación de preferencia con respecto a los médicos, ordenando a los médicos del mejor al peor. Cada médico puede trabajar en un hospital como máximo, y cada hospital puede emplear como máximo un número fijo de médicos (denominado capacidad del hospital). El objetivo es emparejar médicos con hospitales, sin transferencias monetarias.
La envidia es una situación en la que un doctor d 1 , empleado en un hospital h 1 , prefiere otro hospital h 2 , que emplea a otro doctor d 2 (decimos que d 1 envidia a d 2 ). La envidia está justificada si, al mismo tiempo, h 2 prefiere a d 1 sobre d 2 . Nótese que, si d 1 tiene envidia justificada con respecto a h 2 , entonces h 2 tiene envidia justificada con respecto a d 1 ( h 2 envidia a h 1 ). En este caso, también decimos que d 1 y h 2 son un par bloqueante . Una coincidencia sin pares bloqueantes se denomina coincidencia sin envidia justificada (NJE) o una coincidencia que elimina la envidia justificada . [1] [2]
La correspondencia entre envidia no justificada y realidad es una relajación de dos condiciones diferentes:
En un problema de emparejamiento de varios a uno, existen emparejamientos estables que se pueden encontrar mediante el algoritmo de Gale-Shapley . Por lo tanto, también existen emparejamientos NJE. En general, puede haber muchos emparejamientos NJE diferentes. El conjunto de todos los emparejamientos NJE es una red . El conjunto de emparejamientos estables (que son un subconjunto de los emparejamientos NJE) es un punto fijo de un operador de Tarsky en esa red. [3]
A menudo, los hospitales no sólo tienen cuotas superiores (capacidades), sino también cuotas inferiores : cada hospital debe tener asignado al menos un número mínimo de médicos. [4] En tales problemas, puede que no existan emparejamientos estables (aunque es fácil comprobar si existe un emparejamiento estable, ya que según el teorema de los hospitales rurales , en todos los emparejamientos estables, el número de médicos asignados a cada hospital es idéntico). En tales casos, es natural comprobar si existe un emparejamiento 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 ningún emparejamiento factible). En este caso, si todos los pares médico-hospital son aceptables (todos los médicos prefieren cualquier hospital al desempleo, y cualquier hospital prefiere cualquier médico a un puesto vacante), entonces siempre existe un emparejamiento NJE. [4]
Si no todos los pares son aceptables, entonces podría no existir 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 solo si, en la coincidencia estable del nuevo problema, todos los hospitales están llenos. [5]
El algoritmo se puede mejorar para encontrar una correspondencia NJE máxima. [6]
Por definición, en un emparejamiento NJE, puede haber un médico d y un hospital h de modo que d prefiera a h sobre su empleador actual, pero h no prefiera a d sobre ninguno de sus empleados actuales. Esto puede llamarse una "envidia injustificada". Un emparejamiento sin envidia en absoluto existe solo en el caso poco frecuente en que cada médico pueda ser emparejado con su primera opción. Cuando no existe un "emparejamiento totalmente libre de envidia", sigue siendo razonable encontrar emparejamientos que minimicen la "cantidad de envidia". Hay varias formas de medir la cantidad de envidia, por ejemplo: la cantidad total de casos de envidia sobre todos los médicos, o la cantidad máxima de casos de envidia por médico. [7]
{{cite journal}}: Requiere citar revista |journal=( ayuda )