Mercado de pescadores

El mercado de Fisher es un modelo económico atribuido a Irving Fisher . Tiene los siguientes componentes: ^[1]

• Un conjunto de productos divisibles con suministros predeterminados (normalmente normalizados de modo que el suministro de cada bien sea 1). ${\displaystyle m}$
• Un conjunto de compradores. ${\displaystyle n}$
• Para cada comprador hay un presupuesto monetario predeterminado . ${\displaystyle i=1,\dots ,n}$ ${\displaystyle B_{i}}$

Cada producto tiene un precio ; los precios se determinan mediante los métodos que se describen a continuación. El precio de un conjunto de productos es la suma de los precios de los productos que lo componen. Un conjunto se representa mediante un vector , donde es la cantidad de producto . Por lo tanto, el precio de un conjunto es . ${\displaystyle j}$ ${\displaystyle p_{j}}$ ${\displaystyle x=x_{1},\dots ,x_{m}}$ ${\displaystyle x_{j}}$ ${\displaystyle j}$ ${\displaystyle x}$ ${\displaystyle p(x)=\sum _{j=1}^{m}p_{j}\cdot x_{j}}$

Un paquete es asequible para un comprador si el precio de ese paquete se ajusta como máximo al presupuesto del comprador. Es decir, un paquete es asequible para el comprador si ... ${\displaystyle x}$ ${\displaystyle i}$ ${\displaystyle p(x)\leq B_{i}}$

Cada comprador tiene una relación de preferencia sobre los paquetes, que se puede representar mediante una función de utilidad. La función de utilidad del comprador se denota por . El conjunto de demanda de un comprador es el conjunto de paquetes asequibles que maximizan la utilidad del comprador entre todos los paquetes asequibles, es decir: ${\displaystyle i}$ ${\displaystyle u_{i}}$

${\displaystyle {\text{Demand}}_{i}(p):=\arg \max _{p(x)\leq B_{i}}u_{i}(x)}$.

Un equilibrio competitivo (EC) es un vector de precios en el que es posible asignar a cada agente un conjunto de productos de su demanda, de modo que la asignación total sea exactamente igual a la oferta de productos. Los precios correspondientes se denominan precios de equilibrio del mercado . El principal desafío en el análisis de los mercados de Fisher es encontrar un EC. ^{[2] : 103–105} ${\displaystyle p_{1},\dots ,p_{m}}$

Modelos relacionados

• En el modelo de mercado de Fisher, el presupuesto no tiene valor intrínseco: sólo es útil para comprar productos. Esto contrasta con un mercado walrasiano con agentes con utilidades cuasilineales , en el que el dinero es en sí mismo un producto y tiene valor propio.
• El mercado de Arrow-Debreu es una generalización del modelo de Fisher, en el que cada agente puede ser a la vez comprador y vendedor, es decir, cada agente viene con un paquete de productos, en lugar de solo con dinero.
• Los mercados de Eisenberg-Gale son otra generalización del mercado lineal de Fisher. ^[3]

Mercado de pescado con artículos divisibles

Existencia de equilibrio

Cuando todos los artículos del mercado son divisibles, siempre existe un EC. Esto se puede demostrar utilizando el famoso lema de Sperner . ^{[4] : 67}

Supongamos que las cantidades están normalizadas de modo que hay 1 unidad por producto, y los presupuestos están normalizados de modo que su suma es 1. Supongamos también que todos los productos son buenos, es decir, un agente siempre prefiere estrictamente tener más de cada producto, si puede permitírselo.

Consideremos el símplex estándar con m vértices. Cada punto de este símplex corresponde a un vector de precios, donde la suma de todos los precios es 1; por lo tanto, el precio de todos los bienes en conjunto es 1.

En cada vector de precios p , podemos encontrar un conjunto demandado de cada agente, luego calcular la suma de todos los conjuntos demandados y luego encontrar el precio total de esta demanda agregada. Como el precio de cada conjunto demandado es como máximo el presupuesto del agente, y la suma de los presupuestos es como máximo 1, el precio de la demanda agregada es como máximo 1. Por lo tanto, para cada p , hay al menos un producto para el cual la demanda total es como máximo 1. Llamemos a ese producto un "producto caro" en p.

