La fijación de precios sin envidia [1] es una especie de asignación justa de artículos . Hay un solo vendedor que posee algunos artículos y un conjunto de compradores que están interesados en estos artículos. Los compradores tienen diferentes valoraciones de los artículos y tienen una función de utilidad cuasilineal ; esto significa que la utilidad que obtiene un agente de un paquete de artículos es igual al valor del agente para el paquete menos el precio total de los artículos en el paquete. El vendedor debe determinar un precio para cada artículo y vender los artículos a algunos de los compradores, de modo que no haya envidia . Se consideran dos tipos de envidia:
Las condiciones sin envidia garantizan que el mercado sea estable y que los compradores no se resientan con el vendedor. Por definición, cada asignación de mercado libre de envidia también está libre de envidia de agente, pero no al revés.
Siempre existe una asignación libre de envidia en el mercado (que también es libre de envidia del agente): si los precios de todos los artículos son muy altos y no se vende ningún artículo (todos los compradores obtienen un paquete vacío), entonces no hay envidia, ya que ningún agente quisiera obtener un paquete por precios tan altos. Sin embargo, tal asignación es muy ineficaz. El desafío en la fijación de precios sin envidia es encontrar precios sin envidia que también maximicen uno de los siguientes objetivos:
Un equilibrio walrasiano es un precio sin envidia del mercado con el requisito adicional de que todos los artículos con un precio positivo deben asignarse (todos los artículos no asignados deben tener un precio cero). Maximiza el bienestar social. ^ Sin embargo, es posible que no exista un equilibrio walrasiano (se garantiza que existe solo cuando los agentes tienen valoraciones brutas de sustitución ). Además, incluso cuando existe, los ingresos de los vendedores pueden ser bajos. Permitir que el vendedor descarte algunos artículos podría ayudarlo a obtener mayores ingresos.
Muchos autores estudiaron el problema computacional de encontrar un vector de precios que maximice los ingresos del vendedor, sujeto a la ausencia de envidia del mercado.
Guruswami, Hartline, Karlin, Kempe, Kenyon y McSherry [1] (que introdujeron el término precio sin envidia ) estudiaron dos clases de funciones de utilidad: demanda unitaria y unidireccional . Mostraron: