Eficiencia ordinal de Pareto

La eficiencia ordinal de Pareto se refiere a varias adaptaciones del concepto de eficiencia de Pareto a situaciones en las que los agentes sólo expresan utilidades ordinales sobre los artículos, pero no sobre los paquetes. Es decir, los agentes clasifican los artículos de mejor a peor, pero no clasifican los subconjuntos de artículos. En particular, no especifican un valor numérico para cada artículo. Esto puede causar una ambigüedad con respecto a si ciertas asignaciones son eficientes en el sentido de Pareto o no. Como ejemplo, considere una economía con tres artículos y dos agentes, con las siguientes clasificaciones:

• Alicia: x > y > z.
• Jorge: x > z > y.

Consideremos la asignación [Alice: x, George: y, z]. Que esta asignación sea o no eficiente en términos de Pareto depende de las valoraciones numéricas de los agentes. Por ejemplo:

• Es posible que Alice prefiera {y,z} a {x} y George prefiera {x} a {y,z} (por ejemplo: las valoraciones de Alice para x,y,z son 8,7,6 y las de George son 7,1,2, por lo que el perfil de utilidad es 8,3). En ese caso, la asignación no es eficiente en términos de Pareto, ya que tanto Alice como George estarían en mejor situación si intercambiaran sus cestas (el perfil de utilidad sería 13,7).
• Por el contrario, es posible que Alice prefiera {x} a {y, z} y George prefiera {y, z} a {x} (por ejemplo: las valoraciones de Alice son 12, 4, 2 y las de George son 6, 3, 4). Entonces la asignación es eficiente en términos de Pareto: en cualquier otra asignación, si Alice sigue recibiendo x, entonces la utilidad de George es menor; si Alice no recibe x, entonces la utilidad de Alice es menor. Además, la asignación es eficiente en términos de Pareto incluso si los artículos son divisibles (es decir, es fraccionalmente eficiente en términos de Pareto ): si Alice le da cualquier cantidad r de x a George, entonces George tendría que darle al menos 3 r de y o 6 r de z para mantener su utilidad en el mismo nivel. Pero entonces la utilidad de George cambiaría en 6 r -9 r o 6 r -24 r , lo cual es negativo.

Dado que la eficiencia de Pareto de una asignación depende de las clasificaciones de los paquetes, a priori no está claro cómo determinar la eficiencia de una asignación cuando solo se dan las clasificaciones de los artículos.

Definiciones

Una asignación X = (X ₁ ,...,X _n ) domina en el sentido de Pareto a otra asignación Y = (Y ₁ ,...,Y _n ), si cada agente i prefiere débilmente el conjunto X _i al conjunto Y _i , y al menos un agente j prefiere estrictamente X _j a Y _j . Una asignación X es eficiente en el sentido de Pareto si ninguna otra asignación la domina en el sentido de Pareto. A veces, se hace una distinción entre eficiencia discreta en el sentido de Pareto , que significa que una asignación no está dominada por una asignación discreta, y el concepto más fuerte de eficiencia fraccionaria en el sentido de Pareto , que significa que una asignación no está dominada ni siquiera por una asignación fraccionaria.

Las definiciones anteriores dependen de la clasificación de los paquetes (conjuntos de elementos) de los agentes. En nuestro contexto, los agentes informan solo sus clasificaciones de elementos . Una clasificación de paquetes se denomina coherente con una clasificación de elementos si clasifica los paquetes singleton en el mismo orden que los elementos que contienen. Por ejemplo, si la clasificación de Alice es w < x < y < z , entonces cualquier clasificación de paquetes coherente debe tener {w} < {x} < {y} < {z]. A menudo, se hacen suposiciones adicionales sobre el conjunto de clasificaciones de paquetes permitidas, lo que impone restricciones adicionales a la coherencia. Algunos ejemplos de suposiciones son:

• Monotonía: agregar un elemento a un conjunto siempre mejora el conjunto. Esto corresponde al supuesto de que todos los elementos son buenos . Por lo tanto, la clasificación de conjuntos de Alice debe tener, por ejemplo, {y} < {y,x}.
• Capacidad de respuesta : reemplazar un artículo por uno mejor siempre mejora el conjunto. Por lo tanto, la clasificación del conjunto de Alice debe ser, por ejemplo, {w,x} < {w,y} < {x,y} < {x,z}. Esto es más fuerte que la consistencia.
• Aditividad : el agente asigna un valor a cada elemento y valora cada paquete según la suma de sus contenidos. Este supuesto es más sólido que el de responsividad. Por ejemplo, si Alice clasifica {x,y}<{z}, entonces debe clasificar {w,x,y}<{w,z}.
• Lexicográfico : el agente siempre clasifica un conjunto que contiene algún elemento x por encima de cualquier conjunto que contenga solo elementos clasificados por debajo de x. En el ejemplo anterior, Alice debe clasificar {w,x,y} < {z}.

Eficiencia de Pareto necesaria

Brams, Edelman y Fishburn ^{[1] : 9} llaman a una asignación Pareto-aseguradora si es Pareto-eficiente para todas las clasificaciones de paquetes que son consistentes con las clasificaciones de elementos de los agentes (permiten todas las clasificaciones de paquetes monótonas y reactivas ). Por ejemplo:

• Si se supone que las valoraciones de los agentes son positivas, entonces cada asignación que otorga todos los artículos a un solo agente garantiza el efecto de Pareto.
• Si la clasificación de Alice es x>y y la clasificación de George es y>x, entonces la asignación [Alice:x, George:y] asegura el sentido de Pareto.
• Si la clasificación de Alice es x>y>z y la clasificación de George es x>z>y y las asignaciones deben ser discretas, entonces la asignación [Alice: x,y; George: z] asegura el sentido de Pareto. ^{[1] : 5  [ aclaración necesaria ]}
• Con las clasificaciones anteriores, la asignación [Alice: x, George: y, z] no garantiza el equilibrio de Pareto. Como se explicó en la introducción, no es eficiente en términos de Pareto, por ejemplo, cuando las valoraciones de Alice para x, y, z son 8, 7, 6 y las de George son 7, 1, 2. Nótese que ambas valoraciones son coherentes con las clasificaciones de los agentes.

Bouveret, Endriss y Lang ^{[2] : 3} utilizan una definición equivalente. Dicen que una asignación X posiblemente domina en el sentido de Pareto a una asignación Y si existen algunas clasificaciones de paquetes consistentes con las clasificaciones de elementos de los agentes, para las cuales X domina en el sentido de Pareto a Y. Una asignación se denomina necesariamente eficiente en el sentido de Pareto (NecPE) si ninguna otra asignación posiblemente la domina en el sentido de Pareto.

Las dos definiciones son lógicamente equivalentes:

• "X es Pareto-asegurador" es equivalente a "Para cada clasificación de paquetes consistente, para cada otra asignación Y, Y no domina Pareto sobre X".
• "X es NecPE" es equivalente a "Para cada otra asignación Y, para cada clasificación de paquete consistente, Y no domina en el sentido de Pareto a X". Intercambiar el orden de los cuantificadores "para todos" no cambia el significado lógico.

La condición NecPE sigue siendo la misma ya sea que permitamos todas las clasificaciones de paquetes aditivos o que solo permitamos clasificaciones que se basen en valoraciones aditivas con diferencias decrecientes. ^{[3] : Sec.8}

Existencia

NecPE es un requisito muy estricto que, a menudo, no se puede satisfacer. Por ejemplo, supongamos que dos agentes tienen la misma clasificación de ítems. Uno de ellos, digamos Alice, necesariamente recibe el ítem con la clasificación más baja. Existen clasificaciones aditivas consistentes en las que Alice valora este ítem en 0 mientras que George lo valora en 1. Por lo tanto, dárselo a Alice no es Pareto-eficiente.

