El cálculo del equilibrio del mercado (también llamado cálculo del equilibrio competitivo o cálculo de los precios de compensación ) es un problema computacional en la intersección de la economía y la informática . La entrada a este problema es un mercado , que consta de un conjunto de recursos y un conjunto de agentes . Hay varios tipos de mercados, como el mercado Fisher y el mercado Arrow-Debreu , con recursos divisibles o indivisibles. La producción requerida es un equilibrio competitivo , que consta de un vector de precios(un precio por cada recurso) y una asignación (un paquete de recursos para cada agente), de modo que cada agente obtenga el mejor paquete posible (para él) dado el presupuesto, y el mercado se liquida (se asignan todos los recursos).
El cálculo del equilibrio del mercado es interesante debido al hecho de que un equilibrio competitivo siempre es Pareto eficiente . El caso especial de un mercado Fisher, en el que todos los compradores tienen ingresos iguales, es particularmente interesante, ya que en este escenario un equilibrio competitivo también está libre de envidia . Por lo tanto, el cálculo del equilibrio del mercado es una forma de encontrar una asignación que sea justa y eficiente.
Definiciones
La entrada para el cálculo del equilibrio del mercado consta de los siguientes ingredientes: [1] : capítulo 5
- Un conjunto de recursos con suministros preespecificados. Los recursos pueden ser divisibles (en cuyo caso, su suministro es wlog normalizado a 1) o indivisibles .
- Un paquete está representado por un vector, dónde es la cantidad de recurso . Cuando los recursos son indivisibles, todos los x j son números enteros; cuando los recursos son divisibles, x j pueden ser números reales arbitrariamente (normalmente normalizados a [0,1]).
- Un conjunto de agentes . Para cada agente, existe una relación de preferencia sobre los paquetes, que puede representarse mediante una función de utilidad. La función de utilidad del agente se denota por .
- Una dotación inicial para cada agente.
- En un mercado de Fisher , la dotación es un presupuestode "dinero fiduciario" - un dinero que no tiene valor fuera del mercado y, por tanto, no entra en la función de utilidad. Dado que los agentes vienen solo con dinero, a menudo se les llama compradores .
- En un mercado de Arrow-Debreu , la dotación es un paquete arbitrario; en este modelo, los agentes pueden ser compradores y vendedores.
La salida requerida debe contener los siguientes ingredientes:
- Un vector de precios ; un precio por cada recurso. El precio de un paquete es la suma de los precios de los recursos en el, por lo que el precio de un paquete es .
- Una asignación , un paquetepara cada agente i .
La salida debe satisfacer los siguientes requisitos:
- El haz debe ser asequible para i , es decir, su precio debe ser como máximo el precio de la dotación del agente i .
- En un mercado de Fisher, esto significa que .
- En un mercado Arrow-Debreu, esto significa que .
- El haz debe estar en el conjunto de demanda de i :, definido como el conjunto de paquetes que maximizan la utilidad del agente entre todos los paquetes asequibles (independientemente de la oferta), por ejemplo, en un mercado de Fisher:
- El mercado se liquida , es decir, se asignan todos los recursos. Los precios correspondientes se denominan precios de compensación del mercado .
Un precio y la asignación de satisfacer estos requisitos se llaman un equilibrio competitivo (CE) o un equilibrio en el mercado ; los precios también se denominan precios de equilibrio o precios de compensación .
Tipos de funciones de utilidad
El cálculo del equilibrio del mercado se ha estudiado bajo varios supuestos con respecto a las funciones de utilidad de los agentes.
- Concavidad : el supuesto más general (hecho por Fisher y Arrow & Debreu) es que las utilidades de los agentes son funciones cóncavas , es decir, muestran rendimientos decrecientes .
- Homogeneidad : En algunos casos, se asume que las utilidades son funciones homogéneas . Esto incluye, en particular, las empresas de servicios públicos con elasticidad de sustitución constante .
- Separabilidad : una función de utilidad se denomina separable si la utilidad de un paquete es la suma de las utilidades de los recursos individuales en el paquete, es decir,.
- La linealidad por partes es un caso especial de separabilidad, en el que la función de utilidad para cada recurso individual,, es una función lineal por partes de x j.
- La linealidad es un caso aún más especial, en el que la función de utilidad para cada recurso individual es una función lineal . Es decir,, dónde son constantes.
Las utilidades que son lineales por partes y cóncavas a menudo se denominan PLC; si también son separables, se denominan SPLC.
Resultados principales
Algoritmos aproximados
Scarf [2] fue el primero en mostrar la existencia de un EC utilizando el lema de Sperner (ver Fisher market ). También dio un algoritmo para calcular un CE aproximado.
Merrill [3] proporcionó un algoritmo extendido para CE aproximado.
Kakade, Kearns y Ortiz [4] proporcionaron algoritmos para CE aproximada en un mercado Arrow-Debreu generalizado en el que los agentes están ubicados en un gráfico y el comercio puede ocurrir solo entre agentes vecinos. Consideraron utilidades no lineales.
Resultados de dureza
En algunos casos, calcular un CE aproximado es difícil de PPAD :
- Devanur y Kannan [5] demostraron la dureza del PPAD en un mercado de Arrow-Debreu con las utilidades de Leontief , un caso especial de las utilidades de PLC.
- Chen, Dai, Du y Teng [6] demostraron dureza PPAD en un mercado de Arrow-Debreu con utilidades SPLC. Su prueba muestra que este problema de equilibrio de mercado no tiene un FPTAS a menos que PPAD esté en P.
- Chen y Teng [7] demostraron dureza PPAD en un mercado de Fisher con utilidades SPLC.
- Chaudhury, Garg, McGlaughlin y Mehta [8] demostraron la dureza del PPAD en un mercado de Fisher con malas utilidades y utilidades lineales, incluso bajo cierta condición que garantiza la existencia de CE.
Algoritmos exactos
Devanur, Papadimitriou, Saberi y Vazirani [9] dieron un algoritmo de tiempo polinomial para calcular exactamente un equilibrio para los mercados de Fisher con funciones de utilidad lineal . Su algoritmo utiliza el paradigma primal-dual en la configuración mejorada de las condiciones KKT y los programas convexos. Su algoritmo es débilmente polinomial: resuelve problemas de flujo máximo y, por lo tanto, funciona a tiempo, donde u max y B max son la utilidad y el presupuesto máximos, respectivamente.
Orlin [10] proporcionó un algoritmo mejorado para un modelo de mercado de Fisher con utilidades lineales, que se ejecuta en el tiempo. Luego mejoró su algoritmo para que se ejecute en un tiempo fuertemente polinomial :.
Devanur y Kannan [5] proporcionaron algoritmos para los mercados Arrow-Debreu con funciones de utilidad cóncavas , donde todos los recursos son bienes (las utilidades son positivas):
- Cuando los servicios públicos son SPLC y, o bien n o m es una constante, su algoritmo es polinomio en el otro parámetro. La técnica consiste en descomponer el espacio de precios posibles en celdas utilizando un número constante de hiperplanos, de modo que en cada celda, se conozca la utilidad marginal del umbral de cada comprador (cuando tanto n como m son variables, se dejó abierto si existe un algoritmo de tiempo múltiple). .
- Cuando las utilidades son PLC (no necesariamente separables) y m es constante, su algoritmo es polinomio en n . Cuando ambos m y n son variables, la búsqueda de una CE es PPAD-duro incluso para servicios públicos de Leontief , que son un caso especial de los servicios públicos de PLC (cuando n es constante sino que m es variable, se deja abierto si existe un algoritmo polytime).
Codenotti, McCune, Penumatcha y Varadarajan [11] proporcionaron un algoritmo para las marcas Arrow-Debreu con utilidades CES donde la elasticidad de sustitución es al menos 1/2.
Malos y maná mezclado
Bogomolnaia y Moulin y Sandomirskiy y Yanovskaia estudiaron la existencia y propiedades de la CE en un mercado de Fisher con males (artículos con utilidades negativas) [12] y con una mezcla de bienes y males. [13] A diferencia del escenario con mercancías, cuando los recursos son malos la CE no resuelve ningún problema de optimización convexa ni siquiera con utilidades lineales. Las asignaciones de CE corresponden a mínimos locales, máximos locales y puntos silla del producto de los servicios públicos en la frontera de Pareto del conjunto de servicios factibles. La regla CE se vuelve multivalor. Este trabajo ha dado lugar a varios trabajos sobre algoritmos para encontrar CE en dichos mercados:
- Branzei y Sandomirskiy [14] proporcionaron un algoritmo para encontrar toda la CE en un mercado de Fisher con malos y utilidades lineales. Sus carreras algoritmo en tiempo fuertemente-polinomio si cualquiera de n o m es fijo. Su enfoque combina tres ideas: todos los gráficos de consumo de las asignaciones de PO se pueden enumerar en tiempo polinomial; para un gráfico de consumo dado, se puede construir un candidato de 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 [15] proporcionaron un algoritmo para calcular toda la CE en un mercado de Fisher con maná mixto y utilidades lineales. Sus carreras algoritmo en tiempo polinómico si cualquiera de n o m es fijo.
- Chaudhury, Garg, McGlaughlin y Mehta [16] proporcionaron un algoritmo para calcular un único CE en un mercado de Fisher con servicios públicos mixtos 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 difícil de PPAD incluso con bienes [7] ), se ejecuta rápidamente en instancias aleatorias. También demuestra que el problema está en PPAD, las soluciones tienen un valor racional 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 [8] : Thm.3 muestran que, en un mercado Fisher con malas y utilidades lineales, es NP-difícil decidir si existe una CE. La misma dureza es válida incluso para encontrar un (11/12 + δ) -CE para cualquier δ> 0, e incluso con ingresos iguales. También demuestran una condición suficiente, basada en la conectividad gráfica, para la existencia de una CE. Con esta condición, siempre existe una CE, pero encontrarla es difícil de detectar. [8] : Thm.5
Técnicas principales
Bang-for-buck
Cuando las utilidades son lineales, el valor por dólar del agente i (también llamado BPB o utilidad por moneda ) se define como la utilidad de i dividida por el precio pagado. El BPB de un solo recurso es; el BPB total es.
Una observación clave para encontrar un EC en un mercado de Fisher con servicios lineales es que, en cualquier EC y para cualquier agente i : [1]
- El BPB total es débilmente mayor que el BPB de cualquier recurso individual, .
- El agente i consume solo recursos con el máximo BPB posible, es decir,.
Suponga que cada producto tiene un comprador potencial - un comprador con . Entonces, las desigualdades anteriores implican que, es decir, todos los precios son positivos.
Descomposición celular
La descomposición celular [5] es un proceso de partición del espacio de posibles precios.en pequeñas "células", ya sea por hiperplanos o, más generalmente, por superficies polinomiales. Una celda se define especificando en qué lado de cada una de estas superficies se encuentra (con superficies polinomiales, las celdas también se conocen como conjuntos semialgebraicos ). Para cada celda, encontramos un vector de precios de compensación de mercado (es decir, un precio en esa celda para el cual existe una asignación de compensación de mercado), o verificamos que la celda no contiene un vector de precios de compensación de mercado. El desafío es encontrar una descomposición con las siguientes propiedades:
- El número total de celdas es polinomial en el tamaño de la entrada. Esto usa el hecho de que cualquier colección de k hiperplanos en divide el espacio en células. [5] : Thm.2 Este es un polinomio si m es fijo. Además, cualquier colección de k superficies polinomiales de grado como máximo d divide el espacio enceldas no vacías, y se pueden enumerar en el tiempo lineal en el tamaño de salida. [17]
- Encontrar un vector de precios de compensación de mercado en cada celda se puede hacer en tiempo polinomial, por ejemplo, usando programación lineal.
Optimización convexa: utilidades homogéneas
Si las utilidades de todos los agentes son funciones homogéneas , entonces las condiciones de equilibrio en el modelo de Fisher se pueden escribir como soluciones a un programa de optimización convexo llamado programa convexo de Eisenberg-Gale . [18] Este programa encuentra una asignación que maximiza la media geométrica ponderada de los servicios públicos de los compradores, donde los pesos están determinados por los presupuestos. De manera equivalente, maximiza la media aritmética ponderada de los logaritmos de las utilidades:
- Maximizar
- Sujeto a:
- Cantidades no negativas : para todos los compradores y producto :
- Suministros suficientes : para cada producto :
(ya que los suministros se normalizan a 1).
Este problema de optimización se puede resolver utilizando las condiciones de Karush-Kuhn-Tucker (KKT). Estas condiciones introducen multiplicadores lagrangianos que pueden interpretarse como los precios ,. En cada asignación que maximiza el programa Eisenberg-Gale, cada comprador recibe un paquete solicitado. Es decir, una solución al programa Eisenberg-Gale representa un equilibrio de mercado. [1] : 141–142
Algoritmo de Vazirani: utilidades lineales, tiempo polinomial débil
Un caso especial de servicios públicos homogéneos es cuando todos los compradores tienen funciones de utilidad lineal . Suponemos que cada recurso tiene un comprador potencial , un comprador que obtiene una utilidad positiva de ese recurso. Bajo este supuesto, los precios de compensación del mercado existen y son únicos. La prueba se basa en el programa Eisenberg-Gale. Las condiciones KKT implican que las soluciones óptimas (asignaciones y precios ) satisfacen las siguientes desigualdades:
- Todos los precios son no negativos: .
- Si un producto tiene un precio positivo, entonces toda su oferta se agota: .
- El BPB total es débilmente mayor que el BPB de cualquier recurso individual, .
- El agente i consume solo recursos con el máximo BPB posible, es decir,.
Suponga que cada producto tiene un comprador potencial - un comprador con . Entonces, la desigualdad 3 implica que, es decir, todos los precios son positivos. Entonces, la desigualdad 2 implica que todos los suministros están agotados. La desigualdad 4 implica que todos los presupuestos de los compradores están agotados. Es decir, el mercado se despeja. Dado que la función logarítmica es una función estrictamente cóncava , si hay más de una asignación de equilibrio, la utilidad obtenida por cada comprador en ambas asignaciones debe ser la misma (una disminución en la utilidad de un comprador no puede compensarse con un aumento en la utilidad de otro comprador). Esto, junto con la desigualdad 4, implica que los precios son únicos. [1] : 107
Vazirani [1] : 109-121 presentó un algoritmo para encontrar precios de equilibrio y asignaciones en un mercado Fisher lineal. El algoritmo se basa en la condición 4 anterior. La condición implica que, en equilibrio, cada comprador compra solo productos que le den un BPB máximo. Digamos que a un comprador le "gusta" un producto, si ese producto le da un BPB máximo en los precios actuales. Dado un vector de precios, construya una red de flujo en la que la capacidad de cada borde represente el dinero total que "fluye" a través de ese borde. La red es la siguiente:
- Hay un nodo fuente, s .
- Hay un nodo para cada producto; hay una ventaja de sa cada producto j , con capacidad(esta es la cantidad máxima de dinero que se puede gastar en el producto j , ya que la oferta se normaliza a 1).
- Hay un nodo para cada comprador; hay una ventaja de un producto a un comprador, con capacidad infinita, si al comprador le gusta el producto (en los precios actuales).
- Hay un nodo objetivo, t ; hay una ventaja de cada comprador i a t , con capacidad(el gasto máximo de i ).
El vector de precios p es un vector de precios de equilibrio, si y solo si los dos recortes ({s}, V \ {s}) y (V \ {t}, {t}) son mínimos . Por tanto, se puede encontrar un vector de precios de equilibrio utilizando el siguiente esquema:
- Comience con precios muy bajos, que están garantizados por debajo de los precios de equilibrio; en estos precios, a los compradores les queda algo de presupuesto (es decir, el flujo máximo no alcanza la capacidad de los nodos en t ).
- Aumente continuamente los precios y actualice la red de flujo en consecuencia, hasta que se agoten todos los presupuestos.
Existe un algoritmo que resuelve este problema en un tiempo polinomial débil.
Ver también
- División eficiente sin envidia
- Asignación eficiente de artículos aproximadamente equitativa
Referencias
- ↑ a b c d e Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). "Capítulo 5: algoritmos combinatorios para el equilibrio del mercado / Vijay V. Vazirani". Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
- ^ Bufanda, Herbert E. (1967). "Sobre el cálculo de los precios de equilibrio" . Cite journal requiere
|journal=
( ayuda ) - ^ OH Merrill (1972). Aplicaciones y extensiones de un algoritmo que calcula puntos fijos de cierto punto semicontinuo superior para establecer mapeos. Tesis doctoral.
- ^ Kakade, Sham M .; Kearns, Michael; Ortiz, Luis E. (2004). Shawe-Taylor, John; Cantante, Yoram (eds.). "Economía gráfica" . Teoría del aprendizaje . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 3120 : 17–32. doi : 10.1007 / 978-3-540-27819-1_2 . ISBN 978-3-540-27819-1.
- ^ a b c d Devanur, NR; Kannan, R. (1 de octubre de 2008). "Equilibrios de mercado en tiempo polinomial para número fijo de bienes o agentes" . 2008 49º Simposio Anual de IEEE sobre Fundamentos de las Ciencias de la Computación : 45–53. doi : 10.1109 / FOCS.2008.30 . ISBN 978-0-7695-3436-7. S2CID 13992175 .
- ^ Chen, X .; Dai, D .; Du, Y .; Teng, S. (1 de octubre de 2009). "Resolver la complejidad de los equilibrios Arrow-Debreu en mercados con utilidades separables aditivamente" . 2009 50º Simposio Anual de IEEE sobre Fundamentos de las Ciencias de la Computación : 273–282. arXiv : 0904.0644 . doi : 10.1109 / FOCS.2009.29 . ISBN 978-1-4244-5116-6. S2CID 580788 .
- ^ a b Chen, Xi; Teng, Shang-Hua (2009). Dong, Yingfei; Du, Ding-Zhu; Ibarra, Oscar (eds.). "El gasto no es más fácil que el comercio: sobre la equivalencia computacional de los equilibrios de Fisher y Arrow-Debreu" . Algoritmos y Computación . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 5878 : 647–656. arXiv : 0907.4130 . doi : 10.1007 / 978-3-642-10631-6_66 . ISBN 978-3-642-10631-6. S2CID 7817966 .
- ^ a b c Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (01-08-2020). "Dividir cosas malas es más difícil que dividir bienes: sobre la complejidad de la división justa y eficiente de las tareas". arXiv : 2008.00285 [ cs.GT ].
- ^ Devanur, Nikhil R .; Papadimitriou, Christos H .; Saberi, Amin; Vazirani, Vijay V. (5 de noviembre de 2008). "Equilibrio de mercado a través de 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 .
- ^ Orlin, James B. (5 de junio de 2010). "Algoritmos mejorados para calcular los precios de compensación del mercado de pesca: cálculo de los precios de compensación del mercado de pesca" . Actas del cuadragésimo segundo simposio ACM sobre teoría de la computación . STOC '10. Cambridge, Massachusetts, EE. UU.: Asociación de Maquinaria de Computación: 291–300. doi : 10.1145 / 1806689.1806731 . hdl : 1721,1 / 68009 . ISBN 978-1-4503-0050-6. S2CID 8235905 .
- ^ Codenotti, Bruno; McCune, Benton; Penumatcha, Sriram; Varadarajan, Kasturi (2005). Sarukkai, Sundar; Sen, Sandeep (eds.). "Equilibrio de mercado para las economías de intercambio CES: existencia, multiplicidad y computación" . FSTTCS 2005: Fundamentos de la tecnología del software y la informática teórica . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 3821 : 505–516. doi : 10.1007 / 11590156_41 . ISBN 978-3-540-32419-5.
- ^ Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor; Yanovskaia, Elena (1 de marzo de 2019). "Dividiendo males bajo utilidades aditivas" . Elección social y bienestar . 52 (3): 395–417. doi : 10.1007 / s00355-018-1157-x . ISSN 1432-217X .
- ^ 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 .
- ^ Brânzei, Simina; Sandomirskiy, Fedor (3 de julio de 2019). "Algoritmos para la división competitiva de tareas". arXiv : 1907.01766 [ cs.GT ].
- ^ Garg, Jugal; McGlaughlin, Peter (5 de mayo de 2020). "Computación de equilibrios competitivos con maná mixto" . Actas de la XIX Conferencia Internacional sobre Agentes Autónomos y Sistemas MultiAgent . AAMAS '20. Auckland, Nueva Zelanda: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente: 420–428. ISBN 978-1-4503-7518-4.
- ^ Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (2021-01-01), "Asignación competitiva de un maná mixto" , Actas del Simposio ACM-SIAM de 2021 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 1405-1424, doi : 10.1137 / 1.9781611976465.85 , ISBN 978-1-61197-646-5, consultado el 6 de marzo de 2021
- ^ Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (1998). Caviness, Bob F .; Johnson, Jeremy R. (eds.). "Un nuevo algoritmo para encontrar un punto en cada celda definida por una familia de polinomios" . Eliminación de cuantificadores y descomposición algebraica cilíndrica . Textos y monografías en computación simbólica. Viena: Springer: 341–350. doi : 10.1007 / 978-3-7091-9459-1_17 . ISBN 978-3-7091-9459-1.
- ^ Eisenberg, E. (1961). "Agregación de funciones de utilidad" . Ciencias de la gestión . 7 (4): 337–350. doi : 10.1287 / mnsc.7.4.337 .