Precios sin envidia

La fijación de precios sin envidia ^[1] es una especie de asignación justa de artículos . Hay un único vendedor que posee algunos artículos y un conjunto de compradores que están interesados en estos artículos. Los compradores tienen valoraciones diferentes de los artículos y tienen una función de utilidad cuasilineal ; esto significa que la utilidad que un agente obtiene de un paquete de artículos es igual al valor del agente por el paquete menos el precio total de los artículos del paquete. El vendedor debe determinar un precio para cada artículo y vender los artículos a algunos de los compradores, de manera que no haya envidia . Se consideran dos tipos de envidia:

La envidia del agente significa que algún agente asigna una mayor utilidad (una mayor diferencia valor-precio) a un paquete asignado a otro agente.
La envidia del mercado significa que algún agente asigna una mayor utilidad (una mayor diferencia valor-precio) a cualquier paquete.

Las condiciones de no envidia garantizan que el mercado sea estable y que los compradores no se resientan con el vendedor. Por definición, toda asignación libre de envidia del mercado también está libre de envidia de los agentes, pero no al revés.

Siempre existe una asignación libre de envidia en el mercado (que también está libre de envidia de los agentes): 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 A ningún agente le gustaría recibir ningún paquete por precios tan altos. Sin embargo, tal asignación es muy ineficiente. El desafío de los precios sin envidia es encontrar precios sin envidia que también maximicen uno de los siguientes objetivos:

El bienestar social : la suma de las utilidades de los compradores;
Los ingresos (o ganancias ) del vendedor : la suma de los precios pagados por los compradores.

La fijación de precios sin envidia está relacionada, pero no es idéntica, con otros problemas de asignación justa:

En la asignación de artículos sin envidia , no se permiten pagos monetarios.
En el problema de la armonía de alquileres , se permiten pagos monetarios y los agentes son cuasilineales, pero todos los objetos deben asignarse (y cada agente debe recibir exactamente un objeto).

Resultados

Un equilibrio walrasiano es una fijación de precios libre de 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 existirá sólo cuando los agentes tengan valoraciones sustitutivas brutas ). Además, incluso cuando exista, los ingresos de los vendedores podrían ser bajos. Permitir que el vendedor descarte algunos artículos podría ayudarlo a obtener mayores ingresos.

Maximizar los ingresos del vendedor sujeto a la ausencia de envidia del mercado

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] (quienes introdujeron el término fijación de precios sin envidia ) estudiaron dos clases de funciones de utilidad: demanda unitaria y unidireccionales . Mostraron:

Calcular precios libres de envidia del mercado para maximizar los ingresos del vendedor es APX-difícil en ambos casos.
En ambos casos existe un algoritmo de aproximación logarítmica para los ingresos.
Existen algoritmos de tiempo polinomial para algunos casos especiales.

Balcan , Blum y Mansour ^[2] estudiaron dos entornos: 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 bienestar social máximo:

Con una oferta ilimitada, un precio único aleatorio logra una aproximación de factor logarítmico al bienestar social máximo. Esto es cierto incluso con valoraciones generales (no monótonas). Para un solo agente y m tipos de elementos, los ingresos son al menos 4 log (2 m ) del bienestar máximo; para n compradores, es al menos O(log ( n ) + log ( m )) del bienestar máximo.
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 fraccionalmente subaditivos : cualquier precio único tiene una relación de aproximación de 2 ^{Ω (log ^1/4n )} .

Briest y Krysta ^[3] se centraron en bienes con oferta ilimitada y compradores decididos : cada comprador sólo quiere un único paquete de bienes. Demostraron que:

El problema es débilmente NP-hard incluso cuando los paquetes deseados están anidados .
El problema es APX-hard incluso en casos muy escasos.
Existe un algoritmo de aproximación de factor logarítmico.

Briest ^[4] se centró en los compradores con precios mínimos de demanda unitaria . Cada uno de estos compradores tiene un subconjunto de artículos buscados y le gustaría comprar el artículo buscado más barato y asequible, dados los precios. Se centró en el caso del presupuesto uniforme. Demostró que, bajo algunos supuestos de complejidad razonables:

El problema de fijación de precios de compra mínima por demanda unitaria con presupuestos uniformes no se puede aproximar en politiempo para algunos ε > 0.
Un problema ligeramente más general, en el que los consumidores se dan como una distribución de probabilidad explícita, es aún más difícil de aproximar.
Todos los resultados se aplican también a los compradores decididos .

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 . ellos muestran que

