Equilibrio competitivo aproximado a partir de ingresos iguales

El Equilibrio Competitivo Aproximado a partir de Ingresos Iguales ( A-CEEI ) es un procedimiento para la asignación justa de artículos . Fue desarrollado por Eric Budish. ^{[ 1 ]}

El CEEI (Equilibrio Competitivo a partir de Ingresos Iguales) es una regla fundamental para la división justa de los recursos divisibles. Divide los recursos según el resultado del siguiente proceso hipotético:

• Cada agente recibe una unidad de dinero fiduciario . Esta es la parte de Igualdad de Ingresos del CEEI.
• Los agentes comercian libremente hasta que el mercado alcanza un equilibrio competitivo . Este equilibrio se define mediante un vector de precios y una asignación, de modo que (a) cada cesta asignada es óptima para su agente en función de sus ingresos (el agente no puede adquirir una cesta mejor con los mismos ingresos) y (b) el mercado se equilibra (la suma de todas las asignaciones es exactamente igual a la dotación inicial).

La asignación de equilibrio está demostrablemente libre de envidia y es Pareto eficiente . Además, cuando los agentes tienen funciones de utilidad lineales , la asignación CEEI se puede calcular de manera eficiente.

Lamentablemente, cuando existen indivisibilidades, no siempre existe un CEEI, por lo que no puede utilizarse directamente para la asignación justa de ítems . Sin embargo, puede aproximarse, y dicha aproximación posee buenas propiedades de equidad, eficiencia y estrategia.

A-CEEI solo presupone que los agentes saben cómo clasificar conjuntos de artículos. La clasificación no tiene por qué ser débilmente aditiva ni siquiera monótona.

A-CEEI con parámetros${\displaystyle \alpha,\beta}$divide los recursos según el resultado del siguiente proceso hipotético:

• Ingreso aproximado: cada agente recibe un ingreso entre 1 y${\displaystyle 1+\beta }$Los ingresos exactos de cada agente pueden determinarse aleatoriamente o por antigüedad (los agentes con más antigüedad pueden percibir un ingreso ligeramente superior).
• CE aproximado: se calcula un vector de precios y una asignación, de modo que (a) cada paquete asignado sea óptimo para su agente dado su presupuesto, y (b) el mercado "casi" se equilibra: la distancia euclidiana entre la suma de todas las asignaciones y la dotación inicial es como máximo${\displaystyle \alpha }$.

Budismo demuestra que, para cualquier${\displaystyle \beta >0}$, existe${\displaystyle \alpha,\beta}$-CEEI donde${\displaystyle \alpha }$depende del mínimo entre el número de tipos de artículos diferentes y el número de artículos diferentes que un agente puede recibir.

La asignación satisface las siguientes propiedades:

• Libre de envidia excepto 1 artículo (ver asignación de artículo libre de envidia ).
• ${\displaystyle (n+1)}$-Garantía de participación máxima.
• Eficiencia de Pareto con respecto a los artículos asignados. Es decir, no existe intercambio que mejore la eficiencia de Pareto entre los agentes, pero sí puede haber intercambios que la mejoren entre un agente y el creador de mercado.

Además, el mecanismo A-CEEI es inmune a la manipulación estratégica en grandes cantidades: cuando hay muchos agentes, cada uno tiene una influencia mínima sobre el precio, por lo que actúan como tomadores de precios . En consecuencia, es óptimo que cada agente reporte sus valoraciones reales, ya que esto permite que el mecanismo le asigne una combinación óptima de productos en función de los precios.

La asignación A-CEEI es difícil de calcular: es PPAD completa . ^{[ 2 ]}

Sin embargo, en problemas de tamaño realista, el A-CEEI se puede calcular utilizando un proceso de búsqueda de dos niveles:

1. Nivel maestro: el centro utiliza la búsqueda tabú para sugerir precios;
2. Nivel de agente: se resuelven programas de programación entera mixta para encontrar las demandas de los agentes a los precios actuales.

El programa a nivel de agente se puede ejecutar en paralelo para todos los agentes, por lo que este método escala de forma casi óptima en cuanto al número de procesadores. ^{[ 3 ]}

El mecanismo se ha considerado para la tarea de asignar estudiantes a cursos en la Wharton School de la Universidad de Pensilvania . ^{[ 4 ]}

El algoritmo de Máximo Bienestar de Nash (MNW) encuentra una asignación que maximiza el producto de las utilidades de los agentes. Es similar a A-CEEI en varios aspectos: ^{[ 5 ]}

• Ambos algoritmos encuentran una asignación EF-except-1.
• Ambos algoritmos se aproximan a la garantía de participación maximin.

Sin embargo, A-CEEI tiene varias ventajas:

• Funciona con funciones de utilidad arbitrarias, no solo con las submodulares . Ni siquiera requiere que las preferencias sean monotonicidad.
• Funciona con datos de entrada ordinales: los agentes solo deben informar su clasificación en los conjuntos, no su valoración numérica de los artículos.
• Es una estrategia a prueba de fallos "a gran escala".

Por otro lado, A-CEEI tiene varias desventajas:

• Existe un error de aproximación en los artículos que se asignan: algunos artículos pueden tener una demanda excesiva o una oferta excesiva. ^{[ 6 ]}
• En particular, la asignación devuelta no es Pareto-eficiente: algunos elementos permanecen sin asignar (solo es Pareto-eficiente con respecto a los elementos asignados).

El error de aproximación de A-CEEI aumenta con el número de elementos distintos, pero no con el número de jugadores ni con el número de copias de cada elemento. Por lo tanto, A-CEEI es mejor cuando hay muchos agentes y muchas copias de cada elemento. Una aplicación típica se da cuando los agentes son estudiantes y los elementos son puestos en cursos. ^{[ 6 ]}

Por el contrario, el método MNW es mejor cuando hay pocos agentes y muchos elementos distintos, como en la división de una herencia.

A-CEEI (y CEEI en general) está relacionado, pero no es idéntico, al concepto de equilibrio competitivo .

• El equilibrio competitivo (EC) es un concepto descriptivo: describe la situación en el libre mercado cuando el precio se estabiliza y la demanda es igual a la oferta.
• CEEI es un concepto normativo: describe una regla para dividir las mercancías entre las personas.

• Subasta combinatoria