Emparejamiento sin envidia
En economía y teoría de la elección social , un emparejamiento sin envidia (EFM) es un emparejamiento entre personas con "cosas", que es libre de envidia en el sentido de que a nadie le gustaría cambiar su "cosa" con la de otra persona. Este término se ha utilizado en varios contextos diferentes.
En gráficos bipartitos no ponderados
En una no ponderado bipartito gráfico G = ( X + Y , E ), una adaptación libre de envidias es un juego en el que ningún vértice igual en X es adyacente a un vértice emparejado en Y . [1] Suponga que los vértices de X representan personas, los vértices de Y representan casas, y un borde entre una persona x y una casa y representa el hecho de que x está dispuesto a vivir en y. Entonces, un EFM es una asignación parcial de casas a personas de manera que cada persona sin casa no envidia a ninguna persona con una casa, ya que de todos modos no le gusta ninguna casa asignada.
Cada coincidencia que satura X está libre de envidia, y cada coincidencia vacía está libre de envidia. Además, si | N G ( X ) | ≥ | X | ≥ 1 (donde N G ( X ) es el conjunto de vecinos de X en Y ), entonces G admite un EFM no vacío. [1] Esta es una relajación de la condición matrimonial de Hall , que dice que, si | N G ( X ') | ≥ | X '| para cada subconjunto X 'de X , existe una coincidencia de saturación de X.
En mercados con dinero
Considere un mercado en el que hay varios compradores y varios bienes, y cada bien puede tener un precio. Dado un vector de precios, cada comprador tiene un conjunto de demanda : un conjunto de paquetes que maximizan la utilidad del comprador sobre todos los paquetes (este conjunto puede incluir el paquete vacío, en caso de que el comprador considere que todos los paquetes son demasiado caros).
Un emparejamiento sin envidia de precios (dado un vector de precios) es un emparejamiento en el que cada agente recibe un paquete de su conjunto de demanda. Esto significa que ningún agente preferiría obtener otro paquete con los mismos precios. [2] Un ejemplo de esta configuración es el problema de la armonía del alquiler : hacer coincidir a los inquilinos (los agentes) con las habitaciones (los artículos) mientras se establece un precio para cada habitación.
Un precio sin envidia es un vector de precios para el que existe una coincidencia sin envidia. Es una relajación de un equilibrio walrasiano : un equilibrio walrasiano consiste en un precio EF y una igualación de EF, y además, cada artículo debe estar igualado o tener un precio cero. Se sabe que, en un equilibrio walrasiano, el emparejamiento maximiza la suma de valores, es decir, es un emparejamiento de peso máximo . Sin embargo, los ingresos del vendedor pueden ser bajos. Esto motiva la relajación de los precios EF, en los que el vendedor puede usar precios de reserva para aumentar los ingresos; consulte precios sin envidia para obtener más detalles.
En mercados sin dinero
El término coincidencia sin envidia se utiliza a menudo para denotar una condición más débil: coincidencia sin envidia justificada .
En el corte de pasteles
El término emparejamiento sin envidia también se ha utilizado en un contexto diferente: un algoritmo para mejorar la eficiencia del corte de pasteles sin envidia . [3]
Ver también
Referencias
- ^ a b Segal-Halevi, Erel; Aigner-Horev, Elad (28 de enero de 2019). "Emparejamientos sin envidia en gráficos bipartitos y sus aplicaciones a la división justa". arXiv : 1901.09527 [ cs.DS ].
- ^ Alaei, Saeed; Jain, Kamal; Malekian, Azarakhsh (24 de junio de 2010). "Equilibrios competitivos en mercados de emparejamiento bilateral con servicios públicos intransferibles". arXiv : 1006,4696 [ cs.GT ].
- ^ Sen, Sandip; Nuchia, Stephen W. (1 de agosto de 2001). Mejora de la optimización de n divisiones libres de envidia de agentes . Agentes inteligentes VIII . Apuntes de conferencias en Ciencias de la Computación. 2333 . Springer, Berlín, Heidelberg. págs. 277–289 . doi : 10.1007 / 3-540-45448-9_20 . ISBN 978-3-540-43858-8.
- Asignación justa de artículos
- Mercado (economía)
- Coincidencia estable