Triangule el símplex de m vértices y etiquete cada vértice de triangulación p con un índice de un producto caro arbitrario en p . En cada cara del símplex, algunos productos cuestan 0. Como todos los productos son buenos, la demanda de cada agente por un producto que cuesta 0 es siempre 1; por lo tanto, un producto que cuesta 0 nunca puede considerarse caro. Por lo tanto, el etiquetado anterior satisface la condición de contorno de Sperner.

Por el lema de Sperner, existe un baby-símplex cuyos vértices están etiquetados con m etiquetas diferentes. Como la función de demanda es continua, al realizar triangulaciones cada vez más finas encontramos un único vector de precios p ^∗ , en el que todos los productos son caros, es decir, la demanda agregada para cada producto es como máximo 1.

Pero, como la suma de todos los presupuestos es 1, la demanda agregada de cada producto en p ^∗ debe ser exactamente 1. Por lo tanto, p ^∗ es un vector de precios que equilibran el mercado.

Cálculo del equilibrio

Si bien el lema de Sperner se puede utilizar para hallar un CE, ^[4] es muy ineficiente desde el punto de vista computacional. Existen métodos más eficientes (véase también cálculo del equilibrio del mercado ).

Devanur, Papadimitriou, Saberi y Vazirani ^[5] dieron un algoritmo de tiempo polinomial para calcular exactamente un equilibrio para los mercados de Fisher con funciones de utilidad lineales . Su algoritmo utiliza el paradigma primal-dual en el entorno mejorado de condiciones KKT y programas convexos. Su algoritmo es débilmente polinomial: resuelve problemas de flujo máximo y, por lo tanto, se ejecuta en el tiempo , donde u _max y B _max son la utilidad máxima y el presupuesto, respectivamente. ${\displaystyle O((n+m)^{5}\log(u_{\max })+(n+m)^{4}\log {B_{\max }})}$ ${\displaystyle O((n+m)^{8}\log(u_{\max })+(n+m)^{7}\log {B_{\max }})}$

Orlin ^[6] presentó un algoritmo mejorado para un modelo de mercado de Fisher con utilidades lineales, que se ejecuta en tiempo . Luego mejoró su algoritmo para que se ejecutara en tiempo fuertemente polinomial : . ${\displaystyle O((n+m)^{4}\log(u_{\max })+(n+m)^{3}B_{\max })}$ ${\displaystyle O((m+n)^{4}\log(m+n))}$

Chen y Teng ^[7] demostraron que, cuando las utilidades de los agentes pueden ser funciones SPLC (cóncavas lineales separables por partes) arbitrarias, encontrar una CE es difícil en PPAD .

Maná malo y mixto

Bogomolnaia y Moulin y Sandomirskiy y Yanovskaia estudiaron la existencia y las propiedades de la CE en un mercado de Fisher con bienes malos (artículos con utilidades negativas) ^[8] y con una mezcla de bienes y bienes malos. ^[9] A diferencia del escenario con bienes, cuando los recursos son malos la CE no resuelve ningún problema de optimización convexa incluso con utilidades lineales. Las asignaciones de CE corresponden a mínimos locales, máximos locales y puntos de silla del producto de utilidades en la frontera de Pareto del conjunto de utilidades factibles. La regla de la CE se vuelve multivaluada. Este trabajo ha dado lugar a varios trabajos sobre algoritmos para encontrar la CE en dichos mercados:

• Branzei y Sandomirskiy ^[10] dieron un algoritmo para encontrar todos los CE en un mercado de Fisher con males y utilidades lineales. Su algoritmo se ejecuta en tiempo fuertemente polinomial si n o m son fijos. Su enfoque combina tres ideas: todos los gráficos de consumo de asignaciones de PO se pueden enumerar en tiempo polinomial; para un gráfico de consumo dado, se puede construir un candidato a CE mediante una fórmula explícita; y se puede verificar que una asignación dada sea un CE utilizando un cálculo de flujo máximo .
• Garg y McGlaughlin ^[11] presentaron un algoritmo para calcular todos los CE en un mercado de Fisher con utilidades mixtas de maná y lineales. Su algoritmo se ejecuta en tiempo polinomial si n o m son fijos.
• Chaudhury, Garg, McGlaughlin y Mehta ^[12] dieron un algoritmo para calcular un único CE en un mercado de Fisher con utilidades mixtas de maná y SPLC. Su algoritmo es similar al simplex y se basa en el esquema de Lemke . Si bien su tiempo de ejecución en el peor de los casos no es polinomial (el problema es PPAD-hard incluso con bienes ^[13] ), se ejecuta rápidamente en instancias aleatorias. También demuestra que el problema está en PPAD, las soluciones tienen valores racionales y el número de soluciones es impar. Su algoritmo se ejecuta en tiempo polinomial en el caso especial en el que todas las utilidades son negativas.

