Hispanopedia Wiki
Articulo de referencia

Cálculo del equilibrio de mercado

El cálculo del equilibrio de mercado (también llamado cálculo del equilibrio competitivo o cálculo de precios de equilibrio ) es un problema computacional que se sitúa en la int...

Hispanopedia WikiContenido en espanolLectura gratuita

El cálculo del equilibrio de mercado (también llamado cálculo del equilibrio competitivo o cálculo de precios de equilibrio ) es un problema computacional que se sitúa 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 . Existen diversos tipos de mercados, como el mercado de Fisher y el mercado de Arrow-Debreu , con recursos divisibles o indivisibles. El resultado requerido es un equilibrio competitivo , que consiste en un vector de precios (un precio para cada recurso) y una asignación (un conjunto de recursos para cada agente), de manera que cada agente obtenga el mejor conjunto posible (para él) dado su presupuesto, y el mercado se equilibre (todos los recursos se asignen).

El cálculo del equilibrio de mercado resulta interesante debido a que un equilibrio competitivo siempre es eficiente en el sentido de Pareto . El caso especial de un mercado de Fisher, en el que todos los compradores tienen ingresos iguales, es particularmente interesante, ya que en este contexto un equilibrio competitivo también está libre de envidia . Por lo tanto, el cálculo del equilibrio de mercado es una forma de encontrar una asignación que sea a la vez justa y eficiente.

Desde la década de 1960, se han realizado intentos de aplicar la teoría del equilibrio general para respaldar decisiones políticas en temas como la reforma tributaria o las reducciones arancelarias simultáneas . Estos modelos suelen ser extensos, por lo que se requiere una computación eficiente. [ 1 ]

Definiciones

La entrada para el cálculo del equilibrio del mercado consta de los siguientes ingredientes: [ 2 ] : cap.5

  1. Un conjunto demetro{\displaystyle m}recursos con suministros preespecificados. Los recursos pueden ser divisibles (en cuyo caso, su suministro se normaliza sin logaritmo a 1) o indivisibles .
    • Un haz está representado por un vector.incógnita=incógnita1,…,incógnitametro{\displaystyle \mathbf {x} =x_{1},\dots ,x_{m}}, dóndeincógnitaj{\displaystyle x_{j}}es la cantidad de recursoj{\displaystyle j}Cuando los recursos son indivisibles, todos los x j son enteros; cuando los recursos son divisibles, los x j pueden ser números reales arbitrarios (generalmente normalizados a [0,1]).
  2. Un conjunto denorte{\displaystyle n}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 agentei{\displaystyle i}se denota portúi{\displaystyle u_{i}}.
  3. Una dotación inicial para cada agente.
    • En un mercado de Fisher , la dotación es un presupuestoBi{\displaystyle B_{i}}del " dinero fiduciario ": un dinero que no tiene valor fuera del mercado y, por lo tanto, no entra en la función de utilidad. Dado que los agentes solo traen dinero, a menudo se les llama compradores .
    • En un mercado de Arrow-Debreu , la dotación es un conjunto arbitrario.mii{\displaystyle \mathbf {e} ^{i}}En este modelo, los agentes pueden ser tanto compradores como vendedores.

El resultado requerido debe contener los siguientes ingredientes:

  1. Un vector de preciospag=pag1,…,pagmetro{\displaystyle \mathbf {p} =p_{1},\dots,p_{m}}; un precio para cada recurso. El precio de un paquete es la suma de los precios de los recursos que lo componen, por lo que el precio de un paquete es la suma de los precios de los recursos que lo componen.incógnita{\displaystyle \mathbf {x} }espag⋅incógnita=∑j=1metropagj⋅incógnitaj{\displaystyle \mathbf {p} \cdot \mathbf {x} =\sum _{j=1}^{m}p_{j}\cdot x_{j}}.
  2. Una asignación - un paqueteincógnitai{\displaystyle \mathbf {x} ^{i}}para cada agente i .

El resultado debe cumplir los siguientes requisitos:

  1. El paquete incógnitai{\displaystyle \mathbf {x} ^{i}} debe ser asequible para mí , es decir, su precio debe ser como máximo el precio del agente i.dotación de.
    • En un mercado Fisher, esto significa que pag⋅incógnitai≤Bi{\displaystyle \mathbf {p} \cdot \mathbf {x} ^{i}\leq B_{i}}.
    • En un mercado Arrow-Debreu, esto significa que pag⋅incógnitai≤pag⋅mii{\displaystyle \mathbf {p} \cdot \mathbf {x} ^{i}\leq \mathbf {p} \cdot \mathbf {e} ^{i}}.
  2. El paquete incógnitai{\displaystyle \mathbf {x} ^{i}} debe estar en el conjunto de demanda de i :incógnitai∈Demandai(pag){\displaystyle \mathbf {x} ^{i}\in {\text{Demanda}}_{i}(\mathbf {p} )}, definido como el conjunto de cestas que maximizan la utilidad del agente entre todas las cestas asequibles (independientemente de la oferta), por ejemplo, en un mercado de Fisher:Demandai(pag):=arg⁡máximopagincógnita≤Bitúi(incógnita){\displaystyle {\text{Demanda}}_{i}(\mathbf {p} ):=\arg \max _{\mathbf {p} \mathbf {x} \leq B_{i}}u_{i}(\mathbf {x} )}
  3. El mercado se equilibra , es decir, todos los recursos se asignan. Los precios correspondientes se denominan precios de equilibrio del mercado .

