eficiencia de Pareto fraccionaria

Supongamos que hay dos agentes y dos artículos. Alice valora los artículos en 3 y 2, y George en 4 y 1. Sea z la asignación que le da el primer artículo a Alice y el segundo a George. El perfil de utilidad de z es (3,1).

• z es Pareto-eficiente (discreta). Para comprobarlo, consideremos las demás asignaciones discretas posibles: sus perfiles de utilidad son (7,0), (0,3) o (2,4). En cualquier caso, la utilidad de al menos un agente es menor, por lo que ninguna asignación discreta domina a z .
• Sin embargo, z no es fraccionalmente eficiente en el sentido de Pareto. Está dominada por la asignación y, que le da a Alice la mitad del primer artículo y el segundo artículo completo, y la otra mitad del primer artículo a George; el perfil de utilidad de y es (3,5, 2), por lo que proporciona una mayor utilidad a ambos agentes.

El siguiente ejemplo ^{[ 1 ]} muestra el "precio" de fPO. La asignación integral que maximiza el producto de utilidades (también llamado bienestar de Nash) es PE, pero no fPO. Además, el producto de utilidades en cualquier asignación fPO es como máximo 1/3 del producto máximo. Hay cinco bienes {h1 _, h2 _, g1 _, g2 _, g3 _} y 3 agentes con los siguientes valores (donde C es una constante grande y d es una constante positiva pequeña):

Una asignación integral de producto máximo es {h ₁ },{h ₂ },{g ₁ ,g ₂ ,g ₃ }, con producto${\displaystyle C^{2}\cdot (3-2d)}$No se trata de una asignación fPO, ya que está dominada por una asignación fraccionaria: el agente 3 puede dar g ₁ al agente 1 (perdiendo 1- d de utilidad) a cambio de una fracción de h ₁ que ambos agentes valoran en 1- d /2. Este intercambio mejora estrictamente el bienestar de ambos agentes. Además, en cualquier asignación fPO entera, existe un agente A _i que recibe solo (como máximo) el bien g _i ; de lo contrario, se puede realizar un intercambio similar. Por lo tanto, una asignación fPO de producto máximo es {g ₁ ,h ₁ },{g ₂ ,h ₂ },{g ₃ }, con producto${\displaystyle (C+1)^{2}}$Cuando C es suficientemente grande y d es suficientemente pequeño, la relación de productos se aproxima a 1/3.

El siguiente ejemplo ^{[ 2 ] : Sec.6.6} muestra que fPO es incompatible con una noción de equidad conocida como EQx - equidad hasta cualquier bien. Hay tres bienes {g ₁ ,g ₂ ,g ₃ } y dos agentes con los siguientes valores (donde e es una pequeña constante positiva):

Solo dos asignaciones discretas son EQx:

• El agente 1 obtiene { g ₂ } y el agente 2 obtiene {g ₁ ,g ₃ }; el perfil de utilidad es (( 1+e ) ¹⁰ , 2+ e ). Esta asignación es PO pero no fPO, ya que está dominada por la asignación fraccionaria que da al agente 1 el paquete {g ₁ , (1-(1+ e ) ⁻⁹ ) fracción de g ₂ } y al agente 2 el paquete {g ₃ , (1+ e ) ⁻⁹ fracción de g ₂ }, en la que el perfil de utilidad es (( 1+e ) ¹⁰ , 2+2 e ).
• El agente 1 obtiene {g ₁ ,g ₃ } y el agente 2 obtiene { g ₂ }; el perfil de utilidad es (2+ e , ( 1+e ) ¹⁰ ). Esta asignación es PO pero no fPO, ya que está dominada por la asignación fraccionaria que da al agente 2 el paquete {g ₁ , (1-(1+ e ) ⁻⁹ ) fracción de g ₂ } y al agente 1 el paquete {g ₃ , (1+ e ) ⁻⁹ fracción de g ₂ }, en la que el perfil de utilidad es (2+2 e, ( 1+e ) ¹⁰ ).

El mismo ejemplo muestra que fPO es incompatible con una noción de equidad conocida como EFx : ausencia de envidia hasta cualquier bien. ^{[ 2 ] : Rem.5}

Una asignación es fPO si y solo si maximiza una suma ponderada de las utilidades de los agentes. Formalmente, sea w un vector de tamaño n que asigna un peso w _i a cada agente i . Decimos que una asignación z es w -máxima si se cumple alguna de las siguientes propiedades (equivalentes):

• Cada objeto o se asigna únicamente a los agentes i para quienes el producto${\displaystyle w_{i}\cdot v_{i,o}}$es máximo.
• ${\displaystyle z_{i,o}>0}$implica${\displaystyle w_{i}v_{i,o}\geq w_{j}v_{j,o}}$ para todos los agentes i , j y objetos o .
• La suma ponderada de utilidades,${\displaystyle \sum _{i}w_{i}\cdot u_{i}(\mathbf {z} )}$, es máximo entre todas las asignaciones, donde${\displaystyle u_{i}(\mathbf {z} ):=\sum _{o}v_{i,o}\cdot z_{i,o}=}$la utilidad del agente i en la asignación z .

Una asignación es fPO si y solo si es w- máxima para algún vector w de pesos estrictamente positivos. Esta equivalencia fue demostrada para bienes por Negishi ^{[ 3 ]} y Varian ^{[ 4 ]} . La demostración fue extendida para males por Branzei y Sandomirskiy ^{[ 5 ]} . Posteriormente, Sandomirskiy y Segal-Halevi la extendieron a valoraciones generales (mezclas de bienes y males) ^{[ 6 ] : Lem.2.3, Apéndice A}

Una asignación es fPO si y solo si su grafo de consumo dirigido no contiene ciclos con producto menor que 1. El grafo de consumo dirigido de una asignación z es un grafo bipartito en el que los nodos de un lado son agentes, los nodos del otro lado son objetos y las aristas dirigidas representan intercambios: una arista entrante al agente i representa objetos que el agente i desearía aceptar (bienes que no posee o bienes que posee); una arista entrante del agente i representa objetos con los que el agente i puede pagar (bienes que posee o bienes que no posee). El peso de la arista i - > o es | v i , o _| y _el peso de la arista o -> i es 1/| v _i,o |.

Una asignación se considera maliciosa si un agente i consume un objeto o con v _i,o ≤ 0, aunque exista otro agente j con v _j,o > 0; o bien, si un agente i consume un objeto o con v _i,o < 0, aunque exista otro agente j con v _j,o ≥ 0. Es evidente que toda asignación maliciosa puede mejorarse en el sentido de Pareto moviendo el objeto o del agente i al agente j . Por lo tanto, la ausencia de malicia es una condición necesaria para la optimización de Pareto.

Una asignación es fPO si y solo si no es maliciosa, y su grafo de consumo dirigido no tiene ciclos dirigidos en los que el producto de los pesos sea menor que 1. Esta equivalencia fue demostrada para bienes en el contexto del corte de pasteles por Barbanel. ^{[ 7 ]} Fue extendida para males por Branzei y Sandomirskiy. ^{[ 5 ]} Posteriormente fue extendida a valoraciones generales (mezclas de bienes y males) por Sandomirskiy y Segal-Halevi. ^{[ 6 ] : Lem.2.1, Apéndice A}

En un mercado de Fisher , cuando todos los agentes tienen utilidades lineales, cualquier equilibrio de mercado es fPO. Este es el primer teorema del bienestar . ^{[ 8 ]}

El siguiente algoritmo puede utilizarse para decidir si una asignación z dada es fPO:

• Calcular el gráfico de consumo dirigido de z ;
• Sustituya cada peso por su logaritmo;
• Utilice un algoritmo para encontrar un ciclo negativo, por ejemplo, el algoritmo de Bellman-Ford .
• Según la caracterización anterior, z es fPO si y solo si no se encuentra ningún ciclo negativo.

El tiempo de ejecución del algoritmo es O(| V || E |). Aquí, | V |= m + n y | E |≤ mn , donde m es el número de objetos y n el número de agentes. Por lo tanto, fPO se puede decidir en tiempo O( mn ( m + n )). ^{[ 6 ] : Lem.2.2, App.A}

Un algoritmo alternativo consiste en encontrar un vector w tal que la asignación dada sea w- maximizadora. Esto se puede lograr resolviendo un programa lineal . El tiempo de ejecución es débilmente polinomial.

En cambio, decidir si una asignación discreta dada es PO es co-NP-completa . ^{[ 9 ]} Por lo tanto, si el divisor afirma que una asignación es fPO, los agentes pueden verificar eficientemente esta afirmación; pero si el divisor afirma que una asignación es PO, puede ser imposible verificar esta afirmación eficientemente. ^{[ 10 ]}

Encontrar una asignación fPO es fácil. Por ejemplo, se puede encontrar usando una dictadura serial : el agente 1 toma todos los objetos para los que tiene un valor positivo; luego el agente 2 toma todos los objetos restantes para los que tiene un valor positivo; y así sucesivamente.

Un desafío más interesante es: dada una asignación inicial z (que puede ser fraccionaria y no fPO), encontrar una asignación fPO z* que sea una mejora de Pareto de z . Este desafío se puede resolver para n agentes y m objetos con valoraciones mixtas (positivas y negativas), en tiempo fuertemente polinomial , utilizando O( n²m² ( n + ^m ) ) operaciones . Además, en la asignación calculada hay como máximo n -1 comparticiones. ^{[ 6 ] : Lem.2.5, Apéndice A}

Si la asignación inicial z es una división equitativa, entonces la asignación final z* es proporcional. Por lo tanto, el lema anterior implica un algoritmo eficiente para encontrar una asignación fraccionaria PROP+fPO, con como máximo n -1 participaciones. De manera similar, si z es una división desigual, entonces z* es proporcional ponderada (proporcional para agentes con diferentes derechos). Esto implica un algoritmo eficiente para encontrar una asignación fraccionaria WPROP+fPO con como máximo n -1 participaciones.

La combinación del lema anterior con algoritmos más avanzados puede generar, en tiempo fuertemente polinomial, asignaciones libres de fPO y de envidia, con como máximo n -1 comparticiones. ^{[ 6 ] : Cor.2.6}

Existe un algoritmo que enumera todos los gráficos de consumo que corresponden a las asignaciones de fPO. ^{[ 6 ] : Prop.3.7} El tiempo de ejecución del algoritmo es${\displaystyle O(3^{{\frac {(n-1)n}{2}}\cdot D}\cdot m^{{\frac {(n-1)n}{2}}+2})}$donde D es el grado de degeneración de la instancia ( D = m - 1 para valoraciones idénticas; D = 0 para valoraciones no degeneradas, donde para cada par de agentes, las razones de valor de todos los m objetos son diferentes). En particular, cuando n es constante y D = 0, el tiempo de ejecución del algoritmo es fuertemente polinomial.

Varios trabajos recientes han considerado la existencia y el cálculo de una asignación discreta que sea a la vez fPO y que satisfaga una cierta noción de equidad .

• Barman y Krishnamurthy ^{[ 11 ]} demuestran que una asignación discreta fPO+PROP1 de bienes puede calcularse en tiempo fuertemente polinomial. Muestran un resultado similar para una asignación discreta fPO+EF11 , donde EF11 significa "libre de envidia salvo la adición de un bien y la eliminación de otro".
• Aziz, Moulin y Sandomirskiy ^{[ 12 ]} presentan un algoritmo que calcula una asignación fraccionaria fPO+WPROP de objetos mixtos (bienes y tareas). Utiliza un programa lineal que maximiza la suma de utilidades sujeta a proporcionalidad. Si se encuentra una solución factible básica (por ejemplo, utilizando el algoritmo simplex ), entonces el grafo de consumo de la asignación resultante es acíclico. Alternativamente, es posible eliminar ciclos del grafo de consumo resultante en tiempo polinomial. También presentan un algoritmo que convierte una asignación fraccionaria fPO+WPROP en una asignación discreta fPO+WPROP1 , en tiempo fuertemente polinomial.
• Barman, Krishnamurthy y Vaish ^{[ 1 ]} demuestran que siempre existe una asignación discreta de bienes que es fPO+EF1 .
• Murhekar y Garg ^{[ 13 ]} demuestran que se puede encontrar una asignación discreta fPO+EF1 de bienes en tiempo pseudopolinomial . También demuestran que, cuando todos los valores son positivos, existe una asignación discreta fPO+EQ1 que se puede encontrar en tiempo pseudopolinomial. Para instancias k -arias (cada agente tiene como máximo k valores diferentes para los bienes), los dos resultados anteriores se pueden calcular en tiempo polinomial. De manera similar, cuando el número de agentes es constante, los dos resultados anteriores se pueden calcular en tiempo polinomial.
• Garg y Murhekar ^{[ 10 ]} demuestran que, cuando la matriz de valoración contiene solo dos valores diferentes (positivos), siempre existe una asignación discreta fPO+EFx de bienes y puede calcularse en tiempo polinomial. Esto refuerza resultados anteriores que mostraron resultados similares para valoraciones binarias (0,1), ^{[ 14 ] [ 15 ]} y para PO+EFx. ^{[ 16 ]} Muestran resultados similares para PO+EQx .
• Garg, Murhekar y Qin ^{[ 17 ]} demuestran que, cuando la matriz de valoración contiene solo dos valores (negativos) diferentes, siempre existe una asignación discreta fPO+EF1 de tareas que puede calcularse en tiempo polinomial. También demuestran que, en este caso, una asignación fraccionaria fPO+EF de tareas (divisibles) puede calcularse en tiempo polinomial.
• Freeman, Sikdar, Vaish y Xia ^{[ 2 ]} presentan un algoritmo de tiempo polinomial para calcular una asignación discreta que es fPO+aproximadamente-EQ1 , para instancias en las que todas las valoraciones son potencias de (1+ e ) para alguna constante e >0. Demuestran que, incluso para tales instancias (cuando hay al menos 3 valoraciones diferentes), puede que no haya una asignación discreta fPO+EQx y ninguna asignación discreta fPO+EFx .
• Bai y Golz ^{[ 18 ]} presentan un algoritmo para calcular un vector de pesos w tal que, cuando las utilidades u _i de cada agente i se extraen aleatoriamente e independientemente de una distribución (que puede ser diferente para cada agente), cada agente i tiene la misma probabilidad de que w _i u _i sea mayor que w _j u _j de todos los demás agentes. Demuestran, utilizando el lema de Sperner , que siempre existe un vector de pesos igualadores. Cuando w es un vector de pesos igualadores, la asignación w -máxima está libre de envidia con alta probabilidad . Esto implica que, con alta probabilidad (bajo condiciones adecuadas sobre las distribuciones de utilidad), existe una asignación discreta fPO+EF .