Eficiencia ordinal de Pareto

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

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

Considere la asignación [Alice: x, George: y,z]. Que esta asignación sea o no eficiente en el sentido 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 valoraciones de George son 7 ,1,2, por lo que el perfil de utilidad es 8,3). Entonces la asignación no es eficiente en el sentido de Pareto, ya que tanto Alice como George estarían mejor 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 valoraciones de George son 6,3, 4). Entonces la asignación es eficiente en el sentido de Pareto: en cualquier otra asignación, si Alice todavía obtiene x, entonces la utilidad de George es menor; Si Alice no obtiene x, entonces la utilidad de Alice es menor. Además, la asignación es eficiente en el sentido de Pareto incluso si los elementos son divisibles (es decir, es eficiente en el sentido de Pareto fraccionariamente ): 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 al 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 las cestas, a priori no está claro cómo determinar la eficiencia de una asignación cuando sólo se dan clasificaciones de artículos.

Definiciones

Una asignación X = (X ₁ ,...,X _n ) domina en sentido de Pareto otra asignación Y = (Y ₁ ,...,Y _n ), si cada agente i prefiere débilmente el paquete X _i al paquete 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. A veces, se hace una distinción entre eficiencia de Pareto discreta , que significa que una asignación no está dominada por una asignación discreta, y el concepto más fuerte de eficiencia de Pareto fraccionaria , 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 paquetes (conjuntos de artículos) de los agentes. En nuestro entorno, los agentes informan únicamente sus clasificaciones de artículos . Una clasificación de paquete se considera coherente con una clasificación de artículo si clasifica los paquetes únicos en el mismo orden que los artículos que contienen. Por ejemplo, si la clasificación de Alice es w < x < y < z , entonces cualquier clasificación de paquete consistente 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. Los supuestos de ejemplo son:

• Monotonicidad: agregar un artículo a un paquete siempre mejora el paquete. Esto corresponde al supuesto de que todos los artículos son buenos . Por lo tanto, la clasificación del paquete de Alice debe tener, por ejemplo, {y} < {y,x}.
• Capacidad de respuesta : reemplazar un artículo por uno mejor siempre mejora el paquete. Por lo tanto, la clasificación del paquete de Alice debe tener, por ejemplo, {w,x} < {w,y} < {x,y} < {x,z}. Esto es más fuerte que la coherencia.
• Aditividad : el agente asigna un valor a cada artículo y valora cada paquete por la suma de su contenido. Esta suposición es más fuerte que la capacidad de respuesta. Por ejemplo, si Alice ocupa el puesto {x,y}<{z}, entonces debe clasificar {w,x,y}<{w,z}.
• Lexicográfico : el agente siempre clasifica un paquete que contiene algún elemento x por encima de cualquier paquete que contenga solo elementos clasificados por debajo de x. En el ejemplo anterior, Alice debe clasificar {w,x,y} < {z}.

Necesaria eficiencia de Pareto

Brams, Edelman y Fishburn ^{[1] : 9} llaman a una asignación que garantiza Pareto 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ótonos y responsivos ). Por ejemplo:

• Si se supone que las valoraciones de los agentes son positivas, entonces cada asignación que entregue todos los artículos a un solo agente garantiza 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] garantiza 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] garantiza Pareto. ^{[1] : 5  [ se necesita aclaración ]}
• Con las clasificaciones anteriores, la asignación [Alice: x, George: y,z] no garantiza Pareto. Como se explicó en la introducción, no es eficiente en el sentido de Pareto, por ejemplo, cuando las valoraciones de Alice para x,y,z son 8,7,6 y las valoraciones de George son 7,1,2. Tenga en cuenta que ambas valoraciones son consistentes 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 sentido de Pareto 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 sentido de Pareto a Y. Una asignación se llama Necesariamente Pareto-eficiente (NecPE) si no hay otra la asignación posiblemente la domine Pareto.

Las dos definiciones son lógicamente equivalentes:

• "X garantiza Pareto" es equivalente a "Para cada clasificación de paquete consistente, para cada otra asignación Y, Y no domina a X en Pareto".
• "X es NecPE" es equivalente a "Para cualquier otra asignación Y, para cada clasificación de paquete consistente, Y no domina a X en el sentido de Pareto". Cambiar 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 solo permitimos clasificaciones que se basan en valoraciones aditivas con diferencias decrecientes. ^{[3] : Sección 8}

Existencia

NecPE es un requisito muy importante que a menudo no se puede cumplir. Por ejemplo, supongamos que dos agentes tienen la misma clasificación de elementos. Uno de ellos, digamos Alice, necesariamente recibe el artículo con la clasificación más baja. Hay clasificaciones de paquetes aditivos consistentes en las que Alices valora este elemento en 0 mientras que George lo valora en 1. Por lo tanto, dárselo a Alice no es eficiente en el sentido de Pareto.

Si requerimos que todos los elementos tengan un valor estrictamente positivo, entonces entregar todos los elementos a un solo agente es trivialmente NecPE, pero es muy injusto. Si se permiten asignaciones fraccionarias, es posible que no haya una asignación NecPE que otorgue a ambos agentes un valor positivo. Por ejemplo, supongamos que Alice y George tienen la clasificación x>y. Si ambos obtienen un valor positivo, entonces Alice obtiene algo de x y George 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} consideran que una asignación es 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 clasificación de George es x>z>y, entonces la asignación [Alice: x, George: y,z] es Pareto-posible. Como se explicó en la introducción, es eficiente en el sentido de Pareto, por ejemplo, cuando las valoraciones de Alice para x,y,z son 12,4,2 y las valoraciones de George son 6,3,4. Tenga en cuenta 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á dominada por Pareto 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 sentido de Pareto una asignación Y si para todas las clasificaciones de paquetes consistentes con las clasificaciones de elementos de los agentes, X domina en sentido de Pareto a Y. Una asignación se llama Posiblemente eficiente en términos de Pareto (PosPE) si no hay otra asignación necesariamente. Pareto lo domina.

Las dos definiciones no son lógicamente equivalentes:

• "X es Pareto posible" equivale a "Existe una clasificación de paquetes consistente para la cual, para cualquier otra asignación Y, Y no domina a X". Debe tener la misma clasificación de paquete para todas las demás asignaciones Y.
• "X es PosPE" equivale 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) cierta. ^{[ se necesita aclaración ]}

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

Eficiencia de Pareto con dominancia estocástica

Bogomolnaia y Moulin ^{[4] : ​​302–303} presentan una noción de eficiencia para establecer una asignación aleatoria justa (donde las clasificaciones de los paquetes son aditivas , las asignaciones son fraccionarias y la suma de las fracciones dadas 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 Xi domina débilmente estocásticamente (wsd) 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 discretos, entonces X _i sd Y _i significa que para cada elemento z, el número de elementos mejores que z en X _i es al menos tan grande como en Y _i ). La relación sd tiene varias definiciones equivalentes; ver extensión de conjunto responsivo . En particular, X _i sd Y _i si, y sólo si, para cada clasificación de paquete consistente con la clasificación de artículo, Xi _es al menos tan buena como Y _i . ^[5] Un paquete X _i domina de manera estrictamente estocástica (ssd) un paquete Y _i si X _i wsd Y _i y X _i ≠ Y _i . De manera equivalente, para al menos un elemento z, "al menos tan grande como en Y _i " se vuelve "estrictamente más grande 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 otra asignación Y = (Y ₁ ,...,Y _n ), si para cada agente i : X _i wsd Y _i , e Y≠X ( de manera equivalente: 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 equivale a la necesaria dominación de Pareto.

Una asignación se llama 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 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 cierta. McLennan ^[7] demuestra que son equivalentes en el problema de asignación aleatoria justa (con clasificaciones de ítems estrictas o débiles). En particular, demuestra que son equivalentes:

• (a) X es eficiente en sd (es decir, X es PosPE);
• (b) existen clasificaciones de paquetes aditivos consistentes con las clasificaciones de elementos de los agentes para las cuales X es fraccionariamente eficiente en términos de Pareto (es decir, X es Pareto posible);
• (c) existen clasificaciones de paquetes aditivos consistentes con las clasificaciones de elementos 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 desafiante es demostrar que (a) → (c). McLennan lo demuestra utilizando el teorema del hiperplano de separación poliédrica . ^[7]