Un precio y una asignación que satisfacen estos requisitos se denominan equilibrio competitivo (EC) o equilibrio de mercado ; los precios también se denominan precios de equilibrio o precios de liquidación .

Tipos de funciones de utilidad

El cálculo del equilibrio de mercado se ha estudiado bajo diversas suposiciones con respecto a las funciones de utilidad de los agentes.

  • Concavidad : la suposición más general (formulada por Fisher y Arrow&Debreu) ​​es que las utilidades de los agentes son funciones cóncavas , es decir, presentan rendimientos decrecientes . Esta suposición es muy común en economía.
  • Homogeneidad : En algunos casos, se supone que las utilidades son funciones homogéneas .
  • Separabilidad : Una función de utilidad se denomina separable si la utilidad de un conjunto es la suma de las utilidades de los recursos individuales en el conjunto, es decir,túi(incógnita)=∑j=1metrotúi,j(incógnitaj){\displaystyle u_{i}(\mathbf {x} )=\sum _{j=1}^{m}u_{i,j}(x_{j})}.
  • La linealidad por partes es un caso especial de separabilidad, en el que la función de utilidad para cada recurso individual,túi,j(incógnitaj){\displaystyle u_{i,j}(x_{j})}, es una función lineal a trozos de x j. Esta suposición es común en ciencias de la computación, ya que permite una representación finita de las funciones de utilidad.
    • Las funciones de utilidad que son lineales por tramos y cóncavas se suelen denominar PLC ; si además son separables, se denominan SPLC .
  • 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,túi(incógnita)=∑j=1metrotúi,j⋅incógnitaj{\displaystyle u_{i}(\mathbf {x} )=\sum _{j=1}^{m}u_{i,j}\cdot x_{j}}, dóndetúi,j{\displaystyle u_{i,j}}son constantes.
  • Las utilidades de Lenotief son un caso especial de utilidades de PLC.

Resultados principales

Algoritmos aproximados

Herbert Scarf [ 3 ] presentó una prueba de existencia de un CE utilizando el lema de Sperner (véase el mercado de Fisher ). Convirtió esta prueba en un algoritmo para calcular un CE aproximado. En su trabajo posterior, continuó desarrollando estos algoritmos. [ 4 ]

Merrill [ 5 ] dio un algoritmo extendido para CE aproximado.

También se pueden utilizar otros algoritmos para el cálculo de punto fijo , como el método de homotopía , para calcular CE.

Ninguno de estos algoritmos ofrece una garantía de tiempo de ejecución polinomial.

Resultados de dureza

Papadimitriou (quien inventó la clase PPAD ) [ 6 ] demostró que calcular una CE aproximada para mercados Arrow-Debreu dados por funciones de exceso de demanda agregadas es PPAD-completo. Resultados posteriores han demostrado la PPAD-dificultad incluso para clases más específicas de funciones de utilidad:

  • Codenotti, Saberi, Varadrajan y Ye [ 7 ] demuestran que los mercados de intercambio con utilidades de Leontief codifican juegos de dos jugadores con suma no nula. Esto implica que calcular el equilibrio de Nash (incluso en una clase especial que garantiza la existencia de un equilibrio de Nash) es al menos tan difícil como calcular el equilibrio de Nash para juegos de dos jugadores con suma no nula.
  • Devanur y Kannan [ 8 ] demostraron la dureza PPAD para un mercado Arrow-Debreu con utilidades Leontief.
  • Chen, Dai, Du y Teng [ 9 ] demostraron la dureza de PPAD para un mercado de Arrow-Debreu con utilidades SPLC. Su demostración muestra que este problema de equilibrio de mercado no tiene un FPTAS a menos que PPAD esté en P.
  • Chen y Teng [ 10 ] demostraron la dureza PPAD para un mercado de Fisher con utilidades SPLC.
  • Chaudhury, Garg, McGlaughlin y Mehta [ 11 ] demostraron la dureza PPAD para un mercado de Fisher con malas y utilidades lineales, incluso bajo una cierta condición que garantiza la existencia de CE.

Complementando estos resultados, Garg, Mehta, Vazirani y Yazdanbod [ 12 ] muestran que el cálculo de un CE aproximado con utilidades PLC se encuentra en PPAD. El principal desafío técnico fue demostrar que un punto fijo aproximado corresponde a un CE aproximado.

Etessami y Yannakkis (quienes definieron la clase de complejidad FIXP ) [ 13 ] demostraron que el cálculo de precios CE para mercados de intercambio con funciones de demanda algebraicas es FIXP-completo. Resultados posteriores han demostrado la dureza FIXP para clases más específicas de utilidades:

  • Garg, Mehta, Vazirani y Yazdanbod [ 12 ] demostraron la dureza FIXP incluso para utilidades Leontief, lo que implica dureza FIXP para utilidades PLC. Combinado con una prueba previa de pertenencia a FIXP, [ 14 ] sus resultados implican la completitud FIXP. El resultado de dureza FIXP se cumple cuando solo se consideran instancias "sí"; cuando se consideran todas las instancias, decidir si existe un CE es ETR-completo .

