Articulo de referencia

eficiencia de Pareto ordinal

La eficiencia de Pareto ordinal se refiere a diversas adaptaciones del concepto de eficiencia de Pareto a entornos en los que los agentes solo expresan utilidades ordinales sobr...

La eficiencia de Pareto ordinal se refiere a diversas adaptaciones del concepto de eficiencia de Pareto a entornos en los que los agentes solo expresan utilidades ordinales sobre los artículos, pero no sobre los conjuntos. 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 generar ambigüedad respecto a si ciertas asignaciones son eficientes en el sentido de Pareto o no. Como ejemplo, consideremos una economía con tres artículos y dos agentes, con las siguientes clasificaciones:

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

Consideremos la asignación [Alice: x, George: y,z]. Que esta asignación sea o no Pareto-eficiente 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 Pareto-eficiente, ya que tanto Alice como George estarían mejor intercambiando 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 Pareto-eficiente: en cualquier otra asignación, si Alice sigue obteniendo 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 Pareto-eficiente incluso si los elementos son divisibles (es decir, es Pareto-eficiente fraccional ): si Alice entrega 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 la clasificación de los conjuntos, a priori no está claro cómo determinar la eficiencia de una asignación cuando solo se conocen las clasificaciones de los artículos.

Definiciones

Una asignación X = (X 1 ,...,X n ) domina en el sentido de Pareto a otra asignación Y = (Y 1 ,...,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 Pareto-eficiente si ninguna otra asignación la domina en el sentido de Pareto. A veces, se hace una distinción entre la 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 los grupos (conjuntos de elementos) que realizan los agentes. En nuestro caso, los agentes informan únicamente de sus clasificaciones de elementos . Una clasificación de grupos se considera coherente con una clasificación de elementos si clasifica los grupos de un solo elemento 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 grupos coherente debe cumplir {w} < {x} < {y} < {z}. A menudo, se hacen suposiciones adicionales sobre el conjunto de clasificaciones de grupos permitidas, lo que impone restricciones adicionales a la coherencia. Algunos ejemplos de suposiciones son:

  • Monotonicidad: 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 elemento por uno mejor siempre mejora el conjunto. Por lo tanto, la clasificación del conjunto de Alice debe cumplir, por ejemplo, {w,x} < {w,y} < {x,y} < {x,z}. Esto es más importante que la consistencia.
  • Aditividad : el agente asigna un valor a cada elemento y valora cada conjunto como la suma de sus contenidos. Esta suposición es más fuerte que la de capacidad de respuesta. 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 contiene 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 denominan a una asignación Pareto-aseguradora si es Pareto-eficiente para todas las clasificaciones de paquetes que sean consistentes con las clasificaciones de elementos de los agentes (permiten todas las clasificaciones de paquetes monótonas y responsivas ). Por ejemplo:

  • Si se supone que las valoraciones de los agentes son positivas, entonces cualquier asignación que dé todos los artículos a un solo agente garantiza la solución 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] garantiza la simetría de Pareto.
  • Si la clasificación de Alice es x>y>z y la de George es x>z>y, y las asignaciones deben ser discretas, entonces la asignación [Alice: x,y; George: z] garantiza la solución de Pareto. [ 1 ] : 5
  • Con las clasificaciones anteriores, la asignación [Alice: x, George: y,z] no garantiza la simetría de 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 de George son 7, 1, 2. Cabe destacar que ambas valoraciones son consistentes con las clasificaciones de los agentes.

Bouveret, Endriss y Lang. [ 2 ] : 3 utilizan una definición equivalente. Afirman que una asignación X posiblemente domina en el sentido de Pareto a una asignación Y si existe alguna clasificación de paquetes consistente con las clasificaciones de los elementos de los agentes, para la cual X domina en el sentido de Pareto a Y. Una asignación se denomina Necesariamente Pareto-eficiente (NecPE) si ninguna otra asignación posiblemente la domina en el sentido de Pareto.