Bogomolnaia y Moulin ^{[4] : ​​Lem.3} demuestra otra caracterización útil de la eficiencia sd, para el mismo entorno de asignación aleatoria justa pero con clasificaciones estrictas de elementos. Defina el gráfico de intercambio de una asignación fraccionaria dada como un gráfico dirigido en el que los nodos son los elementos, y hay un arco x→y 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 sd-eficiente 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 artículo z, Xi tiene al menos tantos artículos que sean al menos tan buenos como z), entonces, para cada clasificación de paquete responsivo 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 artículos, para la cual _Xi < Y _i .

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

Propiedades

Si X _i wsd Y _i , entonces |X _i | ≥ |Y _yo | , 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 _yo | , entonces para la valoración que asigna casi el mismo valor a todos los artículos, 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 _yo | para todos los agentes i . ^{[1] : Lem.2.2} En otras palabras, una asignación completa X puede estar necesariamente dominada sólo por una asignación Y que asigna a cada agente la misma cantidad que X.

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

Dominio lexicográfico Eficiencia de Pareto

Cho presenta otras dos nociones de eficiencia para establecer una asignación aleatoria justa , basadas en la dominancia lexicográfica .

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

De manera similar, basándose 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, sd-dominación implica dl-dominación y ul-dominación. Por lo tanto, la eficiencia dl y la eficiencia ul implican eficiencia sd.

Equivalencias

Considere la configuración de asignación aleatoria justa (las clasificaciones de los paquetes son aditivas , las asignaciones pueden ser fraccionarias y la fracción total dada 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 permanecen sin asignar). Cho y Dogan ^[6] demuestran que, en este caso particular, la eficiencia dl y la eficiencia ul son equivalentes a la eficiencia sd. En particular, demuestran que si una asignación X es eficiente sd/ld/ul, entonces:

• La gráfica de intercambio de X es acíclica y -
• X no es un desperdicio ("despilfarro" 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 existen restricciones distributivas: hay asignaciones que son eficientes en sd pero no eficientes en dl. ^{[9] : Ejemplo 4}

Lectura adicional

• Aziz, Gaspers, Mackenzie y Walsh ^[10] estudian cuestiones computacionales relacionadas con las 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 ítems.
• Abdulkadiroğlu y Sönmez ^[12] investigan la relación entre la eficiencia sd y la eficiencia de Pareto ex post (en el contexto de la asignación aleatoria). Introducen una nueva noción de dominación para conjuntos de asignaciones y muestran que una lotería es eficiente en sd si cada subconjunto del apoyo 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 Artículos 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 según preferencias ordinales: cálculo de asignaciones de bienes indivisibles sin envidia". Actas de la Conferencia de 2010 sobre ECAI 2010: XIX Conferencia Europea sobre Inteligencia Artificial . NLD: IOS Press: 387–392. ISBN 978-1-60750-605-8.
3. Segal-Halevi, Erel; Jasidim, 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. , Anna; Moulin, Hervé (1 de octubre de 2001). "Una nueva solución al problema de la asignación aleatoria". Revista de teoría económica . 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". Revista de teoría económica . 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". Cartas de Economía . 146 : 8-12. doi :10.1016/j.econlet.2016.07.007. ISSN  0165-1765.
7. McLennan, Andrew (1 de agosto de 2002). "La eficiencia ordinal y el teorema del hiperplano de separación poliédrica". Revista de teoría económica . 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, Simón; Walsh, Toby (1 de octubre de 2015). "Asignación justa de objetos indivisibles según 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, batalla; Doğan, Serhat; Yıldız, Kemal (1 de mayo de 2018). "Un nuevo criterio de eficiencia ex ante e implicaciones para el mecanismo probabilístico en serie". 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 de tareas dominados". Revista de teoría económica . 112 (1): 157-172. doi :10.1016/S0022-0531(03)00091-7. hdl : 10161/1940 . ISSN  0022-0531.