Precios sin envidia

Tipo de asignación justa de artículos

La fijación de precios sin envidia ^[1] es un tipo 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 diferentes valoraciones de los artículos y tienen una función de utilidad cuasilineal ; esto significa que la utilidad que un agente obtiene de un conjunto de artículos es igual al valor que el agente le da al conjunto menos el precio total de los artículos en el conjunto. 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:

• La envidia de agentes significa que algún agente asigna una utilidad mayor (una diferencia valor-precio mayor) 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 resientan al vendedor. Por definición, toda asignación sin envidia del mercado también está libre de envidia del agente, pero no al revés.

Siempre existe una asignación sin envidia del mercado (que también es sin 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 querría obtener ningún paquete por precios tan altos. Sin embargo, tal asignación es muy ineficiente. 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:

• 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, a 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 del alquiler , 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 sin envidia del mercado con el requisito adicional de que todos los artículos con un precio positivo deben ser asignados (todos los artículos no asignados deben tener un precio cero). Maximiza el bienestar social. ^ Sin embargo, un equilibrio walrasiano podría no existir (se garantiza que exista solo cuando los agentes tienen valoraciones sustitutivas brutas ). Además, incluso cuando existe, los ingresos de los vendedores pueden ser bajos. Permitirle al vendedor descartar algunos artículos podría ayudarlo a obtener un ingreso mayor.

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: la demanda unitaria y la de demanda única . Demostraron que:

• Calcular precios libres de envidia del mercado para maximizar los ingresos del vendedor es extremadamente difícil en ambos casos.
• Existe un algoritmo de aproximación logarítmica para los ingresos en ambos casos.
• 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 bienestar social máximo:

• Con una oferta ilimitada, un precio único aleatorio logra una aproximación logarítmica del bienestar social máximo. Esto es cierto incluso con valoraciones generales (no monótonas). Para un solo agente y m tipos de artículos, el ingreso es 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 de 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 individual tiene una relación de aproximación de 2 ^{Ω(log 1/4 n )} .

Briest y Krysta ^[3] se centraron en bienes con oferta ilimitada y compradores con una sola mente : cada comprador solo quiere un único paquete de bienes. Demostraron que:

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

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

• El problema de fijación de precios de compra mínima con demanda unitaria y presupuestos uniformes no puede aproximarse en politiempo para algún ε > 0.
• Un problema un poco 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 con una mentalidad única .

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

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

Wang, Lu e Im ^[6] estudian el problema de las restricciones de oferta que se dan como un sistema de independencia sobre los artículos, como las restricciones matroidales . Se centran en los 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 quiere comprar un solo artículo. Muestran:

• Un algoritmo de politiempo para calcular un precio 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 Grafo Perfecto Fuerte ).
• El problema se vuelve NP-complicado si algunos compradores están interesados ​​en al menos tres artículos.

Cheung y Swamy ^[8] presentan algoritmos de aproximación politemporal para agentes monolíticos con oferta limitada. Aproximan los ingresos con respecto al máximo bienestar social.

Hartline y Yan ^[9] estudian la maximización de ingresos utilizando mecanismos veraces sin previos . También muestran la estructura simple de la fijación de precios sin previos 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".

• Precio mínimo de compra por unidad de demanda : cada comprador compra el artículo más barato que desea si su precio es ≤ el presupuesto del agente; de ​​lo contrario, no compra nada.
• Fijación de precios unidireccional : 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 de peaje , un caso especial de fijación de precios unidireccional en el que cada artículo es una arista en un gráfico y cada conjunto de artículos deseados es una ruta en este gráfico.

Chalermsook, Laekhanukit y Nanongkai ^[11] demuestran la dureza de aproximación para una variante llamada fijación de precios de k-hipergrafos . También demuestran la dureza para la compra mínima con demanda unitaria y la fijación de precios unidireccional. ^[12]

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

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

