En economía y teoría de la elección social , una correspondencia sin envidia (CSE) es una correspondencia entre personas y "cosas", que no genera envidia en el sentido de que a ninguna persona le gustaría cambiar su "cosa" por la de otra persona. Este término se ha utilizado en varios contextos diferentes.
En un grafo bipartito no ponderado G = ( X + Y , E ), un emparejamiento sin envidia es un emparejamiento en el que ningún vértice no emparejado en X es adyacente a un vértice emparejado en Y . [1] Supongamos que los vértices de X representan personas, los vértices de Y representan casas y una arista 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 modo que cada persona sin casa no envidie a ninguna persona con una casa, ya que de todos modos no le gusta ninguna casa asignada.
Toda coincidencia que sature X está libre de envidia, y toda 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 de matrimonio de Hall , que dice que, si | N G ( X ')| ≥ |X'| para cada subconjunto X ' de X , entonces existe una coincidencia que satura X.
Consideremos 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 en todos los paquetes (este conjunto podría 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 demandas. Esto significa que ningún agente preferiría obtener otro paquete con los mismos precios. [2] Un ejemplo de esta situación es el problema de la armonía de alquileres : emparejar a los inquilinos (los agentes) con las habitaciones (los artículos) mientras se fija un precio para cada habitación.
Un precio sin envidia es un vector de precios para el cual existe una correspondencia sin envidia. Es una relajación de un equilibrio walrasiano : un equilibrio walrasiano consiste en un precio EF y una correspondencia EF, y además, cada artículo debe ser emparejado o tener precio cero. Se sabe que, en un equilibrio walrasiano, la correspondencia maximiza la suma de valores, es decir, es una correspondencia de peso máximo . Sin embargo, los ingresos del vendedor pueden ser bajos. Esto motiva la relajación de la fijación de precios EF, en la que el vendedor puede usar precios de reserva para aumentar los ingresos; consulte la fijación de precios sin envidia para obtener más detalles.
El término coincidencia sin envidia se utiliza a menudo para denotar una condición más débil: coincidencia sin envidia justificada .
El término emparejamiento sin envidia también se ha utilizado en un contexto diferente: un algoritmo para mejorar la eficiencia del corte de pastel sin envidia . [3]