En la teoría de la economía y la elección social , un emparejamiento por 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 es simultáneamente preferido por esa asignación.
Considere, por ejemplo, la tarea de emparejar médicos para la residencia en hospitales. Cada médico tiene una relación de preferencia en los hospitales, clasificando los hospitales de mejor a peor. Cada hospital tiene una relación de preferencia sobre los médicos, clasificando a los médicos 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 (lo que se denomina capacidad del hospital). El objetivo es emparejar a los médicos con los hospitales, sin transferencias monetarias.
La envidia es una situación en la que un médico d 1 , empleado en algún hospital h 1 , prefiere otro hospital h 2 , que emplea a otro médico d 2 (decimos que d 1 envidia a d 2 ). La envidia se justifica si, al mismo tiempo, h 2 prefiere d 1 sobre d 2 . Tenga en cuenta que, si d 1 ha justificado la envidia con h 2 , entonces h 2 ha justificado la envidia con d 1 ( h 2 envidia con 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 una coincidencia que elimina la envidia justificada . [1] [2]
Términos relacionados
El emparejamiento de envidia sin justificación es una relajación de dos condiciones diferentes:
- El emparejamiento sin envidia es un emparejamiento en el que no hay envidia en absoluto, ya sea justificada o no.
- El emparejamiento estable es un emparejamiento en el que no hay envidia justificada y, además, no hay desperdicio . Un emparejamiento tiene desperdicio si hay un médico d y un hospital h , de modo que d prefiere h sobre su empleador actual, h tiene algunos puestos vacantes y h prefiere d sobre un puesto vacante.
Estructura de celosía
En un problema de emparejamiento de muchos a uno, existen emparejamientos estables y pueden ser encontrados por el algoritmo de Gale-Shapley . Por lo tanto, las coincidencias NJE también existen. En general, puede haber muchas coincidencias NJE diferentes. El conjunto de todas las coincidencias de NJE es una celosía . El conjunto de coincidencias estables (que son un subconjunto de las coincidencias NJE) es un punto fijo de un operador de Tarsky en esa red. [3]
Cuotas superiores e inferiores
A menudo, los hospitales no solo 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 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 verificar si existe una coincidencia de NJE. Una condición necesaria es que la suma de todas las cuotas más bajas sea como máximo el número de médicos (de lo contrario, no existe ninguna coincidencia viable). 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 de 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 son las cuotas inferiores del problema original y las cuotas inferiores son 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 máxima de NJE. [6]
Minimizando la envidia injustificada
Por definición, en una comparación de NJE, puede haber un médico d y un hospital h tal que d prefiera h sobre su empleador actual, pero h no prefiere d sobre ninguno de sus empleados actuales. Esto puede llamarse una "envidia injustificada". Un emparejamiento sin envidia existe solo en el raro caso en el que cada médico puede ser emparejado con su primera opción. Cuando no existe una "coincidencia 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 casos de envidia entre todos los médicos o la cantidad máxima de casos de envidia por médico. [7]
Ver también
Referencias
- ↑ Abdulkadiroğlu, Atila; Sönmez, Tayfun (1 de junio de 2003). "Elección de escuela: un enfoque de diseño de mecanismo" . American Economic Review . 93 (3): 729–747. doi : 10.1257 / 000282803322157061 . hdl : 10161/2090 . ISSN 0002-8282 .
- ^ Abdulkadiroglu, Atila; Che, Yeon-Koo; Pathak, Parag A .; Roth, Alvin E .; Tercieux, Olivier (27 de marzo de 2017). "Minimizar la envidia justificada en la elección de la escuela: el diseño de OneApp de Nueva Orleans" . Cite journal requiere
|journal=
( ayuda ) - ^ Wu, Qingyun; Roth, Alvin E. (1 de mayo de 2018). "La celosía de los emparejamientos sin envidia". Juegos y comportamiento económico . 109 : 201–211. doi : 10.1016 / j.geb.2017.12.016 . ISSN 0899-8256 .
- ^ a b Fragiadakis, Daniel; Iwasaki, Atsushi; Troyan, Peter; Ueda, Suguru; Yokoo, Makoto (1 de enero de 2016). "Coincidencia a prueba de estrategias con cuotas mínimas". Transacciones ACM en Economía y Computación . 4 (1): 6: 1–6: 40. doi : 10.1145 / 2841226 . ISSN 2167-8375 . S2CID 1287011 .
- ^ Yokoi, Yu (17 de abril de 2017). "Emparejamientos sin envidia con cuotas más bajas". arXiv : 1704.04888 [ cs.GT ].
- ^ "¿Qué tan buenas son las coincidencias populares?" (PDF) . www.cse.iitm.ac.in . Archivado desde el original (PDF) el 17 de enero de 2019 . Consultado el 16 de enero de 2019 .
- ^ Tadenuma, Koichi (2011), "Asociación, solidaridad y envidia mínima en problemas de emparejamiento", en Fleurbaey, Marc; Salles, Maurice; Weymark, John A. (eds.), Ética social y economía normativa , Estudios sobre elección y bienestar, Springer Berlin Heidelberg, págs. 155-167, doi : 10.1007 / 978-3-642-17807-8_6 , ISBN 9783642178078