Coincidencia sin envidia

El emparejamiento libre de envidia ( EFM ) es un  emparejamiento entre personas y "objetos" en el que no hay envidia en el sentido de que ninguna de las personas tiene el deseo de cambiar a un "objeto" que pertenece a otra persona. El término se utiliza en varios contextos diferentes. A continuación, la abreviatura OZ significa No Envy , y PbZ significa Matching without Envy .

En el mercado con dinero

Considere un mercado en el que hay varios compradores y varios objetos, y cada objeto puede tener un precio. Dado un vector de precios, cada cliente tiene un conjunto de solicitudes : el conjunto de conjuntos que maximiza la utilidad del cliente sobre otros conjuntos (este conjunto puede incluir un conjunto vacío si el cliente cree que todos los conjuntos son demasiado caros).

Un emparejamiento sin envidia (dado un vector de precios) es un emparejamiento en el que cada agente recibe un conjunto de su conjunto de conjuntos. Esto significa que ningún agente quiere recibir el paquete de otro agente por el mismo precio [1] . Un ejemplo de tales condiciones es el problema del alquiler justo : emparejar inquilinos (agentes) con viviendas (objetos) en presencia de un precio para cada vivienda.

Los precios sin envidia son el vector de precios para los que existe una igualación sin envidia. Esto es un debilitamiento del equilibrio walrasiano : el equilibrio walrasiano consiste en el costo PV y el CV coincidente y, además, cada objeto debe incluirse en la coincidencia o tener un precio cero. Se sabe que en el equilibrio walrasiano, el emparejamiento maximiza la suma de los valores, es decir, este es el emparejamiento de peso máximo . Sin embargo, los ingresos del vendedor pueden ser bajos. Esto induce una relajación de precios en la OZ, en la que el vendedor puede utilizar los precios mínimos aceptables para aumentar los ingresos [2] [3] [4] [5] [6] [7] .

En un mercado sin dinero

Considere el problema de combinar médicos para trabajar en clínicas. Cada médico tiene una preferencia por las clínicas (tiene una opinión comparativa de las clínicas de mala a buena), y cada clínica tiene una preferencia por los médicos (ordenando a los médicos de mejor a peor). Cada médico debe trabajar como máximo en una clínica, y cada clínica puede emplear un número fijo de médicos (llamado la capacidad de la clínica ). Tenemos que conseguir médicos para las clínicas. No se permiten cambios de moneda. Hay dos casos en los que tal arreglo puede ser "malo":

  1. Un emparejamiento tiene envidia razonable si hay un médico d y una clínica h tal que d prefiere h al trabajo actual y la clínica h prefiere al médico d sobre uno de los empleados actuales.
  2. Un emparejamiento está vacío si hay un médico d y una clínica h tal que d prefiere la clínica h al trabajo actual, y la clínica h tiene algunas vacantes, y h prefiere contratar d que dejar el lugar vacío.

Un emparejamiento sin envidia es un emparejamiento sin envidia justificada. Tal emparejamiento es un debilitamiento de la condición de estabilidad del emparejamiento : un emparejamiento estable está libre de envidia y no tiene vacíos.

Estructura de celosía

En el problema de emparejamiento de muchos a uno, existen emparejamientos estables y se pueden encontrar usando el algoritmo de Gale-Shapley . Por lo tanto, la OZ también existe. En general, puede haber muchas coincidencias de OD diferentes. El conjunto de todas las coincidencias de OD es una red . El conjunto de coincidencias estables (que es un subconjunto de las coincidencias OD) es un punto fijo del operador de Tarski en esta red [8] .

Cuotas superior e inferior

A menudo, las clínicas no solo tienen cuotas superiores (capacidades), sino también cuotas más bajas : cada clínica debe contratar una determinada cantidad mínima de médicos [9] . En tales problemas, los emparejamientos estables pueden no existir (aunque es fácil comprobar si existe un emparejamiento estable mediante el teorema de las clínicas rurales , según el cual el número de médicos asignados a cada clínica es el mismo en todos los emparejamientos estables). Bajo tales condiciones, es natural verificar si existe una coincidencia de OD. Una condición necesaria es que la suma de todas las cuotas inferiores no sea mayor que el número de médicos (de lo contrario, no hay solución factible). En este caso, si todos los binomios médico-clínica son aceptables (cada médico prefiere trabajar en algún lugar y no estar desempleado, y cada clínica prefiere contratar a algún médico para que no falte personal), entonces el emparejamiento OD siempre existe [9 ] .