Algoritmos exactos

Para algunos casos especiales, se han desarrollado algoritmos de tiempo polinomial.

Eaves [ 15 ] demostró que, en un mercado de intercambio con utilidades Cobb-Douglas , el CE se puede escribir como la solución de un programa lineal ; por lo tanto, es posible calcular todos los CE en tiempo polinomial.

Deng, Papadimitriou y Safra [ 16 ] : El teorema 2 presenta un algoritmo politemporal para encontrar el CE cuando m está acotado y las utilidades son lineales.

Kakade, Kearns y Ortiz [ 17 ] : Sub.5.1 generalizan el algoritmo anterior para m acotado . Su algoritmo generalizado calcula una CE aproximada para una clase general de funciones de utilidad no lineales.

Newman y Primak [ 18 ] estudiaron dos variantes del método del elipsoide para encontrar un CE en un mercado de Arrow-Debreu con utilidades lineales. Demostraron que el método del elipsoide inscrito es computacionalmente más eficiente que el método del elipsoide circunscrito.

Codenotti y Varadarajan [ 19 ] propusieron un algoritmo politemporal para mercados de Fisher con utilidades de Leontief . Su enfoque se extiende a una familia más amplia de utilidades, que incluye las utilidades CES . Sin embargo, a diferencia del caso lineal, los precios de equilibrio pueden ser irracionales, lo que significa que no es posible un cálculo exacto.

Codenotti, McCune, Penumatcha y Varadarajan [ 20 ] dieron un algoritmo de tiempo polinomial para mercados Arrow-Debreu con utilidades CES donde la elasticidad de sustitución es al menos 1/2.

Codenotti, Pemmaraju, Raman y Varadarajan [ 21 ] presentaron un algoritmo de tiempo polinomial para mercados de intercambio con utilidades sustitutivas brutas débiles ; estos generalizan funciones de utilidad lineales, Cobb-Douglas, CES e incluso algunas no homogéneas.

Chen, Deng, Sun y Yao [ 22 ] dieron un algoritmo de tiempo polinomial para mercados de Fisher con utilidades logarítmicas , cuando m o n es constante.

Kamal Jain [ 23 ] introdujo un programa convexo (ya descrito en 1983 por Nenakov y Primak) que caracteriza el CE para mercados de intercambio con utilidades lineales, utilidades CES con r > 0 y algunas otras funciones de utilidad. También demostró que para utilidades lineales existe un CE normalizado con precios racionales. Jain utilizó esta propiedad para desarrollar una variante del método del elipsoide para calcular el CE exactamente en tiempo polinomial. Posteriormente, Ye [ 24 ] mostró cómo utilizar métodos de punto interior , que son mucho más eficientes en la práctica. Codenotti y Varadarajan [ 25 ] presentaron un programa convexo diferente que caracteriza el CE también para utilidades CES con -1 < r < 0.

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

Orlin [ 27 ] proporcionó un algoritmo mejorado para un modelo de mercado de Fisher con utilidades lineales, que se ejecuta en tiempoO((norte+metro)4registro⁡(túmáximo)+(norte+metro)3Bmáximo){\displaystyle O((n+m)^{4}\log(u_{\max })+(n+m)^{3}B_{\max })}Luego mejoró su algoritmo para que se ejecutara en tiempo fuertemente polinomial :O((metro+norte)4registro⁡(metro+norte)){\displaystyle O((m+n)^{4}\log(m+n))}.

Devanur y Kannan [ 8 ] dieron algoritmos para mercados de Arrow-Debreu con funciones de utilidad cóncavas , donde todos los recursos son bienes (las utilidades son positivas):

  • Cuando las utilidades son SPLC y n o m son constantes, su algoritmo es polinomial en el otro parámetro. La técnica consiste en descomponer el espacio de precios posibles en celdas mediante un número constante de hiperplanos, de modo que en cada celda se conoce la utilidad marginal umbral de cada comprador (cuando tanto n como m son variables, se dejó abierta la cuestión de si existe un algoritmo polinomial).
  • Cuando las utilidades son PLC (no necesariamente separables) y m es constante, su algoritmo es polinomial en n . Cuando tanto m como n son variables, encontrar un CE es PPAD-difícil incluso para las utilidades de Leontief , una subclase de utilidades PLC (cuando n es constante pero m es variable, se dejó abierto si existe un algoritmo de tiempo polinomial).

Garg, Mehta, Vazirani y Yazdanbod [ 12 ] dieron un algoritmo politiempo para las utilidades de Leontief cuando n es constante ym es variable.

Maná malo y mixto