Si tanto n como m son variables, el problema se vuelve computacionalmente difícil:

• Chaudhury, Garg, McGlaughlin y Mehta ^{[14] : Thm.3} muestran que, en un mercado de Fisher con males y utilidades lineales, es NP-difícil decidir si existe un CE. La misma dificultad se cumple incluso para encontrar un (11/12+δ)-CE para cualquier δ>0, e incluso con ingresos iguales. También prueban una condición suficiente, basada en la conectividad de grafos, para la existencia de un CE. Con esta condición, siempre existe un CE, pero encontrarlo es PPAD-difícil. ^{[14] : Thm.5}

Mercados de pescado con artículos indivisibles

Cuando los artículos en el mercado son indivisibles, no se garantiza la existencia de un EC. Decidir si existe un EC es un problema computacionalmente difícil.

Deng et al ^[15] estudiaron un mercado en el que cada agente llega con una dotación inicial (en lugar de un ingreso inicial) y todas las valoraciones son aditivas. Demostraron que decidir si existe CE es NP-hard incluso con 3 agentes. Presentaron un algoritmo de aproximación que relaja las condiciones de CE de dos maneras: (1) el paquete asignado a cada agente se valora al menos 1-épsilon del óptimo dados los precios, y (2) la demanda es al menos 1-épsilon multiplicada por la oferta.

Bouveret y Lemaitre ^[16] estudiaron la CE a partir de ingresos iguales (CEEI) como regla para la asignación justa de ítems. La relacionaron con otros cuatro criterios de equidad asumiendo que todos los agentes tienen funciones de valoración aditivas. Se preguntaron cuál es la complejidad computacional de decidir si existe CEEI.

Esta pregunta fue respondida poco después por Aziz ^[17], quien demostró que el problema es débilmente NP-hard cuando hay dos agentes y m elementos, y fuertemente NP-hard cuando hay n agentes y 3 n elementos. También presentó una condición más fuerte llamada CEEI-FRAC que es, curiosamente, más fácil de verificar: se puede verificar en tiempo polinomial. Miltersen, Hosseini y Branzei ^[18] demostraron que incluso verificar si una asignación dada es CEEI es co-NP-hard. Estudiaron CEEI también para agentes unipersonales. En este caso, verificar si una asignación dada es CEEI es polinomial, pero verificar si existe CEEI es co-NP-completo.

Heinen et al ^{. [19]} extendieron el trabajo de Bouveret y Lemaitre desde funciones de utilidad aditivas a k-aditivas, en las que cada agente informa un valor para paquetes que contienen como máximo k artículos, y los valores de paquetes más grandes se determinan sumando y restando los valores de los paquetes básicos.

Budish ^[20] estudió el contexto más general en el que los agentes pueden tener relaciones de preferencia arbitrarias sobre los paquetes. Inventó el mecanismo de Equilibrio Competitivo Aproximado a Partir de Ingresos Iguales , que relaja las condiciones del CEEI de dos maneras: (1) los ingresos de los agentes no son exactamente iguales y (2) una pequeña cantidad de ítems pueden permanecer sin asignar. Demostró que siempre existe un CEEI aproximado (aunque Othman et al ^[21] demostró recientemente que el cálculo del CEEI aproximado es PPAD completo ).

Barman y Krishnamurthy ^[22] estudian los mercados de Fisher en los que todos los agentes tienen utilidades aditivas. Demuestran que un CE fraccionario (en el que algunos bienes se dividen) siempre se puede redondear a un CE integral (en el que los bienes permanecen indivisibles), modificando los presupuestos de los agentes. El cambio en cada presupuesto puede ser tan alto como el precio más alto de un bien en el CE fraccionario.

