Eficiencia de Pareto fraccional

En economía y ciencias de la computación , la eficiencia fraccional de Pareto u optimalidad fraccional de Pareto (fPO) es una variante de la eficiencia de Pareto utilizada en el contexto de la asignación justa de objetos discretos . Una asignación de objetos se denomina discreta si cada elemento se asigna en su totalidad a un solo agente; se denomina fraccionaria si algunos objetos se dividen entre dos o más agentes. Una asignación discreta se denomina Pareto-eficiente (PO) si no está dominada por Pareto por ninguna asignación discreta; se denomina fraccionalmente Pareto-eficiente (fPO) si no está dominada por Pareto por ninguna asignación discreta o fraccionaria . ^[1] Por lo tanto, fPO es un requisito más fuerte que PO: cada asignación fPO es PO, pero no toda asignación PO es fPO.

Definiciones formales

Hay un conjunto de n agentes y un conjunto de m objetos. La asignación se determina mediante una matriz z de n por m , donde cada elemento z [ i , o ] es un número real entre 0 y 1. Representa la fracción que el agente i obtiene del objeto o . Para cada objeto o , la suma de todos los elementos en la columna o es igual a 1, ya que se asigna el objeto completo.

Una asignación se denomina discreta o integral si todos sus elementos z [ i , o ] son ​​0 o 1; es decir, cada objeto se asigna enteramente a un solo agente.

Una asignación y se denomina mejora de Pareto de una asignación z si la utilidad de todos los agentes en y es al menos tan grande como en z y la utilidad de algunos agentes en y es estrictamente mayor que en z . En este caso, también decimos que y domina en el sentido de Pareto a z .

Si una asignación z no está dominada en el sentido de Pareto por ninguna asignación discreta, entonces se denomina eficiente en el sentido de Pareto discreta o simplemente eficiente en el sentido de Pareto (generalmente abreviado PO ).

Si z no está dominado por Pareto mediante ninguna asignación, ya sea discreta o fraccionaria, entonces se dice que es fraccionalmente Pareto-eficiente (generalmente abreviado fPO ).

Ejemplos

PO no implica fPO

Supongamos que hay dos agentes y dos artículos. Alice valora los artículos en 3, 2 y George en 4, 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 (discreta) eficiente en el sentido de Pareto. Para comprobarlo, considere las otras asignaciones discretas posibles: sus perfiles de utilidad son (7,0) o (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 otorga a Alice la mitad del primer artículo y todo el segundo artículo, y la otra mitad del primer artículo a George; el perfil de utilidad de y es (3,5, 2), por lo que otorga una utilidad mayor a ambos agentes.

El precio del fPO

El siguiente ejemplo ^[1] muestra el "precio" de fPO. La asignación integral que maximiza el producto de las utilidades (también llamada bienestar de Nash) es PE pero no fPO. Además, el producto de las utilidades en cualquier asignación de fPO es como máximo 1/3 del producto máximo. Hay cinco bienes {h ₁ ,h ₂ ,g ₁ ,g ₂ ,g ₃ } 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 máximo producto es {h ₁ },{h ₂ },{g ₁ ,g ₂ ,g ₃ }, con producto . No es 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 integral fPO, 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 máximo producto es {g ₁ ,h ₁ },{g ₂ ,h ₂ },{g ₃ }, con producto . Cuando C es suficientemente grande y d es suficientemente pequeño, la relación del producto se acerca a 1/3. ${\displaystyle C^{2}\cdot (3-2d)}$ ${\displaystyle (C+1)^{2}}$

Ninguna asignación de fPO es casi equitativa

El siguiente ejemplo ^{[2] : Sec.6.6} muestra que fPO es incompatible con una noción de justicia 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):

Sólo 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 el 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 el 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 (libre de envidia hasta cualquier bien). ^{[2] : Rem.5}

Caracterización

Maximizar una suma ponderada de utilidades

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 , asignando un peso w _i a cada agente i . Decimos que una asignación z es w -máxima si se cumple una de las siguientes propiedades (equivalentes):

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

Una asignación es fPO si y sólo si es w -máxima para algún vector w de pesos estrictamente positivos. Negishi ^[3] y Varian demostraron esta equivalencia para bienes . ^[4] Branzei y Sandomirskiy extendieron la demostración para males. ^[5] Sandomirskiy y Segal-Halevi la extendieron posteriormente a valoraciones generales (mezclas de bienes y males). ^{[6] : Lem.2.3, App.A}

No hay ciclos de mejoras en el gráfico de consumo

Una asignación es fPO si y solo si su gráfico de consumo dirigido no contiene ciclos con producto menor que 1. El gráfico de consumo dirigido de una asignación z es un gráfico 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 que entra al agente i representa objetos que el agente i quisiera aceptar (bienes que no posee o bienes que posee); una arista que entra 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 |, 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 denomina maliciosa si algún objeto o es consumido por algún agente i con v _i,o ≤ 0, aunque exista algún otro agente j con v _j,o > 0; o, algún objeto o es consumido por algún agente i con v _i,o < 0, aunque exista algún otro agente j con v _j,o ≥ 0. Claramente, cada asignación maliciosa puede mejorarse en el sentido de Pareto moviendo el objeto o del agente i al agente j . Por lo tanto, la no malicia es una condición necesaria para fPO.

Una asignación es fPO si y solo si no es maliciosa, y su gráfico de consumo dirigido no es un ciclo dirigido en el que el producto de pesos es menor que 1. Esta equivalencia fue probada para bienes en el contexto del corte de torta 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, App.A}

Relación con el equilibrio del mercado

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]

Algoritmos

Decidir si una asignación determinada es fPO

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

• Calcular el gráfico de consumo dirigido de z ;
• Reemplace cada peso con su logaritmo;
• Utilice un algoritmo para encontrar un ciclo negativo, por ejemplo, el algoritmo Bellman-Ford .
• Con base en 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 un 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 hacer resolviendo un programa lineal . El tiempo de ejecución es débilmente polinomial.

Por el contrario, decidir si una asignación discreta dada es PO es co-NP-completo . ^[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 dominante

Encontrar una asignación de fPO es fácil. Por ejemplo, se puede encontrar utilizando la 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 ser 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 operaciones O( n ² m ² ( n + m )). Además, en la asignación calculada hay como máximo n -1 participaciones. ^{[6] : Lem.2.5, App.A}

Si la asignación inicial z es la 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 un máximo de 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 un máximo de n -1 participaciones.

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

Enumeración de las asignaciones de fPO

Hay 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 , 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 dos agentes, las razones de valores 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. ${\displaystyle O(3^{{\frac {(n-1)n}{2}}\cdot D}\cdot m^{{\frac {(n-1)n}{2}}+2})}$

Encontrar asignaciones justas y justas

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

• Barman y Krishnamurthy ^[11] demuestran que es posible calcular una asignación discreta de bienes fPO+PROP1 en tiempo fuertemente polinomial. Muestran un resultado similar para una asignación discreta fPO+EF11 , donde EF11 significa "libre de envidia hasta 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 domésticas). Utiliza un programa lineal que maximiza la suma de utilidades sujetas a proporcionalidad. Si se encuentra una solución factible básica (por ejemplo, utilizando el algoritmo simplex ), entonces el gráfico de consumo de la asignación resultante es acíclico. Alternativamente, es posible eliminar ciclos del gráfico 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 de bienes fPO+EF1 en tiempo pseudopolinomial. También demuestran que, cuando todos los valores son positivos, puede existir una asignación discreta fPO+EQ1 y 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 una 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 de bienes fPO+EFx y se puede calcular en tiempo polinomial. Esto refuerza los 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 diferentes (negativos), siempre existe una asignación discreta fPO+EF1 de tareas y se puede calcular en tiempo polinomial. También demuestran que, en este caso, se puede calcular una asignación fraccionaria fPO+EF de tareas (divisibles) 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 no haber una asignación discreta fPO+EQx ni una 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 diferentes agentes), cada agente i tiene una probabilidad igual de que w _i u _i sea mayor que el w _j u _j de todos los demás agentes. Muestran, 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 (en condiciones adecuadas en las distribuciones de utilidad), existe una asignación fPO+EF discreta.

Referencias

1. Barman, S., Krishnamurthy, SK, y Vaish, R., "Encontrar asignaciones justas y eficientes", EC '18: Actas de la Conferencia ACM de 2018 sobre economía y computación , junio de 2018.
2. Freeman, Rupert; Sikdar, Sujoy; Vaish, Rohit; Xia, Lirong (10 de agosto de 2019). "Asignaciones equitativas de bienes indivisibles". Actas de la 28.ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI'19. Macao, China: AAAI Press: 280–286. arXiv : 1905.10656 . ISBN 978-0-9992411-4-1.
3. Negishi, Takashi (1960-06-01). "Economía del bienestar y existencia de un equilibrio para una economía competitiva". Metroeconomica . 12 (2–3): 92–97. doi :10.1111/j.1467-999X.1960.tb00275.x. ISSN  0026-1386.
4. Varian, Hal R. (1 de abril de 1976). "Dos problemas en la teoría de la equidad". Revista de Economía Pública . 5 (3): 249–260. doi :10.1016/0047-2727(76)90018-9. hdl : 1721.1/64180 . ISSN  0047-2727.
5. Brânzei, Simina; Sandomirskiy, Fedor (3 de julio de 2019). "Algoritmos para la división competitiva de tareas". arXiv : 1907.01766 [cs.GT].
6. Sandomirskiy, Fedor; Segal-Halevi, Erel (1 de mayo de 2022). "División justa eficiente con mínima compartición". Investigación de operaciones . 70 (3): 1762–1782. arXiv : 1908.01669 . doi :10.1287/opre.2022.2279. ISSN  0030-364X. S2CID  247922344.
7. Barbanel, Julius B. (24 de enero de 2005). La geometría de la división justa y eficiente. Cambridge University Press. ISBN 978-1-139-44439-2.
8. Mas-Colell, Andreu (1995). "Teoría microeconómica". 1 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
9. de Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009). "Sobre la complejidad de la eficiencia y la ausencia de envidia en la división justa de bienes indivisibles con preferencias aditivas". En Rossi, Francesca; Tsoukias, Alexis (eds.). Teoría de la decisión algorítmica . Apuntes de clase en informática. Vol. 5783. Berlín, Heidelberg: Springer. págs. 98–110. doi :10.1007/978-3-642-04428-1_9. ISBN 978-3-642-04428-1.
10. Garg, Jugal; Murhekar, Aniket (2021). "Computación de asignaciones justas y eficientes con pocos valores de utilidad". En Caragiannis, Ioannis; Hansen, Kristoffer Arnsfelt (eds.). Teoría de juegos algorítmicos . Apuntes de clase en informática. Vol. 12885. Cham: Springer International Publishing. págs. 345–359. doi :10.1007/978-3-030-85947-3_23. ISBN 978-3-030-85947-3. Número de identificación del sujeto  237521642.
11. Barman, Siddharth; Krishnamurthy, Sanath Kumar (17 de julio de 2019). "Sobre la proximidad de los mercados con equilibrios integrales". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 33 (1): 1748–1755. arXiv : 1811.08673 . doi : 10.1609/aaai.v33i01.33011748 . ISSN  2374-3468. S2CID  53793188.
12. Aziz, Haris; Moulin, Hervé; Sandomirskiy, Fedor (1 de septiembre de 2020). "Un algoritmo de tiempo polinomial para calcular una asignación Pareto óptima y casi proporcional". Operations Research Letters . 48 (5): 573–578. arXiv : 1909.00740 . doi :10.1016/j.orl.2020.07.005. ISSN  0167-6377. S2CID  202541717.
13. Murhekar, Aniket; Garg, Jugal (18 de mayo de 2021). "Sobre asignaciones justas y eficientes de bienes indivisibles". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 35 (6): 5595–5602. arXiv : 2204.14229 . doi : 10.1609/aaai.v35i6.16703 . ISSN  2374-3468. S2CID  235306087.
14. Darmann, Andreas; Schauer, Joachim (1 de diciembre de 2015). "Maximización del bienestar social del producto de Nash en la asignación de bienes indivisibles". Revista Europea de Investigación Operativa . 247 (2): 548–559. doi :10.1016/j.ejor.2015.05.071. ISSN  0377-2217.
15. Barman, Siddharth; Krishnamurthy, Sanath Kumar; Vaish, Rohit (9 de julio de 2018). "Algoritmos voraces para maximizar el bienestar social de Nash". Actas de la 17.ª Conferencia internacional sobre agentes autónomos y sistemas multiagente . AAMAS '18. Richland, SC: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente: 7–13. arXiv : 1801.09046 .
16. Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A. (8 de abril de 2021). "El bienestar máximo de Nash y otras historias sobre EFX". Ciencias de la Computación Teórica . 863 : 69–85. arXiv : 2001.09838 . doi :10.1016/j.tcs.2021.02.020. ISSN  0304-3975. S2CID  232423008.
17. Garg, Jugal; Murhekar, Aniket; Qin, John (18 de octubre de 2021). "Asignaciones justas y eficientes de tareas en el marco de preferencias bivaluadas". arXiv : 2110.09601 [cs.GT].
18. Bai, Yushi; Gölz, Paul (11 de febrero de 2022). "Asignaciones libres de envidia y óptimas en el sentido de Pareto para agentes con valoraciones aleatorias asimétricas". arXiv : 2109.08971 [cs.GT].