Las dos definiciones son lógicamente equivalentes:

  • "X garantiza el criterio de Pareto" es equivalente a "Para cada clasificación de paquetes consistente, para cualquier otra asignación Y, Y no domina a X en el sentido de Pareto".
  • "X es NecPE" es equivalente a "Para cualquier otra asignación Y, para cualquier clasificación de paquetes consistente, Y no domina a X en el sentido de Pareto". Intercambiar el orden de los cuantificadores "para todos" no altera el significado lógico.

La condición NecPE permanece igual, ya sea que permitamos todas las clasificaciones de cestas aditivas o que permitamos solo 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 artículos. Uno de ellos, digamos Alice, necesariamente recibe el artículo de menor clasificación. Existen clasificaciones de cestas aditivas consistentes en las que Alice valora este artículo en 0, mientras que George lo valora en 1. Por lo tanto, dárselo a Alice no es Pareto-eficiente.

Si exigimos que todos los elementos tengan un valor estrictamente positivo, entonces dar todos los elementos a un solo agente es trivialmente NecPE, pero es 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 o 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 3r de y. Alice gana 6r - 4r y George gana 8r - 3r , por lo que ambas ganancias son positivas. En el segundo caso, se mantiene un argumento análogo.

Posible eficiencia de Pareto

Brams, Edelman y Fishburn [ 1 ] : 9 llaman a una asignación Pareto-posible si es Pareto-eficiente para algunas clasificaciones de paquetes que son consistentes con las clasificaciones de los elementos de los agentes. Obviamente, toda asignación que garantiza 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 [Alice: 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. Cabe destacar 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. Afirman 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 los artículos 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 conjuntos consistente para la cual, para cualquier otra asignación Y, Y no domina a X". Debe ser la misma clasificación de conjuntos para todas las demás asignaciones Y.
  • "X es PosPE" es equivalente a "Para cualquier otra asignación Y, existe una clasificación de paquetes consistente, para la cual Y no domina a X". Puede haber una clasificación de paquetes diferente para cualquier otra asignación Y.

Si X es Pareto-posible, entonces es PosPE, pero la otra implicación no es (lógicamente) verdadera.

La condición de Pareto-posible permanece igual, ya sea que permitamos todas las clasificaciones de cestas aditivas o que permitamos solo clasificaciones que se basen en valoraciones aditivas con diferencias decrecientes . [ 3 ] : Sec.8

Eficiencia de Pareto de dominancia estocástica

Bogomolnaia y Moulin [ 4 ] : 302–303 presentan una noción de eficiencia para el contexto de la 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 X i domina débilmente estocásticamente (wsd) un paquete Y i si para cada elemento z, la fracción total de elementos 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 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; véase la extensión del conjunto responsivo . En particular, X i sd Y i si y solo si, para cada clasificación de paquetes consistente con la clasificación de elementos, X i es al menos tan bueno como Y i . [ 5 ] Un paquete X i domina estrictamente estocásticamente (ssd) un paquete Y i si X i wsd Y i y X i ≠ Y i . Equivalentemente, para al menos un elemento 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 1 ,...,X n ) domina estocásticamente a otra asignación Y = (Y 1 ,...,Y n ), si para cada agente i : X i wsd Y i , y 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 existe ninguna 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 indicó anteriormente, la posibilidad de Pareto implica la posibilidad de Pareto, 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 los siguientes son equivalentes:

  • (a) X es sd-eficiente (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 fraccionalmente Pareto-eficiente (es decir, X es Pareto-posible);
  • (c) existen clasificaciones de cestas aditivas consistentes con las clasificaciones de ítems 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 ] : Lem.3 demuestran otra caracterización útil de la eficiencia sd, para el mismo escenario de asignación aleatoria justa pero con clasificaciones estrictas de los elementos. Definimos el grafo de intercambio de una asignación fraccionaria dada como un grafo dirigido en el que los nodos son los elementos, 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. Definimos una asignación como acíclica si su grafo 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 haces discretos , con clasificaciones de haces responsivas : [ 8 ] [ 1 ] : Lem.2.1

  • Si X i >> Y i (es decir: X iY 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 paquetes receptiva 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 paquetes receptiva consistente con la clasificación de elementos, para la cual X i <Y i .

Por lo tanto, se cumple lo siguiente para las relaciones de dominancia de asignaciones discretas: X >> Y si y solo si X necesariamente domina a Y en el sentido de Pareto . [ 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 a 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.

Eficiencia de Pareto por dominancia lexicográfica

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

Una asignación X = (X 1 ,...,X n ) domina lexicográficamente hacia abajo (dl) a otra asignación Y = (Y 1 ,...,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 existe otra asignación que la domine dl.

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, la dominancia sd implica la dominancia dl y la dominancia 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 asignada a cada agente debe ser 1), con clasificaciones estrictas de los elementos, donde puede haber más elementos que agentes (por lo que algunos elementos pueden quedar 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:

  • 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á asignado en su totalidad).

La equivalencia no se cumple si existen restricciones distributivas: hay asignaciones que son sd-eficientes pero no dl-eficientes. [ 9 ] : Ejemplo 4

Lecturas adicionales

  • Aziz, Gaspers, Mackenzie y Walsh [ 10 ] estudian cuestiones computacionales relacionadas con nociones de equidad ordinal. En la Sección 7 estudian brevemente la eficiencia de Pareto sd.
  • Dogan, Dogan y Yildiz [ 11 ] estudian una relación de dominación diferente entre asignaciones: una asignación X domina a una asignación Y si es Pareto-eficiente para un conjunto más grande de clasificaciones de paquetes consistentes con las clasificaciones de los elementos.
  • 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 demuestran que una lotería es sd-eficiente si y solo si cada subconjunto del soporte de la lotería no está dominado.

Referencias

  1. 1 2 3 4 5 6 7 8 Brams, Steven J.; Edelman, Paul H.; Fishburn, Peter C. (2003-09-01). "División justa de artículos indivisibles" . Theory and Decision . 55 (2): 147– 180. doi : 10.1023/B:THEO.0000024421.85722.0a . ISSN 1573-7187 . S2CID 153943630 .  
  2. 1 2 Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (2010-08-04). "División justa bajo preferencias ordinales: cálculo de asignaciones libres de envidia de bienes indivisibles" . Actas de la Conferencia ECAI 2010: 19.ª Conferencia Europea sobre Inteligencia Artificial . NLD: IOS Press: 387–392 . ISBN 978-1-60750-605-8.
  3. 1 2 Segal-Halevi, Erel; Hassidim, Avinatan; Aziz, Haris (2020-03-10). "Asignación justa con diferencias decrecientes" . Journal of Artificial Intelligence Research . 67 : 471–507–471–507. arXiv : 1705.07993 . doi : 10.1613/jair.1.11994 . ISSN 1076-9757 . S2CID 108290839 .  
  4. 1 2 3 Bogomolnaia, Anna; Moulin, Hervé (2001-10-01). "Una nueva solución al problema de la 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. 1 2 Cho, Wonki Jo; Doğan, Battal (2016-09-01). "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. 1 2 McLennan, Andrew (2002-08-01). "Eficiencia ordinal y el 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. (1996-03-01). "Probabilidad cualitativa lineal finita" . Journal of Mathematical Psychology . 40 (1): 64– 77. doi : 10.1006/jmps.1996.0004 . ISSN 0022-2496 . 
  9. Aziz, Haris; Brandl, Florian (2022-09-01). "La regla de la alimentación vigilante: un enfoque general para el diseño económico probabilístico con restricciones" . Games and Economic Behavior . 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 (2015-10-01). "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 (2018-05-01). "Un nuevo criterio de eficiencia ex ante e implicaciones para el mecanismo serial probabilístico" . Journal of Economic Theory . 175 : 178–200 . doi : 10.1016/j.jet.2018.01.011 . hdl : 11693/48988 . ISSN 0022-0531 . 
  12. Abdulkadiroğlu, Atila; Sönmez, Tayfun (2003-09-01). "Eficiencia ordinal y conjuntos dominados de asignaciones" . Journal of Economic Theory . 112 (1): 157– 172. doi : 10.1016/S0022-0531(03)00091-7 . hdl : 10161/1940 . ISSN 0022-0531 . 
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ordinal_Pareto_efficiency&oldid=1310201247"