Bogomolnaia y Moulin, y Sandomirskiy y Yanovskaia estudiaron la existencia y las propiedades de CE en un mercado de Fisher con bienes indeseables (artículos con utilidades negativas) [ 28 ] y con una mezcla de bienes y bienes indeseables. [ 29 ] A diferencia del escenario con bienes, cuando los recursos son indeseables, 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 CE se vuelve multivaluada. Este trabajo ha dado lugar a varios trabajos sobre algoritmos para encontrar CE en dichos mercados:

  • Branzei y Sandomirskiy [ 30 ] propusieron un algoritmo para encontrar todos los CE en un mercado de Fisher con bienes indeseables y utilidades lineales. Su algoritmo se ejecuta en tiempo fuertemente polinomial si n o m son fijos. Su enfoque combina tres ideas: todos los grafos de consumo de asignaciones de PO se pueden listar en tiempo polinomial; para un grafo de consumo dado, se puede construir un candidato a CE mediante una fórmula explícita; y se puede verificar si una asignación dada es un CE utilizando un cálculo de flujo máximo .
  • Garg y McGlaughlin [ 31 ] presentaron un algoritmo para calcular todos los CE en un mercado de Fisher con maná mixto y utilidades lineales. Su algoritmo se ejecuta en tiempo polinomial si n o m son fijos.
  • Chaudhury, Garg, McGlaughlin y Mehta [ 32 ] presentaron 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 caso no es polinomial (el problema es PPAD-difícil incluso con bienes [ 10 ] ), se ejecuta rápidamente en instancias aleatorias. También demuestra que el problema es PPAD, las soluciones son de 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 [ 11 ] : Teorema 3 muestran que, en un mercado de Fisher con bienes indeseables y utilidades lineales, es NP-difícil decidir si existe un CE. La misma dificultad se mantiene 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 del grafo, para la existencia de un CE. Con esta condición, siempre existe un CE, pero encontrarlo es PPAD-difícil. [ 11 ] : Teorema 5

bienes indivisibles

Cuando los bienes son indivisibles, puede que no exista un CE, pero puede ser posible calcular un CE aproximado.

Deng, Papadimitriou y Safra [ 16 ] estudian mercados de intercambio con m bienes, que pueden ser indivisibles. Demuestran lo siguiente:

  1. Con bienes indivisibles, es NP-difícil aproximar la deficiencia del mercado a un factor mejor que 1/3. Es NP-difícil hallar precios de equilibrio incluso cuando se sabe que existen. Esto se cumple incluso para utilidades lineales.
  2. En el caso de bienes indivisibles, existe un algoritmo de tiempo polinomial para encontrar una CE aproximada cuando m está acotada y las utilidades son lineales.
  3. Cuando las utilidades no son estrictamente cóncavas, calcular una asignación Pareto eficiente requiere Omega(n log(m+n)) bits de comunicación para coordinar los paquetes (cuando las utilidades son estrictamente cóncavas no se necesita coordinación, ya que cada agente tiene un paquete óptimo único dado el vector de precios). El límite inferior se mantiene incluso para bienes divisibles; para bienes indivisibles, el límite inferior se mantiene incluso para una asignación aproximadamente eficiente, para cualquier razón de aproximación. Estos límites se mantienen incluso para m constante .

Técnicas principales

Excelente relación calidad-precio.

Cuando las utilidades son lineales, el rendimiento 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 bpagbi,j:=túi,jpagj{\displaystyle bpb_{i,j}:={\frac {u_{i,j}}{p_{j}}}}; el BPB total esbpagbi,total:=∑j=1metrotúi,j⋅incógnitai,jBi{\displaystyle bpb_{i,total}:={\frac {\sum _{j=1}^{m}u_{i,j}\cdot x_{i,j}}{B_{i}}}}.

Una observación clave para encontrar un CE en un mercado de Fisher con utilidades lineales es que, en cualquier CE y para cualquier agente i : [ 2 ]

  • El BPB total es ligeramente mayor que el BPB de cualquier recurso individual, ∀j:bpagbi,j≤bpagbi,total{\displaystyle \forall j:bpb_{i,j}\leq bpb_{i,total}}.
  • El agente i consume únicamente recursos con el máximo BPB posible, es decir,∀j:incógnitai,j>0⟹bpagbi,j=bpagbi,total{\displaystyle \forall j:x_{i,j}>0\implies bpb_{i,j}=bpb_{i,total}}.

Supongamos que cada productoj{\displaystyle j}tiene un comprador potencial - un compradori{\displaystyle i}contúi,j>0{\displaystyle u_{i,j}>0}Entonces, las desigualdades anteriores implican quepagj>0{\displaystyle p_{j}>0}, es decir, todos los precios son positivos.

Descomposición celular

La descomposición celular [ 8 ] es un proceso de partición del espacio de precios posibles.R+metro{\displaystyle \mathbb {R} _{+}^{m}}en pequeñas "celdas", ya sea mediante hiperplanos o, más generalmente, mediante superficies polinómicas. Una celda se define especificando en qué lado de cada una de estas superficies se encuentra (con superficies polinómicas, las celdas también se conocen como conjuntos semialgebraicos ). Para cada celda, encontramos un vector de precios de equilibrio de mercado (es decir, un precio en esa celda para el cual existe una asignación de equilibrio de mercado), o verificamos que la celda no contiene un vector de precios de equilibrio de mercado. El desafío consiste en encontrar una descomposición con las siguientes propiedades:

  • El número total de celdas es polinomial en el tamaño de la entrada. Esto utiliza el hecho de que cualquier colección de k hiperplanos enR+metro{\displaystyle \mathbb {R} _{+}^{m}}divide el espacio enO(kmetro){\displaystyle O(k^{m})}células. [ 8 ] : Teorema 2 Esto es polinomial si m es fijo. Además, cualquier colección de k superficies polinomiales de grado como máximo d particiona el espacio enO(kmetro+1⋅dO(metro)){\displaystyle O(k^{m+1}\cdot d^{O(m)})}celdas no vacías, y pueden enumerarse en un tiempo lineal con respecto al tamaño de la salida. [ 33 ]
  • Encontrar un vector de precios de equilibrio de mercado en cada celda se puede hacer en tiempo polinomial, por ejemplo, utilizando 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 pueden expresarse como soluciones de un programa de optimización convexa denominado programa convexo de Eisenberg-Gale . [ 34 ] Este programa encuentra una asignación que maximiza la media geométrica ponderada de las utilidades de los compradores, donde las ponderaciones están determinadas por los presupuestos. De forma equivalente, maximiza la media aritmética ponderada de los logaritmos de las utilidades:

Maximizar∑i=1norte(Bi⋅registro⁡(túi)){\displaystyle \sum _{i=1}^{n}\left(B_{i}\cdot \log {(u_{i})}\right)}
Sujeto a:
Cantidades no negativas : Por cada compradori{\displaystyle i}y productoj{\displaystyle j}:incógnitai,j≥0{\displaystyle x_{i,j}\geq 0}
Suministros suficientes : Para cada productoj{\displaystyle j}:∑i=1norteincógnitai,j≤1{\displaystyle \sum _{i=1}^{n}x_{i,j}\leq 1}

