Precios sin envidia

Muchos autores han estudiado el problema computacional de encontrar un vector de precios que maximice los ingresos del vendedor, sujeto a la ausencia de envidia de mercado.

Guruswami, Hartline, Karlin, Kempe, Kenyon y McSherry ^{[ 1 ]} (quienes introdujeron el término precios sin envidia ) estudiaron dos clases de funciones de utilidad: demanda unitaria y demanda centrada en un solo objetivo . Demostraron que:

• Calcular precios libres de envidia de mercado para maximizar los ingresos del vendedor es un problema de complejidad APX en ambos casos.
• En ambos casos se utiliza un algoritmo de aproximación logarítmica para calcular los ingresos.
• Existen algoritmos de tiempo polinomial para algunos casos especiales.

Balcan , Blum y Mansour ^{[ 2 ]} estudiaron dos escenarios: bienes con oferta ilimitada (por ejemplo, bienes digitales ) y bienes con oferta limitada . Demostraron que un precio único, seleccionado al azar, alcanza un ingreso esperado que es una aproximación no trivial del máximo bienestar social:

• Con una oferta ilimitada, un precio único aleatorio alcanza una aproximación logarítmica al máximo bienestar social. Esto se cumple incluso con valoraciones generales (no monótonas). Para un solo agente y m tipos de artículos, los ingresos son al menos 4 log (2 m ) del máximo bienestar; para n compradores, son al menos O(log ( n ) + log ( m )) del máximo bienestar.
• Con una oferta limitada, para valoraciones subaditivas , un precio único aleatorio logra ingresos dentro de 2 ^{O(√(log n loglog n ))} del bienestar máximo.
• En el caso de unidades múltiples, cuando ningún comprador requiere más de una fracción 1-ε de los artículos, un precio único aleatorio logra ingresos dentro de O(log n ) del bienestar máximo.
• Un límite inferior para compradores fraccionariamente subaditivos : cualquier precio único tiene una razón de aproximación de 2 ^{Ω(log 1/4 n )} .

Briest y Krysta ^{[ 3 ]} se centraron en bienes con suministro ilimitado y compradores con una sola preferencia : cada comprador desea solo un único conjunto de bienes. Demostraron que:

• El problema es débilmente NP-difícil incluso cuando los haces deseados están anidados .
• El problema es APX-difícil incluso para instancias muy dispersas.
• Existe un algoritmo de aproximación mediante factor logarítmico.

Briest ^{[ 4 ]} se centró en compradores con precios mínimos y demanda unitaria . Cada comprador tiene un subconjunto de artículos deseados y desea adquirir el artículo deseado más barato y asequible, dados los precios. Se centró en el caso de presupuesto uniforme. Demostró que, bajo ciertas suposiciones de complejidad razonables:

• El problema de precios de compra mínima con demanda unitaria y presupuestos uniformes no puede aproximarse en tiempo polinomial para algún ε > 0.
• Un problema un poco más general, en el que los consumidores se representan mediante una distribución de probabilidad explícita , es aún más difícil de aproximar.
• Todos los resultados también son válidos para compradores con una sola idea en mente .

Chen, Ghosh y Vassilvtskii ^{[ 5 ]} se centraron en artículos con sustituibilidad métrica : el valor del comprador i para el artículo j es v _i − c _i,j , y los costos de sustitución c _i,j , forman una métrica . Demuestran que

• Gracias a la sustituibilidad métrica, el problema puede resolverse exactamente en tiempo polinomial.
• Cuando los costos de sustitución son solo una métrica aproximada (es decir, satisfacen la desigualdad triangular de forma aproximada), el problema se vuelve NP-difícil.

Wang, Lu e Im ^{[ 6 ]} estudian el problema con restricciones de suministro dadas como un sistema de independencia sobre los artículos, como restricciones de matroide . Se centran en compradores con demanda unitaria .

Chen y Deng ^{[ 7 ]} estudian mercados de múltiples artículos: hay m artículos indivisibles con una oferta unitaria cada uno y n compradores potenciales, donde cada comprador desea comprar un solo artículo. Demuestran lo siguiente:

• Un algoritmo de tiempo polinomial para calcular un precio EF que maximice los ingresos cuando cada comprador evalúa como máximo dos artículos con una valoración positiva (utilizan el Teorema del Grafo Perfecto Fuerte ).
• El problema se vuelve NP-difícil si algunos compradores están interesados ​​en al menos tres artículos.

Cheung y Swamy ^{[ 8 ]} presentan algoritmos de aproximación de tiempo polinomial para agentes con una sola intención y un suministro limitado. Aproximan los ingresos con respecto al máximo bienestar social.

Hartline y Yan ^{[ 9 ]} estudian la maximización de ingresos utilizando mecanismos veraces sin información previa . También muestran la estructura simple de precios sin nvy y su conexión con el diseño de mecanismos veraces .

Chalermsook, Chuzhoy, Kannan y Khanna ^{[ 10 ]} estudian dos variantes del problema. En ambas variantes, cada comprador tiene un conjunto de "artículos deseados".

• Fijación de precios por unidad de demanda y precio mínimo de compra : cada comprador adquiere el artículo más barato que desea si su precio es menor o igual al presupuesto del agente; de ​​lo contrario, no compra nada.
• Fijación de precios sin concesiones : cada comprador adquiere todos los artículos que desea si su precio es igual o inferior al presupuesto del agente; de ​​lo contrario, no compra nada.

También estudian el problema de la fijación de precios en cabinas de peaje , un caso especial de fijación de precios unívoca en el que cada artículo es una arista en un grafo, y cada conjunto de artículos deseados es un camino en este grafo.

Chalermsook, Laekhanukit y Nanongkai ^{[ 11 ]} demuestran la dificultad de aproximación para una variante llamada fijación de precios de k-hipergrafos . También demuestran la dificultad para la fijación de precios de demanda unitaria mínima y la fijación de precios de enfoque único. ^{[ 12 ]}

Demaine, Feige, Hajiaghayi y Salavatipour ^{[ 13 ]} muestran resultados de dificultad de aproximación mediante reducción a partir del problema de cobertura única .

Anshelevich, Kar y Sekar ^{[ 14 ]} estudian la fijación de precios de EF en grandes mercados. Consideran tanto la maximización de ingresos como la maximización del bienestar.

Bilo, Flammini y Monaco ^{[ 15 ]} estudian la fijación de precios EF con demandas agudas, donde cada comprador está interesado en una cantidad fija de un artículo.

Colini-Baldeschi, Leonardi, Sankowski y Zhang ^{[ 16 ]} y Feldman, Fiat, Leonardi y Sankowski ^{[ 17 ]} estudian la fijación de precios de EF con agentes presupuestados.

Monaco, Sankowski y Zhang ^{[ 18 ]} estudian mercados de unidades múltiples. Analizan la maximización de ingresos bajo condiciones de ausencia de envidia de mercado y de envidia de agente. Consideran tanto la fijación de precios por artículo como la fijación de precios por paquete.

• Chen y Rudra ^{[ 19 ]} consideran una relajación del equilibrio walrasiano, en la que solo los ganadores deben estar libres de envidia. El objetivo es maximizar el número de compradores libres de envidia.
• Alon, Mansour y Tennenholtz ^{[ 20 ]} y Amanatidis, Fulla, Markakis y Sornat ^{[ 21 ]} consideran una relajación de la ausencia de envidia de mercado, en la que los compradores están organizados en una red social, los precios deben ser similares solo entre nodos que son adyacentes en la red, y los perdedores no deben envidiar.
• Flammini, Mauro y Tonelly ^{[ 22 ] [ 23 ]} consideran una relajación de la ausencia de envidia de mercado en la que cada agente ve solo los artículos de los agentes vecinos (en una red social dada).
• Elbassioni, Fouz y Swamy ^{[ 24 ]} consideran una relajación de la ausencia de envidia entre agentes, en la que solo los ganadores no deben envidiar. Consideran la fijación de precios en paquetes.
• Bérczi, Codazzi, Golak y Grigoriev ^{[ 25 ]} exploran el concepto de precios dinámicos donde los precios pueden adaptarse a las condiciones del mercado para mantener la equidad entre los consumidores, extendiendo las nociones tradicionales de ausencia de envidia más allá de los escenarios estáticos.