Bilo, Flammini y Monaco ^[15] estudian la fijación de precios EF con demandas estrictas, 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 multiunidades. Estudian la maximización de ingresos tanto en condiciones de ausencia de envidia del mercado como de envidia del agente. Consideran tanto la fijación de precios de los artículos como 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 de la libertad de mercado ante la envidia, en la que los compradores están organizados en una red social, los precios deberían ser similares solo entre los nodos 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 del mercado en la que cada agente ve únicamente los elementos de los agentes vecinos (en una red social determinada).
• Elbassioni, Fouz y Swamy ^[24] consideran una relajación de la libertad de envidia de los agentes, 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 precios dinámicos, según el cual 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.

Véase también

• Oráculo de demanda : un oráculo que suele utilizarse en algoritmos para fijar precios sin envidia.

Referencias

1. Guruswami, Venkatesan; Hartline, Jason D.; Karlin, Anna R.; Kempe, David; Kenyon, Claire; McSherry, Frank (23 de enero de 2005). Sobre la fijación de precios sin envidia que maximiza las ganancias. Society for Industrial and Applied Mathematics. págs. 1164–1173. ISBN 978-0-89871-585-9.
2. Balcan, Maria-Florina; Blum, Avrim; Mansour, Yishay (2008). "Fijación de precios de artículos para maximizar los ingresos". En Fortnow, Lance; Riedl, John; Sandholm, Tuomas (eds.). Actas de la 9.ª Conferencia de la ACM sobre comercio electrónico (EC-2008), Chicago, IL, EE. UU., 8-12 de junio de 2008. págs. 50-59. doi :10.1145/1386790.1386802. ISBN 9781605581699. Número de identificación del sujeto  53038874.
3. Briest, Patrick; Krysta, Piotr (22 de enero de 2006). "Precios de oferta ilimitados y unidireccionales en instancias dispersas". Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos - SODA '06 . Miami, Florida: Society for Industrial and Applied Mathematics. págs. 1093–1102. doi :10.1145/1109557.1109678. ISBN . 978-0-89871-605-4. Número de identificación del sujeto  4191038.
4. Briest, Patrick (2008). "Presupuestos uniformes y el problema de los precios sin envidia". En Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 5125. Springer Berlin Heidelberg. págs. 808–819. CiteSeerX 10.1.1.205.433 . doi :10.1007/978-3-540-70575-8_66. ISBN: 978-3-540-70575-8_66 .  9783540705758.
5. 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. 
6. Im, Sungjin; Lu, Pinyan; Wang, Yajun (2010). "Fijación de precios sin envidia con restricciones generales de la oferta". En Saberi, Amin (ed.). Internet and Network Economics . Apuntes de clase en 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.
7. Chen, Ning; Deng, Xiaotie (1 de febrero de 2014). "Precios sin envidia en mercados de múltiples artículos". ACM Transactions on Algorithms . 10 (2): 7:1–7:15. CiteSeerX 10.1.1.297.784 . doi :10.1145/2567923. ISSN  1549-6325. S2CID  15309106. 
8. Cheung, M.; Swamy, C. (1 de octubre de 2008). "Algoritmos de aproximación para problemas de maximización de beneficios sin envidia y con oferta limitada". 49.° Simposio anual IEEE sobre fundamentos de la informática de 2008. págs. 35–44. doi :10.1109/FOCS.2008.15. ISBN 978-0-7695-3436-7. Número de identificación del sujeto  1318192.
9. Devanur, Nikhil R.; Hartline, Jason D.; Yan, Qiqi (1 de marzo de 2015). "Libertad de envidia y diseño de mecanismos sin prior". Journal of Economic Theory . 156 : 103–143. arXiv : 1212.3741 . doi :10.1016/j.jet.2014.08.001. ISSN  0022-0531. S2CID  17990320.
10. 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 oferta ilimitada". En Gupta, Anupam; Jansen, Klaus; Rolim, José; Servedio, Rocco (eds.). Aproximación, aleatorización y optimización combinatoria. Algoritmos y técnicas . Apuntes de clase en 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.
11. Chalermsook, P.; Laekhanukit, B.; Nanongkai, D. (1 de octubre de 2013). "Conjunto independiente, emparejamiento inducido y fijación de precios: conexiones y durezas de aproximación ajustada (tiempo subexponencial)". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . págs. 370–379. arXiv : 1308.2617 . doi :10.1109/FOCS.2013.47. ISBN 978-0-7695-5135-7.S2CID 972321  .
12. Chalermsook, Parinya; Laekhanukit, Bundit; Nanongkai, Danupon (6 de enero de 2013). "Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More". Actas del Simposio Anual ACM-SIAM de 2013 sobre Algoritmos Discretos. Sociedad de Matemáticas Industriales y Aplicadas. 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 .
13. Demaine, Erik D.; Feige, Uriel; Hajiaghayi, MohammadTaghi; Salavatipour, Mohammad R. (1 de enero de 2008). "La combinación puede ser difícil: aproximabilidad del problema de cobertura única". Revista SIAM de informática . 38 (4): 1464–1483. doi :10.1137/060656048. ISSN  0097-5397. S2CID  12248889.
14. Anshelevich, Elliot; Kar, Koushik; Sekar, Shreyas (9 de agosto de 2017). "Fijación de precios sin envidia en grandes mercados: aproximación de ingresos y bienestar". ACM Transactions on Economics and Computation . 5 (3): 16:1–16:42. doi :10.1145/3105786. ISSN  2167-8375. S2CID  7008965.
15. Bilò, Vittorio; Flammini, Michele; Monaco, Gianpiero (1 de febrero de 2017). "Aproximación del problema de maximización de ingresos con demandas agudas". Ciencias Informáticas Teóricas . 662 : 9–30. arXiv : 1312.3892 . doi : 10.1016/j.tcs.2016.12.002 . ISSN  0304-3975.
16. Colini-Baldeschi, Riccardo; Leonardi, Stefano; Sankowski, Piotr; Zhang, Qiang (2014). "Subastas de precio fijo sin envidia que maximizan los ingresos con presupuestos". En Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). Economía de Internet y de la Web . Apuntes de clase en Ciencias de la Computación. Vol. 8877. Cham: Springer International Publishing. págs. 233–246. doi :10.1007/978-3-319-13129-0_18. hdl : 11573/754515 . ISBN . 978-3-319-13129-0.
17. Feldman, Michal ; Fiat, Amos; Leonardi, Stefano; Sankowski, Piotr (2012). "Subastas multiunidades sin envidia que maximizan los ingresos con presupuestos". Actas de la 13.ª Conferencia de la ACM sobre comercio electrónico . EC '12. Nueva York, NY, EE. UU.: ACM. págs. 532–549. doi :10.1145/2229012.2229052. ISBN 9781450314152.S2CID15639601  .​
18. Monaco, Gianpiero; Sankowski, Piotr; Zhang, Qiang (25 de julio de 2015). "Maximización de ingresos: fijación de precios sin envidia 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.
19. Chen, Ning; Rudra, Atri (1 de septiembre de 2008). "Equilibrio walrasiano: dureza, aproximaciones e instancias manejables". Algorithmica . 52 (1): 44–64. doi :10.1007/s00453-007-9103-9. ISSN  1432-0541. S2CID  18839423.
20. Alon, Noga; Mansour, 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 de la ACM sobre comercio electrónico . EC '13. Filadelfia, Pensilvania, EE. UU.: Association for Computing Machinery. págs. 9–24. doi :10.1145/2492002.2482545. ISBN . 978-1-4503-1962-1.
21. Amanatidis, Georgios; Fulla, Peter; Markakis, Evangelos; Sornat, Krzysztof (17 de diciembre de 2019). "Precios de aversión a la inequidad en redes sociales: algoritmos de aproximación y resultados de dureza". arXiv : 1606.06664 [cs.GT].
22. 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.
23. "Precios por aversión a la inequidad en mercados multi-unidades". iris.gssi.it . Consultado el 5 de abril de 2021 .
24. Elbassioni, Khaled; Fouz, Mahmoud; Swamy, Chaitanya (2010). "Algoritmos de aproximación para problemas de maximización de beneficios no unidireccionales con oferta limitada". En Saberi, Amin (ed.). Internet and Network Economics . Apuntes de clase en 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.S2CID14124011  .​
25. Bérczi, Kristóf; Codazzi, Laura; Golak, Julián; Grigoriev, Alejandro (2023). "Libre de envidia dinámica en los precios". arXiv : 2301.01529 [cs.GT].