(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 de Lagrange que pueden interpretarse como los precios ,pag1,…,pagmetro{\displaystyle p_{1},\dots ,p_{m}}En cada asignación que maximiza el programa de Eisenberg-Gale, cada comprador recibe la cesta demandada. Es decir, una solución al programa de Eisenberg-Gale representa un equilibrio de mercado. [ 2 ] : 141–142

Algoritmo de Vazirani: utilidades lineales, tiempo débilmente polinomial.

Un caso especial de utilidades homogéneas es cuando todos los compradores tienen funciones de utilidad lineales . Suponemos que cada recurso tiene un comprador potencial , un comprador que obtiene una utilidad positiva de ese recurso. Bajo este supuesto, existen precios de equilibrio de mercado y son únicos. La demostración se basa en el programa de Eisenberg-Gale. Las condiciones de KKT implican que las soluciones óptimas (asignacionesincógnitai,j{\displaystyle x_{i,j}}y preciospagj{\displaystyle p_{j}}) satisfacen las siguientes desigualdades:

  1. Todos los precios son no negativos:pagj≥0{\displaystyle p_{j}\geq 0}.
  2. Si un producto tiene un precio positivo, entonces toda su oferta está agotada:pagj>0⟹∑i=1norteincógnitai,j=1{\displaystyle p_{j}>0\implies \sum _{i=1}^{n}x_{i,j}=1}.
  3. El BPB total es ligeramente mayor que el BPB de cualquier recurso individual, ∀j:bpagbi,j≤bpagbi,total{\displaystyle \forall j:bpb_{i,j}\leq bpb_{i,total}}.
  4. El agente i consume únicamente recursos con el máximo BPB posible, es decir,∀j:incógnitai,j>0⟹bpagbi,j=bpagbi,total{\displaystyle \forall j:x_{i,j}>0\implies bpb_{i,j}=bpb_{i,total}}.

Supongamos que cada productoj{\displaystyle j}tiene un comprador potencial - un compradori{\displaystyle i}contúi,j>0{\displaystyle u_{i,j}>0}. Entonces, la desigualdad 3 implica quepagj>0{\displaystyle p_{j}>0}Es decir, todos los precios son positivos. Entonces, la desigualdad 2 implica que todas las ofertas se han agotado. La desigualdad 4 implica que los presupuestos de todos los compradores se han agotado. Es decir, el mercado se equilibra. Dado que la función logaritmo es una función estrictamente cóncava , si hay más de una asignación de equilibrio, la utilidad que obtiene cada comprador en ambas asignaciones debe ser la misma (una disminución en la utilidad de un comprador no puede ser compensada por un aumento en la utilidad de otro comprador). Esto, junto con la desigualdad 4, implica que los precios son únicos. [ 2 ] : 107

Vazirani [ 2 ] : 109–121 presentó un algoritmo para encontrar precios y asignaciones de equilibrio en un mercado lineal de Fisher. El algoritmo se basa en la condición 4 anterior. Esta condición implica que, en equilibrio, cada comprador adquiere únicamente productos que le proporcionan el máximo BPB. Digamos que un comprador "prefiere" un producto si este le proporciona el máximo BPB a los precios actuales. Dado un vector de precios, construya una red de flujo en la que la capacidad de cada arista represente el flujo total de dinero a través de ella. La red es la siguiente:

  • Hay un nodo fuente, s .
  • Hay un nodo para cada producto; hay una arista desde s a cada producto j , con capacidadpagj{\displaystyle p_{j}}(esta es la cantidad máxima de dinero que se puede gastar en el producto j , ya que la oferta está normalizada a 1).
  • Existe un nodo para cada comprador; hay una arista desde un producto hasta un comprador, con capacidad infinita, si y solo si al comprador le gusta el producto (a los precios actuales).
  • Hay un nodo objetivo, t ; hay una arista desde cada comprador i hasta t , con capacidadBi{\displaystyle B_{i}}(el gasto máximo de i ).

El vector de precios p es un vector de precios de equilibrio si y solo si los dos cortes ({s},V\{s}) y (V\{t},{t}) son cortes mínimos . Por lo tanto, se puede encontrar un vector de precios de equilibrio utilizando el siguiente esquema:

  • Comience con precios muy bajos, que están garantizados para estar por debajo de los precios de equilibrio; con estos precios, los compradores tienen algo de presupuesto disponible (es decir, el flujo máximo no alcanza la capacidad de los nodos en t ).
  • Incremente continuamente los precios y actualice la red de flujos en consecuencia, hasta que se agoten todos los presupuestos.

Existe un algoritmo que resuelve este problema en tiempo débilmente polinomial.

Generalizaciones y extensiones

Mercados gráficos

Kakade, Kearns y Ortiz [ 17 ] estudiaron un mercado de Arrow-Debreu generalizado en el que los agentes se ubican en un grafo, el comercio solo puede ocurrir entre agentes vecinos y todos los mercados locales deben equilibrarse. Demostraron un teorema general de existencia para equilibrios gráficos y un algoritmo para calcular equilibrios de grafos que se ejecuta en tiempo polinomial en el número de consumidores cuando el grafo es un árbol. Sus algoritmos también funcionan para agentes con utilidades no lineales.

Computación en línea

Gao, Peysakhovich y Kroer [ 35 ] presentaron un algoritmo para el cálculo en línea del equilibrio del mercado.

Véase también

Lecturas adicionales

  • [ 36 ] examinar la historia del cálculo de equilibrios de mercado hasta 2004.
  • [ 37 ] discuten la aproximación del equilibrio de mercado maximizando el bienestar de Nash.
  • [ 38 ] presentan la dinámica de respuesta proporcional y demuestran que converge a un equilibrio de mercado.
  • [ 39 ] presentan una generalización de la dinámica de respuesta proporcional, que converge a un equilibrio de mercado cuando los agentes tienenvaloraciones de sustitutos brutos.

Referencias

  1. ↑ Codenotti, Bruno; Pemmaraju, Sriram; Varadarajan, Kasturi (1 de diciembre de 2004). "El cálculo de los equilibrios del mercado" . Noticias SIGACT . 35 (4): 23– 37. doi : 10.1145/1054916.1054927 . ISSN 0163-5700 . 
  2. 1 2 3 4 5 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ítmica (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
  3. ↑ Scarf, Herbert E. (1967). "Sobre el cálculo de precios de equilibrio" . Documentos de debate de la Fundación Cowles .
  4. ↑ Scarf, Herbert E. (1 de enero de 1982), Capítulo 21 El cálculo de los precios de equilibrio: Una exposición , Manual de Economía Matemática, vol. 2, Elsevier, págs. 1007–1061 , doi : 10.1016/S1573-4382(82)02016-5 , ISBN   978-0-444-86127-6Consultado el 14 de agosto de 2025.
  5. ↑ OH Merrill (1972). Aplicaciones y extensiones de un algoritmo que calcula puntos fijos de ciertas aplicaciones semicontinuas superiores de puntos a conjuntos. Tesis doctoral.
  6. ↑ Christos Papadimitriou (1994). "Sobre la complejidad del argumento de paridad y otras pruebas ineficientes de existencia" (PDF) . Journal of Computer and System Sciences . 48 (3): 498– 532. doi : 10.1016/S0022-0000(05)80063-7 . Archivado del original (PDF) el 4 de marzo de 2016. Recuperado el 8 de marzo de 2008 .
  7. ↑ Codenotti, Bruno; Saberi, Amin; Varadarajan, Kasturi; Ye, Yinyu (22 de enero de 2006). "Las economías de Leontief codifican juegos de dos jugadores de suma distinta de cero" . Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmo discreto - SODA '06 . Estados Unidos: Sociedad de Matemáticas Industriales y Aplicadas. págs. 659– 667. doi : 10.1145/1109557.1109629 . ISBN  978-0-89871-605-4.
  8. 1 2 3 4 Devanur, NR; Kannan, R. (1 de octubre de 2008). "Equilibrios de mercado en tiempo polinomial para un número fijo de bienes o agentes". 49.º Simposio Anual IEEE sobre Fundamentos de la Informática , 2008. págs. 45-53 . doi : 10.1109/FOCS.2008.30 . ISBN  978-0-7695-3436-7. S2CID 13992175 . 
  9. ↑ Chen, X.; Dai, D.; Du, Y.; Teng, S. (1 de octubre de 2009). «Resolviendo la complejidad de los equilibrios de Arrow-Debreu en mercados con utilidades aditivamente separables». 50.º Simposio Anual IEEE sobre Fundamentos de la Informática de 2009. págs. 273-282 . arXiv : 0904.0644 . doi : 10.1109/FOCS.2009.29 . ISBN  978-1-4244-5116-6. S2CID 580788 . 
  10. 1 2 Chen, Xi; Teng, Shang-Hua (2009). "Gastar no es más fácil que comerciar: sobre la equivalencia computacional de los equilibrios de Fisher y Arrow-Debreu" . En Dong, Yingfei; Du, Ding-Zhu; Ibarra, Oscar (eds.). Algoritmos y computación . Notas de clase en ciencias de la computación. Vol. 5878. Berlín, Heidelberg: Springer. pp. 647–656 . arXiv : 0907.4130 . doi : 10.1007/978-3-642-10631-6_66 . ISBN   978-3-642-10631-6. S2CID 7817966 . 
  11. 1 2 3 Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (1 de agosto de 2020). "Dividir lo malo es más difícil que dividir lo bueno: Sobre la complejidad de la división justa y eficiente de las tareas domésticas". arXiv : 2008.00285 [ cs.GT ].
  12. 1 2 3 Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra (19 de junio de 2017). "Resolviendo la complejidad de los mercados de intercambio de Leontief y PLC bajo equilibrios exactos y aproximados" . Actas del 49.º Simposio Anual ACM SIGACT sobre Teoría de la Computación . STOC 2017. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 890–901 . doi : 10.1145/3055399.3055474 . ISBN  978-1-4503-4528-6.
  13. ^ Etessami, Kousha; Yannakakis, Mihalis (enero de 2010). "Sobre la complejidad de los equilibrios de Nash y otros puntos fijos" . Revista SIAM de Computación . 39 (6): 2531–2597.doi : 10.1137 / 080720826 . hdl : 20.500.11820/98752471-0a7a-4366-8871-b8f1984190ef . ISSN 0097-5397 . 
  14. ↑ Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. (31 de mayo de 2014). «Dicotomías en el cálculo de equilibrio y algoritmos de pivote complementarios para una nueva clase de funciones de utilidad no separables» . Actas del cuadragésimo sexto simposio anual de la ACM sobre Teoría de la Computación . STOC '14. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 525–534 . doi : 10.1145/2591796.2591863 . ISBN  978-1-4503-2710-7.
  15. ↑ Curtis Eaves, B. (1985), "Solución finita de mercados de comercio puro con utilidades Cobb-Douglas" , en Manne, Alan S. (ed.), Equilibrio económico: formulación y solución de modelos , Estudios de programación matemática, vol. 23, Berlín, Heidelberg: Springer, pp. 226–239 , doi : 10.1007/bfb0121035 , ISBN   978-3-642-00917-4Consultado el 15 de agosto de 2025.
  16. 1 2 Deng, Xiaotie ; Papadimitriou, Christos; Safra, Shmuel (19 de mayo de 2002). "Sobre la complejidad de los equilibrios" . Actas del trigésimo cuarto simposio anual de la ACM sobre Teoría de la Computación . STOC '02. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 67–71 . doi : 10.1145/509907.509920 . ISBN  978-1-58113-495-7.
  17. 1 2 Kakade, Sham M.; Kearns, Michael; Ortiz, Luis E. (2004). "Graphical Economics" . En Shawe-Taylor, John; Singer, Yoram (eds.). Learning Theory . Lecture Notes in Computer Science. Vol. 3120. Berlín, Heidelberg: Springer. pp. 17–32 . doi : 10.1007/978-3-540-27819-1_2 . ISBN   978-3-540-27819-1.
  18. ↑ Newman, DJ; Primak, ME (1 de diciembre de 1992). "Complejidad de los métodos de elipsoides circunscritos e inscritos para resolver modelos económicos de equilibrio" . Matemáticas Aplicadas y Computación . 52 (2): 223– 231. doi : 10.1016/0096-3003(92)90079-G . ISSN 0096-3003 . 
  19. ↑ Codenotti, Bruno; Varadarajan, Kasturi (2004). "Cálculo eficiente de precios de equilibrio para mercados con Leontief Utilities" . En Díaz, Josep; Karhumäki, Juhani; Lepistö, Arto; Sannella, Donald (eds.). Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. vol. 3142. Berlín, Heidelberg: Springer. págs. 371– 382. doi : 10.1007/978-3-540-27836-8_33 . ISBN   978-3-540-27836-8.
  20. ↑ Codenotti, Bruno; McCune, Benton; Penumatcha, Sriram; Varadarajan, Kasturi (2005). "Equilibrio de mercado para economías de intercambio CES: existencia, multiplicidad y computación" . En Sarukkai, Sundar; Sen, Sandeep (eds.). FSTTCS 2005: Fundamentos de la tecnología del software y la informática teórica . Lecture Notes in Computer Science. Vol. 3821. Berlín, Heidelberg: Springer. pp. 505–516 . doi : 10.1007/11590156_41 . ISBN   978-3-540-32419-5.
  21. ↑ Codenotti, Bruno; Pemmaraju, Sriram; Varadarajan, Kasturi (23 de enero de 2005). «Sobre el cálculo en tiempo polinomial de equilibrios para ciertas economías de intercambio» . Actas del decimosexto simposio anual ACM-SIAM sobre algoritmos discretos . SODA '05. EE. UU.: Society for Industrial and Applied Mathematics: 72–81 . ISBN 978-0-89871-585-9.
  22. ↑ Chen, Ning; Deng, Xiaotie; Sun, Xiaoming; Yao, Andrew Chi-Chih (2004). "Precio de equilibrio de Fisher con una clase de funciones de utilidad cóncavas" . En Albers, Susanne; Radzik, Tomasz (eds.). Algoritmos – ESA 2004. Lecture Notes in Computer Science. Vol. 3221. Berlín, Heidelberg: Springer. pp. 169–179 . doi : 10.1007/978-3-540-30140-0_17 . ISBN   978-3-540-30140-0.
  23. ↑ Jain, Kamal (enero de 2007). "Un algoritmo de tiempo polinomial para calcular un equilibrio de mercado de Arrow-Debreu para utilidades lineales" . SIAM Journal on Computing . 37 (1): 303–318 . doi : 10.1137/S0097539705447384 . ISSN 0097-5397 . 
  24. ↑ Ye, Yinyu (1 de enero de 2008). "Un camino hacia el equilibrio de mercado competitivo de Arrow-Debreu" . Programación matemática . 111 (1): 315–348 . doi : 10.1007/s10107-006-0065-5 . ISSN 1436-4646 . 
  25. ↑ Codenotti, Bruno; Varadarajan, Kasturi (10 de marzo de 2005). Equilibrio de mercado en economías de intercambio con algunas familias de funciones de utilidad cóncavas (Informe). Biblioteca Universitaria de Múnich, Alemania.
  26. ^ 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 .  
  27. ↑ Orlin, James B. (5 de junio de 2010). «Algoritmos mejorados para el cálculo de los precios de equilibrio del mercado de Fisher» . 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. S2CID 8235905 . 
  28. ↑ Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor; Yanovskaia, Elena (1 de marzo de 2019). "Dividiendo los males bajo utilidades aditivas" . Social Choice and Welfare . 52 (3): 395– 417. doi : 10.1007/s00355-018-1157-x . ISSN 1432-217X . 
  29. ↑ 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 .  
  30. ↑ Brânzei, Simina; Sandomirskiy, Fedor (3 de julio de 2019). "Algoritmos para la división competitiva de tareas". arXiv : 1907.01766 [ cs.GT ].
  31. ↑ Garg, Jugal; McGlaughlin, Peter (5 de mayo de 2020). «Cálculo 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.
  32. ^ 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. 1405-1424 , arXiv : 2008.02753 , doi : 10.1137/1.9781611976465.85 , ISBN  978-1-61197-646-5
  33. ↑ Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (1998). "Un nuevo algoritmo para encontrar un punto en cada celda definida por una familia de polinomios" . En Caviness, Bob F.; Johnson, Jeremy R. (eds.). Eliminación de cuantificadores y descomposición algebraica cilíndrica . Textos y monografías en computación simbólica. Viena: Springer. pp. 341–350 . doi : 10.1007/978-3-7091-9459-1_17 . ISBN  978-3-7091-9459-1.
  34. ↑ Eisenberg, E. (1961). «Agregación de funciones de utilidad» . Management Science . 7 (4): 337– 350. doi : 10.1287/mnsc.7.4.337 . Archivado del original el 23 de septiembre de 2017.
  35. ↑ Gao, Yuan; Peysakhovich, Alex; Kroer, Christian (2021). "Equilibrio de mercado en línea con aplicación a la división justa" . Advances in Neural Information Processing Systems . 34. Curran Associates, Inc.: 27305–27318 . arXiv : 2103.12936 .
  36. ↑ Codenotti, Bruno; Pemmaraju, Sriram; Varadarajan, Kasturi (1 de diciembre de 2004). "El cálculo de los equilibrios del mercado" . Noticias SIGACT . 35 (4): 23– 37. doi : 10.1145/1054916.1054927 . ISSN 0163-5700 . 
  37. ↑ Garg, Jugal; Tao, Yixin; Végh, László A. (enero de 2025), "Aproximación del equilibrio competitivo mediante el bienestar de Nash" , Actas del Simposio Anual ACM-SIAM de 2025 sobre Algoritmos Discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 2538–2559 , doi : 10.1137/1.9781611978322.83 , ISBN  978-1-61197-832-2Consultado el 25 de julio de 2025.
  38. ↑ Wu, Fang; Zhang, Li (11 de junio de 2007). «La dinámica de respuesta proporcional conduce al equilibrio del mercado» . Actas del trigésimo noveno simposio anual de la ACM sobre Teoría de la Computación . STOC '07. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 354–363 . doi : 10.1145/1250790.1250844 . ISBN  978-1-59593-631-8.
  39. ↑ Cheung, Yun Kuen; Cole, Richard; Tao, Yixin (3 de junio de 2025), Dinámica de respuesta proporcional en mercados de sustitutos brutos , arXiv : 2506.02852