Si requerimos que todos los ítems tengan un valor estrictamente positivo, entonces dar todos los ítems a un solo agente es trivialmente NecPE, pero muy injusto. Si se permiten asignaciones fraccionarias, entonces puede que no haya una asignación NecPE que dé a ambos agentes un valor positivo. Por ejemplo, supongamos que Alice y George tienen ambos la clasificación x>y. Si ambos obtienen un valor positivo, entonces Alice obtiene algo de x y George obtiene algo de y, o viceversa. En el primer caso, es posible que las valoraciones de Alice sean, por ejemplo, 4,2 y las valoraciones de George sean 8,1, por lo que Alice puede intercambiar una pequeña cantidad r de x por una pequeña cantidad 3 r de y. Alice gana 6 r -4 r y George gana 8 r -3 r , por lo que ambas ganancias son positivas. En el último caso, se sostiene un argumento análogo.

Posible eficiencia de Pareto

Brams, Edelman y Fishburn ^{[1] : 9} Llamamos a una asignación Pareto-posible si es Pareto-eficiente para algunas clasificaciones de paquetes que son consistentes con las clasificaciones de elementos de los agentes. Obviamente, toda asignación que garantice Pareto es Pareto-posible. Además:

• Si la clasificación de Alice es x>y>z y la de George es x>z>y, entonces la asignación [Alicia: x, George: y,z] es Pareto-posible. Como se explicó en la introducción, es Pareto-eficiente, por ejemplo, cuando las valoraciones de Alice para x,y,z son 12,4,2 y las de George son 6,3,4. Nótese que ambas valoraciones son consistentes con las clasificaciones de los agentes.
• Si la clasificación de Alice es x>y y la clasificación de George es y>x, entonces la asignación [Alice:y, George:x] no es Pareto-posible, ya que siempre está Pareto-dominada por la asignación [Alice:x, George:y].

Bouveret, Endriss y Lang ^{[2] : 3} utilizan una definición diferente. Dicen que una asignación X necesariamente domina en el sentido de Pareto a una asignación Y si, para todas las clasificaciones de paquetes consistentes con las clasificaciones de elementos de los agentes, X domina en el sentido de Pareto a Y. Una asignación se denomina Posiblemente Pareto-eficiente (PosPE) si ninguna otra asignación la domina necesariamente en el sentido de Pareto.

Las dos definiciones no son lógicamente equivalentes:

• "X es Pareto-posible" es equivalente a "Existe una clasificación de conjunto consistente para la cual, para cada otra asignación Y, Y no domina a X". Debe ser la misma clasificación de conjunto para todas las demás asignaciones Y.
• "X es PosPE" es equivalente a "Para cada otra asignación Y, existe una clasificación de paquete consistente, para la cual Y no domina a X". Puede haber una clasificación de paquete diferente para cada otra asignación Y.

Si X es Pareto-posible entonces es PosPE, pero la otra implicación no es (lógicamente) verdadera. ^{[ aclaración necesaria ]}

La condición de Pareto posible sigue siendo la misma tanto si permitimos todas las clasificaciones de paquetes aditivos como si permitimos sólo clasificaciones que se basan en valoraciones aditivas con diferencias decrecientes . ^{[3] : Sec.8}

Dominancia estocástica Eficiencia de Pareto

Bogomolnaia y Moulin ^{[4] : ​​302–303} presentan una noción de eficiencia para el establecimiento de una asignación aleatoria justa (donde las clasificaciones de los paquetes son aditivas , las asignaciones son fraccionarias y la suma de las fracciones otorgadas a cada agente debe ser como máximo 1 ). Se basa en la noción de dominancia estocástica .