Con la sustituibilidad métrica, el problema se puede resolver exactamente en tiempo polinomial.
Cuando los costos de sustitución son sólo aproximadamente una métrica (es decir, satisfacen aproximadamente la desigualdad del triángulo ), el problema se vuelve NP-difícil.

Wang, Lu e Im ^[6] estudian el problema de las restricciones de oferta dadas como un sistema de independencia sobre los artículos, como las restricciones matroides . Se centran en compradores de demanda unitaria .

Chen y Deng ^[7] estudian mercados de artículos múltiples: hay m artículos indivisibles con oferta unitaria cada uno y n compradores potenciales donde cada comprador quiere comprar un solo artículo. Ellos muestran:

Un algoritmo politime para calcular un precio de EF que maximiza los ingresos cuando cada comprador evalúa como máximo dos artículos con una valoración positiva (utilizan el teorema del gráfico 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 politime para agentes decididos con oferta limitada. Se aproximan a los ingresos con respecto al máximo bienestar social.

Hartline y Yan ^[9] estudian la maximización de ingresos utilizando mecanismos veraces sin previo aviso . También muestran la estructura simple de la fijación de precios sin nvy y su conexión con un diseño de mecanismo veraz.

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

Precio de compra mínimo por demanda unitaria : cada comprador compra el artículo deseado más barato si su precio es ≤ el presupuesto del agente; de lo contrario no compra nada.
Fijación de precios fija : cada comprador compra todos los artículos que desea si su precio es ≤ el presupuesto del agente; de lo contrario no compra nada.

También estudian el problema de fijación de precios en las cabinas de peaje , un caso especial de fijación de precios con un solo propósito en el que cada artículo es una ventaja en un gráfico, y cada conjunto de artículos buscados es una ruta en este gráfico.

Chalermsook, Laekhanukit y Nanongkai ^[11] demuestran la dureza de aproximación de una variante llamada fijación de precios k-hypergraph . También demuestran dureza para las compras mínimas según la demanda unitaria y los precios decididos. ^[12]

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

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

Bilo, Flammini y Monaco ^[15] estudian los precios EF con demandas marcadas, 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 los precios de EF con agentes presupuestados.

Monaco, Sankowski y Zhang ^[18] estudian los mercados de unidades múltiples. Estudian la maximización de ingresos tanto en condiciones de ausencia de envidia del mercado como de ausencia de envidia de los agentes. Consideran tanto el precio de los artículos como el precio de los paquetes.

Nociones relajadas de ausencia de envidia

Chen y Rudra ^[19] consideran una relajación del equilibrio walrasiano, en el que sólo 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 del mercado libre de envidia, en la que los compradores están organizados en una red social, los precios deberían ser similares sólo entre nodos adyacentes. en la red, y los perdedores no deben tener envidia.
Flammini, Mauro y Tonelly ^[22]^[23] consideran una relajación de la envidia del mercado en la que cada agente ve sólo los artículos de los agentes vecinos (en una red social determinada).
Elbassioni, Fouz y Swamy ^[24] consideran una relajación de la ausencia de envidia del agente, en la que sólo los ganadores no deben envidiar. Consideran la fijación de precios por paquetes.
Bérczi, Codazzi, Golak y Grigoriev ^[25] exploran el concepto de fijación de precios dinámica, 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.

Ver también

Oráculo de la demanda : un oráculo que se utiliza a menudo en algoritmos para fijar precios sin envidia.

Referencias

^ ab Guruswami, Venkatesan; Hartline, Jason D.; Karlin, Anna R.; Kempe, David; Kenyon, Claire; McSherry, Frank (23 de enero de 2005). Sobre precios sin envidia que maximizan las ganancias. Sociedad de Matemática Industrial y Aplicada. págs. 1164-1173. ISBN 978-0-89871-585-9.
^ Balcan, María-Florina; Blum, Avrim; Mansour, Yishay (2008). "Precio de artículos para maximizar los ingresos". En Fortnow, Lanza; Riedl, Juan; Sandholm, Tuomas (eds.). Actas de la 9ª Conferencia ACM sobre Comercio Electrónico (EC-2008), Chicago, IL, EE. UU., 8 al 12 de junio de 2008 . págs. 50–59. doi :10.1145/1386790.1386802. ISBN 9781605581699. S2CID 53038874.
^ Briest, Patricio; Krysta, Piotr (22 de enero de 2006). "Precios de suministro ilimitados y decididos en casos escasos". Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmo discreto - SODA '06 . Refresco '06. Miami, Florida: Sociedad de Matemáticas Industriales y Aplicadas. págs. 1093-1102. doi :10.1145/1109557.1109678. ISBN 978-0-89871-605-4. S2CID 4191038.
^ Briest, Patricio (2008). "Presupuestos uniformes y el problema de los precios sin envidia". En Aceto, Luca; Damgard, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. vol. 5125. Springer Berlín Heidelberg. págs. 808–819. CiteSeerX 10.1.1.205.433 . doi :10.1007/978-3-540-70575-8_66. ISBN 9783540705758.
^ Chen, Ning; Ghosh, Arpita; Vassilvitskii, Sergei (2011). "SIAM (Sociedad de Matemática Industrial y Aplicada)". Revista SIAM de Computación . 40 (3): 623–645. CiteSeerX 10.1.1.193.6235 . doi :10.1137/080740970.
^ Soy, Sungjin; Lu, Pinyan; Wang, Yajun (2010). "Precios sin envidia con restricciones generales de oferta". En Saberi, Amin (ed.). Internet y economía de redes . Apuntes de conferencias sobre informática. vol. 6484. Berlín, Heidelberg: Springer. págs. 483–491. doi :10.1007/978-3-642-17572-5_41. ISBN 978-3-642-17572-5.
^ Chen, Ning; Deng, Xiaotie (1 de febrero de 2014). "Precios sin envidia en mercados de artículos múltiples". Transacciones ACM sobre algoritmos . 10 (2): 7:1–7:15. CiteSeerX 10.1.1.297.784 . doi :10.1145/2567923. ISSN 1549-6325. S2CID 15309106.
^ Cheung, M.; Swamy, C. (1 de octubre de 2008). "Algoritmos de aproximación para problemas de maximización de beneficios resueltos y libres de envidia con oferta limitada". 2008 49º Simposio anual del IEEE sobre fundamentos de la informática . págs. 35–44. doi :10.1109/FOCS.2008.15. ISBN 978-0-7695-3436-7. S2CID 1318192.
^ Devanur, Nikhil R.; Hartline, Jason D.; Yan, Qiqi (1 de marzo de 2015). "Libertad de envidia y diseño de mecanismos sin previo aviso". Revista de teoría económica . 156 : 103-143. arXiv : 1212.3741 . doi :10.1016/j.jet.2014.08.001. ISSN 0022-0531. S2CID 17990320.
^ Chalermsook, Parinya; Chuzhoy, Julia; Kannan, Sampath; Khanna, Sanjeev (2012). "Resultados de dureza mejorados para problemas de fijación de precios de maximización de beneficios con suministro ilimitado". En Gupta, Anupam; Jansen, Klaus; Rolim, José; Servedio, Rocco (eds.). Aproximación, aleatorización y optimización combinatoria. Algoritmos y Técnicas . Apuntes de conferencias sobre informática. vol. 7408. Berlín, Heidelberg: Springer. págs. 73–84. doi :10.1007/978-3-642-32512-0_7. ISBN 978-3-642-32512-0.
^ Chalermsook, P.; Laekhanukit, B.; Nanongkai, D. (1 de octubre de 2013). "Conjunto independiente, coincidencia inducida y fijación de precios: conexiones y durezas de aproximación ajustadas (tiempo subexponencial)". 2013 54º Simposio Anual del IEEE sobre Fundamentos de la Informática . págs. 370–379. arXiv : 1308.2617 . doi :10.1109/FOCS.2013.47. ISBN 978-0-7695-5135-7. S2CID 972321.
^ Chalermsook, Parinya; Laekhanukit, Bundit; Nanongkai, Danupon (6 de enero de 2013). "Productos gráficos revisados: dureza de aproximación estricta de la coincidencia inducida, dimensión Poset y más". Actas del Simposio anual ACM-SIAM de 2013 sobre algoritmos discretos. Actas. Sociedad de Matemática Industrial y Aplicada. págs. 1557-1576. arXiv : 1212.4129 . doi :10.1137/1.9781611973105.112. ISBN 978-1-61197-251-1. S2CID 6556716 . Consultado el 4 de abril de 2021 .
^ Demaine, Erik D.; Feige, Uriel; Hajiaghayi, Mohammad Taghi; Salavatipour, Mohammad R. (1 de enero de 2008). "La combinación puede ser difícil: la proximidad del problema de cobertura única". Revista SIAM de Computación . 38 (4): 1464-1483. doi :10.1137/060656048. ISSN 0097-5397. S2CID 12248889.
^ Anshelevich, Elliot; Kar, Koushik; Sekar, Shreyas (9 de agosto de 2017). "Precios sin envidia en los grandes mercados: aproximación de ingresos y bienestar". Transacciones ACM sobre Economía y Computación . 5 (3): 16:1–16:42. doi :10.1145/3105786. ISSN 2167-8375. S2CID 7008965.
^ Bilò, Vittorio; Flammini, Michele; Mónaco, Gianpiero (1 de febrero de 2017). "Aproximación al problema de maximización de ingresos con fuertes demandas". Informática Teórica . 662 : 9–30. arXiv : 1312.3892 . doi : 10.1016/j.tcs.2016.12.002 . ISSN 0304-3975.
^ Colini-Baldeschi, Riccardo; Leonardo, Stefano; Sankowski, Piotr; Zhang, Qiang (2014). "Maximización de ingresos en subastas de precio fijo sin envidia con presupuestos". En Liu, Tie-Yan; Qi, Qi; Vosotros, Yinyu (eds.). Economía de la Web y de Internet . Apuntes de conferencias sobre informática. vol. 8877. Cham: Editorial Internacional Springer. págs. 233–246. doi :10.1007/978-3-319-13129-0_18. hdl : 11573/754515 . ISBN 978-3-319-13129-0.
^ Feldman, Michal ; Fiat, Amós; Leonardo, Stefano; Sankowski, Piotr (2012). "Maximización de ingresos con presupuestos en subastas multiunidades sin envidia". Actas de la 13ª Conferencia ACM sobre Comercio Electrónico . CE '12. Nueva York, NY, Estados Unidos: ACM. págs. 532–549. doi :10.1145/2229012.2229052. ISBN 9781450314152. S2CID 15639601.
^ Mónaco, Gianpiero; Sankowski, Piotr; Zhang, Qiang (25 de julio de 2015). "Precios sin envidia para maximizar los ingresos para recursos homogéneos". Actas de la 24ª Conferencia Internacional sobre Inteligencia Artificial . IJCAI'15. Buenos Aires, Argentina: AAAI Press: 90–96. ISBN 978-1-57735-738-4.
^ Chen, Ning; Rudra, Atri (1 de septiembre de 2008). "Equilibrio de Walras: dureza, aproximaciones e instancias manejables". Algorítmica . 52 (1): 44–64. doi :10.1007/s00453-007-9103-9. ISSN 1432-0541. S2CID 18839423.
^ Alon, Noga; Mansur, Yishay; Tenneholtz, Moshe (16 de junio de 2013). "Precios diferenciales con aversión a la inequidad en las redes sociales". Actas de la decimocuarta conferencia ACM sobre comercio electrónico . CE '13. Filadelfia, Pensilvania, EE.UU.: Asociación de Maquinaria de Computación. págs. 9–24. doi :10.1145/2492002.2482545. ISBN 978-1-4503-1962-1.
^ Amanatidis, Georgios; Fulla, Pedro; Markakis, Evangelos; Sornat, Krzysztof (17 de diciembre de 2019). "Precios de aversión a la inequidad en las redes sociales: algoritmos de aproximación y resultados de dureza". arXiv : 1606.06664 [cs.GT].
^ Flammini, Michele; Mauro, Manuel; Tonelli, Matteo (1 de abril de 2019). "Sobre la ausencia de envidia social en mercados de unidades múltiples". Inteligencia artificial . 269 : 1–26. doi : 10.1016/j.artint.2018.12.003 . ISSN 0004-3702. S2CID 19205358.
^ "Precios de aversión a la desigualdad en mercados de unidades múltiples". iris.gssi.it. Consultado el 5 de abril de 2021 .
^ Elbassioni, Khaled; Fouz, Mahmoud; Swamy, Chaitanya (2010). "Algoritmos de aproximación para problemas de maximización de beneficios no resueltos con oferta limitada". En Saberi, Amin (ed.). Internet y economía de redes . Apuntes de conferencias sobre informática. vol. 6484. Berlín, Heidelberg: Springer. págs. 462–472. arXiv : 1312.0137 . doi :10.1007/978-3-642-17572-5_39. ISBN 978-3-642-17572-5. S2CID 14124011.
^ "Libre de envidia dinámica en los precios" . Consultado el 10 de abril de 2024 .