Si no todos los pares son aceptables, es posible que no exista una coincidencia de OD. Puede averiguar sobre la existencia de PbZ de la siguiente manera. Vamos a crear un nuevo problema en el que las cuotas superiores sean iguales a las cuotas inferiores del problema original y las cuotas inferiores sean iguales a 0. En este nuevo problema, siempre existe una coincidencia estable y se puede encontrar de manera eficiente. El problema original tiene una coincidencia de OD si y solo si alguna clínica se llena en el nuevo problema [10] .

El algoritmo se puede mejorar para encontrar el EP máximo de la coincidencia [11] .

Minimización de la envidia

Como se definió anteriormente, emparejar sin envidia excluye la envidia justificada , donde el médico d está celoso de otro médico que ha sido asignado a la clínica h que d prefiere. Sin embargo, incluso en PbZ puede haber un médico d y una clínica h tal que d prefiera h , aunque se le asigne otro médico, pero h no ve al médico d como reemplazo de algunos de sus empleados existentes. Esto se puede llamar "envidia irrazonable". El emparejamiento sin envidia existe solo en casos raros, cuando cada médico puede ser designado para el lugar que más prefiera. Cuando tal "coincidencia completamente libre de envidia" no existe, es razonable encontrar coincidencias que minimicen la "cantidad de envidia". Hay varias formas de medir la magnitud de la envidia, como la suma de la envidia de todos los médicos o la envidia máxima [12] .

En grafos bipartitos

En un gráfico bipartito no ponderado , una coincidencia sin envidia es una coincidencia en la que ninguno de los vértices coincidentes de X es adyacente a un vértice coincidente de Y [13] . Imagina que los vértices X representan personas y los vértices Y representan casas, y el borde entre la persona x y la casa y representa el hecho de que a x le gustaría vivir en y . Entonces PbZ es una distribución parcial de casas para personas, de tal manera que cada persona sin hogar no envidie a la persona que tiene la casa, porque no quiere vivir en ninguna de las casas ofrecidas.

Cualquier emparejamiento que sature X no tiene envidia, y cualquier emparejamiento vacío no tiene envidia.

Además, si (donde está el conjunto de vecinos de X en Y ), entonces G admite una PbZ no vacía.

Este es un debilitamiento de la condición de Hall , que dice que si para cualquier subconjunto X ' de un conjunto X , entonces existe una partición completa de X en pares.

En cortar el pastel

El término emparejamiento sin envidia también se usó en otro contexto, en un algoritmo para mejorar la eficiencia de un cortador de pastel envidioso [14] .

Véase también

Notas

  1. ↑ Alaei, Jain, Malekian, 2010 .
  2. ↑ Guruswami, Hartline, Karlin et al., 2005 , pág. 1164-1173.
  3. ↑ Briest, 2008 , pág. 808–819.
  4. ↑ Chen, Ghosh, Vassilvitskii, 2011 , pág. 623–645.
  5. ↑ Wang, Lu, Im, 2010 , pág. 483–491.
  6. ↑ Feldman, Fiat, Leonardi, Sankowski, 2012 , pág. 532–549.
  7. ↑ Chen, Deng, 2014 , pág. 7:1–7:15.
  8. ↑ Wu, Roth, 2018 , pág. 201–211.
  9. ↑ 1 2 Fragiadakis, Iwasaki, Troyan et al., 2016 , pág. 6:1–6:40.
  10. ↑ Yokoi, 2017 .
  11. ↑ ¿Qué tan buenos son los emparejamientos populares? . www.cse.iitm.ac.in._ _ Consultado el 16 de enero de 2019. Archivado desde el original el 17 de enero de 2019.
  12. ↑ Tadenuma, 2011 , pág. 155–167.
  13. ↑ Segal-Halevi, Aigner-Horev, 2019 .
  14. ↑ Sen, Nuchia, 2001 , p. 277–289.

Literatura