Para cada agente i , un paquete X _i domina estocásticamente débilmente (wsd) a un paquete Y _i si para cada artículo z, la fracción total de artículos mejores que z en X _i es al menos tan grande como en Y _i (si las asignaciones son discretas, entonces X _i sd Y _i significa que para cada artículo z, la cantidad de artículos mejores que z en X _i es al menos tan grande como en Y _i ). La relación sd tiene varias definiciones equivalentes; consulte extensión de conjunto responsivo . En particular, X _i sd Y _i si y solo si, para cada clasificación de paquete consistente con la clasificación de artículo, X _i es al menos tan bueno como Y _i . ^[5] Un paquete X _i domina estocásticamente estricto (ssd) a un paquete Y _i si X _i wsd Y _i y X _i ≠ Y _i . De manera equivalente, para al menos un artículo z, el "al menos tan grande como en Y _i " se convierte en "estrictamente mayor que en Y _i ". En ^[1] la relación ssd se escribe como "X _i >> Y _i ".

Una asignación X = (X ₁ ,...,X _n ) domina estocásticamente a otra asignación Y = (Y ₁ ,...,Y _n ), si para cada agente i : X _i wsd Y _i , e Y≠X (equivalentemente: para al menos un agente i, X _i ssd Y _i ). En ^[1] la relación de dominación estocástica entre asignaciones también se escribe como "X >> Y". Esto es equivalente a la dominación de Pareto necesaria.

Una asignación se denomina sd-eficiente ^[6] (también llamada: ordinalmente eficiente u O-eficiente ) ^[4] si no hay una asignación que la domine estocásticamente. Esto es similar a PosPE, pero enfatiza que las clasificaciones de los paquetes deben basarse en funciones de utilidad aditivas y las asignaciones pueden ser fraccionarias .

Equivalencias

Como se señaló anteriormente, Pareto-posible implica PosPE, pero la otra dirección no es lógicamente verdadera. McLennan ^[7] demuestra que son equivalentes en el problema de asignación aleatoria justa (con clasificaciones de elementos estrictas o débiles). En particular, demuestra que los siguientes son equivalentes:

• (a) X es sd-eficiente (es decir, X es PosPE);
• (b) existen clasificaciones aditivas de paquetes consistentes con las clasificaciones de ítems de los agentes para las cuales X es fraccionalmente Pareto-eficiente (es decir, X es Pareto-posible);
• (c) existen clasificaciones aditivas de paquetes consistentes con las clasificaciones de artículos de los agentes para las cuales X maximiza la suma de las utilidades de los agentes.

Las implicaciones (c) → (b) → (a) son fáciles; la parte difícil es demostrar que (a) → (c). McLennan lo demuestra utilizando el teorema del hiperplano separador poliédrico . ^[7]

Bogomolnaia y Moulin ^{[4] : La lección 3} prueba otra caracterización útil de la eficiencia sd, para el mismo entorno de asignación aleatoria justa pero con clasificaciones estrictas de los ítems. Defina el gráfico de intercambio de una asignación fraccionaria dada como un gráfico dirigido en el que los nodos son los ítems, y hay un arco x→y si y solo si existe un agente i que prefiere x y recibe una fracción positiva de y. Defina una asignación como acíclica si su gráfico de intercambio no tiene ciclos dirigidos. Entonces, una asignación es sd-eficiente si y solo si es acíclica.

Fishburn demostró la siguiente equivalencia en las relaciones de dominancia de paquetes discretos , con clasificaciones de paquetes sensibles : ^{[8] [1] : Lem.2.1}

• Si X _i >> Y _i (es decir: X _i ≠ Y _i , y para cada elemento z, X _i tiene al menos tantos elementos que son al menos tan buenos como z), entonces, para cada clasificación de paquete responsiva consistente con la clasificación de elementos, X _i > Y _i .
• Si no X _i >> Y _i , entonces existe al menos una clasificación de paquete responsiva consistente con la clasificación de ítems, para la cual X _i < Y _i .

Por lo tanto, lo siguiente se cumple para las relaciones de dominancia de asignaciones discretas: X >> Y sólo si X necesariamente domina en el sentido de Pareto a Y. ^{[1] : 8}

Propiedades

Si X _i wsd Y _i , entonces |X _i | ≥ |Y _i | , es decir, la cantidad total de objetos (discretos o fraccionarios) en X _i debe ser al menos tan grande como en Y _i . Esto se debe a que, si |X _i | < |Y _i | , entonces para la valoración que asigna casi el mismo valor para todos los elementos, v( X _i ) < v( Y _i ).

Esto significa que, si X wsd Y y tanto X como Y son asignaciones completas (todos los objetos están asignados), entonces necesariamente |X _i | = |Y _i | para todos los agentes i . ^{[1] : Lem.2.2} En otras palabras, una asignación completa X puede ser necesariamente dominada solo por una asignación Y que asigna a cada agente la misma cantidad que X.

Esto significa que, en particular, si X es sd-eficiente en el conjunto de todas las asignaciones que dan exactamente 1 unidad a cada agente, entonces X es sd-eficiente en general.

Dominancia lexicográfica Eficiencia de Pareto

Cho presenta otras dos nociones de eficiencia para el establecimiento de una asignación aleatoria justa , basada en el dominio lexicográfico .

Una asignación X = (X ₁ ,...,X _n ) domina lexicográficamente hacia abajo (dl) a otra asignación Y = (Y ₁ ,...,Y _n ), si para cada agente i, X _i domina débilmente-dl-a Y _i , y para al menos un agente j , X _j domina estrictamente-dl-a Y _j . Una asignación se denomina dl-eficiente si no hay otra asignación que la domine dl.

De manera similar, con base en la noción de dominación lexicográfica ascendente (ul) , una asignación se denomina ul-eficiente si no hay otra asignación que la domine ul.

En general, la dominación sd implica la dominación dl y la dominación ul. Por lo tanto, la eficiencia dl y la eficiencia ul implican la eficiencia sd.

Equivalencias

Consideremos el escenario de asignación aleatoria justa (las clasificaciones de los paquetes son aditivas , las asignaciones pueden ser fraccionarias y la fracción total otorgada a cada agente debe ser 1), con clasificaciones estrictas de elementos, donde puede haber más elementos que agentes (por lo que algunos elementos pueden permanecer sin asignar). Cho y Dogan ^[6] prueban que, en este caso particular, la eficiencia dl y la eficiencia ul son equivalentes a la eficiencia sd. En particular, prueban que si una asignación X es eficiente sd/ld/ul, entonces:

• El gráfico de intercambio de X es acíclico, y -
• X no es derrochador ("derrochador" significa que algún agente i , que recibe una fracción positiva de un artículo x , prefiere otro artículo y que no está completamente asignado).

La equivalencia no se cumple si hay restricciones distribucionales: hay asignaciones que son sd-eficientes pero no dl-eficientes. ^{[9] : Ejemplo 4}

Lectura adicional

• Aziz, Gaspers, Mackenzie y Walsh ^[10] estudian cuestiones computacionales relacionadas con nociones de equidad ordinal. En la Sección 7 estudian brevemente la eficiencia sd-Pareto.
• Dogan, Dogan y Yildiz ^[11] estudian una relación de dominación diferente entre asignaciones: una asignación X domina una asignación Y si es Pareto-eficiente para un conjunto más grande de clasificaciones de paquetes consistentes con las clasificaciones de los ítems.
• Abdulkadiroğlu y Sönmez ^[12] investigan la relación entre la eficiencia sd y la eficiencia Pareto ex post (en el contexto de la asignación aleatoria). Introducen una nueva noción de dominación para conjuntos de asignaciones y demuestran que una lotería es eficiente sd si y solo si cada subconjunto del soporte de la lotería no está dominado.

Referencias

1. Brams, Steven J.; Edelman, Paul H.; Fishburn, Peter C. (1 de septiembre de 2003). "División justa de elementos indivisibles". Teoría y decisión . 55 (2): 147–180. doi :10.1023/B:THEO.0000024421.85722.0a. ISSN  1573-7187. S2CID  153943630.
2. Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (4 de agosto de 2010). "División justa bajo preferencias ordinales: cálculo de asignaciones libres de envidia de bienes indivisibles". Actas de la Conferencia de 2010 sobre ECAI 2010: 19.ª Conferencia Europea sobre Inteligencia Artificial . NLD: IOS Press: 387–392. ISBN 978-1-60750-605-8.
3. Segal-Halevi, Erel; Hassidim, Avinatan; Aziz, Haris (10 de marzo de 2020). "Asignación justa con diferencias decrecientes". Revista de investigación en inteligencia artificial . 67 : 471–507–471–507. arXiv : 1705.07993 . doi : 10.1613/jair.1.11994 . ISSN  1076-9757. S2CID  108290839.
4. Bogomolnaia, Anna; Moulin, Hervé (1 de octubre de 2001). "Una nueva solución al problema de asignación aleatoria". Journal of Economic Theory . 100 (2): 295–328. doi :10.1006/jeth.2000.2710. ISSN  0022-0531.
5. Katta, Akshay-Kumar; Sethuraman, Jay (2006). "Una solución al problema de asignación aleatoria en el dominio de preferencia completo". Journal of Economic Theory . 131 (1): 231. doi :10.1016/j.jet.2005.05.001.
6. Cho, Wonki Jo; Doğan, Battal (1 de septiembre de 2016). "Equivalencia de nociones de eficiencia para problemas de asignación ordinal". Economics Letters . 146 : 8–12. doi :10.1016/j.econlet.2016.07.007. ISSN  0165-1765.
7. McLennan, Andrew (1 de agosto de 2002). "Eficiencia ordinal y teorema del hiperplano separador poliédrico". Journal of Economic Theory . 105 (2): 435–449. doi :10.1006/jeth.2001.2864. ISSN  0022-0531.
8. Fishburn, Peter C. (1 de marzo de 1996). "Probabilidad cualitativa lineal finita". Revista de psicología matemática . 40 (1): 64–77. doi :10.1006/jmps.1996.0004. ISSN  0022-2496.
9. Aziz, Haris; Brandl, Florian (1 de septiembre de 2022). "La regla de la alimentación vigilante: un enfoque general para el diseño económico probabilístico con restricciones". Juegos y comportamiento económico . 135 : 168–187. arXiv : 2008.08991 . doi :10.1016/j.geb.2022.06.002. ISSN  0899-8256. S2CID  221186811.
10. Aziz, Haris; Gaspers, Serge; Mackenzie, Simon; Walsh, Toby (1 de octubre de 2015). "Asignación justa de objetos indivisibles bajo preferencias ordinales". Inteligencia artificial . 227 : 71–92. arXiv : 1312.6546 . doi : 10.1016/j.artint.2015.06.002 . ISSN  0004-3702. S2CID  1408197.
11. Doğan, Battal; Doğan, Serhat; Yıldız, Kemal (1 de mayo de 2018). "Un nuevo criterio de eficiencia ex ante e implicaciones para el mecanismo serial probabilístico". Revista de teoría económica . 175 : 178–200. doi :10.1016/j.jet.2018.01.011. hdl : 11693/48988 . ISSN  0022-0531.
12. Abdulkadiroğlu, Atila; Sönmez, Tayfun (1 de septiembre de 2003). "Eficiencia ordinal y conjuntos dominados de asignaciones". Revista de teoría económica . 112 (1): 157–172. doi :10.1016/S0022-0531(03)00091-7. hdl : 10161/1940 . ISSN  0022-0531.