Babaioff, Nisan y Talgam-Cohen ^[23] estudiaron si la CE existe cuando los ingresos son genéricos , es decir, no satisfacen un conjunto finito de igualdades. En otras palabras: si existe una CE para casi todos los vectores de ingresos. Probaron su existencia para tres bienes, y para cuatro bienes y dos agentes. Probaron su inexistencia para cinco bienes y dos agentes. Más tarde, demostraron que con cuatro bienes y tres agentes, la CE puede no existir cuando las valoraciones no son aditivas, pero siempre existe cuando las valoraciones son aditivas. ^[24]

Véase también

• Equilibrio general

Referencias

1. Yishay Mansour (2011). "Conferencia 10: Equilibrio del mercado" (PDF) . Temas avanzados en aprendizaje automático y teoría de juegos algorítmicos . Consultado el 15 de marzo de 2016 .
2. Vazirani, Vijay V. ; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). "Capítulo 5: Algoritmos combinatorios para equilibrios de mercado / Vijay V. Vazirani". Teoría de juegos algorítmicos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
3. Jain, Kamal; Vazirani, Vijay V. (2010). "Mercados de Eisenberg-Gale: algoritmos y propiedades de teoría de juegos". Juegos y comportamiento económico . 70 : 84–106. doi :10.1016/j.geb.2008.11.011.
4. Scarf, Herbert (1967). "El núcleo de un juego de N personas". Econometrica . 35 (1): 50–69. doi :10.2307/1909383. JSTOR  1909383.
5. Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V. (5 de noviembre de 2008). "Equilibrio del mercado mediante un algoritmo dual primario para un programa convexo". Revista de la ACM . 55 (5): 22:1–22:18. doi :10.1145/1411509.1411512. ISSN  0004-5411. S2CID  11836728.
6. Orlin, James B. (5 de junio de 2010). "Algoritmos mejorados para calcular los precios de equilibrio del mercado de pescadores". Actas del cuadragésimo segundo simposio de la ACM sobre teoría de la computación . STOC '10. Cambridge, Massachusetts, EE. UU.: Association for Computing Machinery. págs. 291–300. doi :10.1145/1806689.1806731. hdl : 1721.1/68009 . ISBN. 978-1-4503-0050-6.S2CID8235905  .​
7. Chen, Xi; Teng, Shang-Hua (2009). Dong, Yingfei; Du, Ding-Zhu; Ibarra, Oscar (eds.). "Gastar no es más fácil que comerciar: sobre la equivalencia computacional de los equilibrios de Fisher y Arrow-Debreu". Algorithms and Computation . Apuntes de clase en informática. 5878 . Berlín, Heidelberg: Springer: 647–656. arXiv : 0907.4130 . doi :10.1007/978-3-642-10631-6_66. ISBN 978-3-642-10631-6.S2CID 7817966  .
8. Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor; Yanovskaia, Elena (1 de marzo de 2019). "División de males bajo utilidades aditivas". Elección social y bienestar . 52 (3): 395–417. doi : 10.1007/s00355-018-1157-x . ISSN  1432-217X.
9. Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor; Yanovskaya, Elena (2017). "División competitiva de un maná mixto". Econometrica . 85 (6): 1847–1871. arXiv : 1702.00616 . doi :10.3982/ECTA14564. ISSN  1468-0262. S2CID  17081755.
10. Brânzei, Simina; Sandomirskiy, Fedor (3 de julio de 2019). "Algoritmos para la división competitiva de tareas". arXiv : 1907.01766 [cs.GT].
11. Garg, Jugal; McGlaughlin, Peter (5 de mayo de 2020). "Computación de equilibrios competitivos con maná mixto". Actas de la 19.ª Conferencia internacional sobre agentes autónomos y sistemas multiagente . AAMAS '20. Auckland, Nueva Zelanda: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente: 420–428. ISBN 978-1-4503-7518-4.
12. Chaudhury, Bhaskar Ray; Garg, yugal; McGlaughlin, Peter; Mehta, Ruta (1 de enero de 2021), "Asignación competitiva de un maná mixto", Actas del Simposio ACM-SIAM sobre algoritmos discretos (SODA) de 2021 , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. arXiv : 2008.02753 , doi : 10.1137/1.9781611976465.85 , ISBN 978-1-61197-646-5
13. Chen, Xi; Teng, Shang-Hua (2009). Dong, Yingfei; Du, Ding-Zhu; Ibarra, Oscar (eds.). "Gastar no es más fácil que comerciar: sobre la equivalencia computacional de los equilibrios de Fisher y Arrow-Debreu". Algorithms and Computation . Apuntes de clase en informática. 5878 . Berlín, Heidelberg: Springer: 647–656. arXiv : 0907.4130 . doi :10.1007/978-3-642-10631-6_66. ISBN 978-3-642-10631-6.S2CID 7817966  .
14. Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (1 de agosto de 2020). "Dividir los males es más difícil que dividir los bienes: sobre la complejidad de la división justa y eficiente de las tareas". arXiv : 2008.00285 [cs.GT].
15. Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel (1 de septiembre de 2003). "Sobre la complejidad de los equilibrios de precios". Journal of Computer and System Sciences . 67 (2): 311–324. doi : 10.1016/S0022-0000(03)00011-4 . ISSN  0022-0000.
16. Lemaître, Michel; Bouveret, Sylvain (1 de marzo de 2016). "Caracterización de los conflictos en la división justa de bienes indivisibles utilizando una escala de criterios". Agentes autónomos y sistemas multiagente . 30 (2): 259–290. doi :10.1007/s10458-015-9287-3. ISSN  1573-7454. S2CID  16041218.
17. Aziz, Haris (1 de noviembre de 2015). "Equilibrio competitivo con ingresos iguales para la asignación de objetos indivisibles". Operations Research Letters . 43 (6): 622–624. arXiv : 1501.06627 . Bibcode :2015arXiv150106627A. doi :10.1016/j.orl.2015.10.001. ISSN  0167-6377. S2CID  11495811.
18. Miltersen, Peter Bro; Hosseini, Hadi; Brânzei, Simina (28 de septiembre de 2015). "Caracterización y cálculo de equilibrios para bienes indivisibles". Teoría de juegos algorítmicos . Apuntes de clase en informática. Vol. 9347. Springer, Berlín, Heidelberg. págs. 244–255. arXiv : 1503.06855 . doi :10.1007/978-3-662-48433-3_19. ISBN . 9783662484326.S2CID656603  .​
19. Rothe, Jörg; Nguyen, Nhan-Tam; Heinen, Tobias (27 de septiembre de 2015). "Justicia y utilitarismo ponderado por rango en la asignación de recursos". Teoría de la decisión algorítmica . Apuntes de clase en informática. Vol. 9346. Springer, Cham. págs. 521–536. doi :10.1007/978-3-319-23114-3_31. ISBN 9783319231136.
20. Budish, Eric (2011). "El problema de asignación combinatoria: equilibrio competitivo aproximado a partir de ingresos iguales". Revista de economía política . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . doi :10.1086/664613. S2CID  154703357. 
21. Othman, Abraham; Papadimitriou, Christos; Rubinstein, Aviad (1 de agosto de 2016). "La complejidad de la equidad a través del equilibrio". ACM Transactions on Economics and Computation . 4 (4): 20:1–20:19. CiteSeerX 10.1.1.747.956 . doi :10.1145/2956583. ISSN  2167-8375. S2CID  2780775. 
22. Barman, Siddharth; Krishnamurthy, Sanath Kumar (21 de noviembre de 2018). "Sobre la proximidad de los mercados con equilibrios integrales". arXiv : 1811.08673 [cs.GT].
23. Talgam-Cohen, Inbal; Nisan, Noam; Babaioff, Moshe (23 de marzo de 2017). "Equilibrio competitivo con bienes indivisibles y presupuestos genéricos". arXiv : 1703.08150 [cs.GT].
24. Segal-Halevi, Erel (2020-02-20). "Equilibrio competitivo para casi todos los ingresos: existencia y equidad". Agentes autónomos y sistemas multiagente . 34 (1): 26. arXiv : 1705.04212 . doi :10.1007/s10458-020-09444-z. ISSN  1573-7454. S2CID  210911501.