Hispanopedia Wiki
Articulo de referencia

Asignación proporcional de artículos

La asignación proporcional de artículos es un problema de asignación justa de artículos , en el que el criterio de equidad es la proporcionalidad : cada agente debe recibir un p...

Hispanopedia WikiContenido en espanolLectura gratuita

La asignación proporcional de artículos es un problema de asignación justa de artículos , en el que el criterio de equidad es la proporcionalidad : cada agente debe recibir un paquete que valore al menos tanto como 1/ n de la asignación total, donde n es el número de agentes. [ 1 ] : 296–297

Dado que los elementos son indivisibles, es posible que no exista una asignación proporcional. El caso más sencillo se da cuando hay un solo elemento y al menos dos agentes: si el elemento se asigna a un agente, el otro tendrá un valor de 0, que es menor que 1/2. Por lo tanto, la literatura considera diversas flexibilizaciones del requisito de proporcionalidad.

Asignación proporcional

Una asignación de objetos se denomina proporcional (PROP) si cada agente i valora su cesta al menos 1/ n del total. Formalmente, para todo i (donde M es el conjunto de todos los bienes):

  • Vi(incógnitai)≥Vi(METRO)/norte{\displaystyle V_{i}(X_{i})\geq V_{i}(M)/n}.

Es posible que no exista una división proporcional. Por ejemplo, si el número de personas es mayor que el número de artículos, algunas personas no recibirán ningún artículo y su valor será cero. Sin embargo, dicha división existe con alta probabilidad para artículos indivisibles bajo ciertas suposiciones sobre las valoraciones de los agentes. [ 2 ]

Decidir si existe una asignación PROP: utilidades cardinales

Supongamos que los agentes tienen funciones de utilidad cardinales sobre los artículos. Entonces, el problema de decidir si existe una asignación proporcional es NP-completo : se puede reducir del problema de partición . [ 3 ]

Decidir si existe una asignación de PROP: clasificaciones ordinales

Supongamos que los agentes tienen clasificaciones ordinales de los elementos. Una asignación se denomina proporcional necesaria (o proporcional sd ) si es proporcional según todas las valoraciones consistentes con las clasificaciones. Se denomina posiblemente proporcional si es proporcional según al menos un conjunto de valoraciones consistentes.

  • Pruhs y Woeginger [ 4 ] presentan un algoritmo de tiempo polinomial para decidir si existe una asignación necesaria-proporcional, cuando los agentes tienen clasificaciones estrictas. El algoritmo es más sencillo cuando hay dos agentes.
  • Aziz, Gaspers, Mackenzie y Walsh [ 5 ] extienden este algoritmo a agentes con preferencias débiles y con derechos posiblemente diferentes : muestran que el problema de decidir si existe una asignación necesariamente proporcional se puede reducir al problema de comprobar si un grafo bipartito admite un emparejamiento b factible (un emparejamiento cuando las aristas tienen capacidades).
  • También presentan algoritmos para decidir si existe una asignación posiblemente proporcional. Su tiempo de ejecución es polinomial si las preferencias son estrictas o si el número de agentes es constante . Queda por determinar si el problema pertenece a P cuando el número de agentes es variable y las preferencias son indiferentes. [ 5 ]

Relación con otros criterios de equidad

Con valoraciones aditivas:

Asignaciones de PROP1

Una asignación se denomina proporcional hasta los mejores c elementos (PROPc) si para cada agente i , existe un subconjunto de como máximo c elementos que, si se le da a i , lleva el valor total de i a al menos 1/ n del total. Formalmente, para todo i (donde M es el conjunto de todos los bienes): [ 6 ]

  • ∃Y⊆METRO∖incógnitai:   |Y|≤do,   Vi(incógnitai∪Y)≥Vi(METRO)/norte{\displaystyle \exists Y\subseteq M\setminus X_{i}:~~~|Y|\leq c,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}.

Una definición equivalente es: el valor de cada agente i es al menos (1/ n del total) menos (los c elementos más valiosos no asignados a i ):

  • Vi(incógnitai) ≥ Vi(METRO)/norte − máximoY⊆METRO∖incógnitai,|Y|≤doVi(Y){\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{Y\subseteq M\setminus X_{i},|Y|\leq c}V_{i}(Y)}

PROP0 equivale a la proporcionalidad, que podría no existir. En cambio, una asignación PROP1 siempre existe y puede obtenerse, por ejemplo, mediante la asignación rotativa de ítems . La cuestión interesante es cómo combinarla con condiciones de eficiencia como la eficiencia de Pareto (EP).

Encontrar asignaciones eficientes de PROP1

Conitzer, Freeman y Shah [ 6 ] demostraron que, en el contexto de una toma de decisiones públicas justa, una asignación de PROP1 que también es PE.

Barman y Krishnamurthy [ 7 ] presentaron un algoritmo de tiempo fuertemente polinomial que encuentra una asignación PE+PROP1 para bienes (objetos con utilidad positiva).

Branzei y Sandomirskiy [ 8 ] extendieron la condición de PROP1 a las tareas domésticas (objetos con utilidad negativa). Formalmente, para todo i :

  • ∃Y⊆incógnitai:   |Y|≤1,   Vi(incógnitai∖Y)≥Vi(METRO)/norte{\displaystyle \exists Y\subseteq X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\setminus Y)\geq V_{i}(M)/n}.

Presentaron un algoritmo que encuentra una asignación de tareas PE+PROP1. El algoritmo tiene una complejidad temporal fuertemente polinómica si el número de objetos o el número de agentes (o ambos) son fijos.

Aziz, Caragiannis, Igarashi y Walsh [ 9 ] extendieron la condición de PROP1 a valoraciones mixtas (los objetos pueden tener utilidades tanto positivas como negativas). En este contexto, una asignación se denomina PROP1 si, para cada agente i , si eliminamos un elemento negativo de su cesta o añadimos un elemento positivo, entonces la utilidad de i es al menos 1/ n del total. Su algoritmo de Ganador Ajustado Generalizado encuentra una asignación PE+EF1 para dos agentes; dicha asignación también es PROP1.

Aziz, Moulin y Sandomirskiy [ 10 ] presentaron un algoritmo de tiempo fuertemente polinomial para encontrar una asignación que sea fraccionariamente-PE (más fuerte que PE) y PROP1, con valoraciones mixtas generales, incluso si el número de agentes u objetos no es fijo, e incluso si los agentes tienen diferentes derechos.

Relación con otros criterios de equidad

Con valoraciones aditivas:

  • Cada asignación EF1 es también PROP1, pero lo contrario no es necesariamente cierto incluso con dos agentes. [ 11 ] : Apéndice A
  • Lo mismo es cierto para cualquier c ≥ 1: Cada asignación EF c es también PROP c , pero lo contrario no es necesariamente cierto incluso con dos agentes.

Asignaciones PROP*( n -1)

Una asignación se denomina proporcional a partir de todos los elementos excepto c (PROP* c ) para un agente i si existe un conjunto de como máximo c elementos que, si se eliminan del conjunto de todos los elementos, entonces i valora su cesta al menos 1/ n del resto. Formalmente, para todo i : [ 12 ]

  • ∃Y⊆METRO:   |Y|≤do,   Vi(incógnitai)≥Vi(METRO∖Y)/norte{\displaystyle \exists Y\subseteq M:~~~|Y|\leq c,~~~V_{i}(X_{i})\geq V_{i}(M\setminus Y)/n}.

PROP*( n -1) es ligeramente más fuerte que PROP1: cuando n =2, PROP*( n -1) es equivalente a EF1, pero PROP1 es más débil. Siempre existe una asignación PROP*( n -1) y se puede encontrar, por ejemplo, mediante la asignación de elementos round-robin .

Relación con otros criterios de equidad

Con valoraciones aditivas:

  • EF1 implica PROP*( n -1). La implicación opuesta es cierta cuando n =2, pero no cuando n >2. Por lo tanto, la relación entre EF1 y PROP*( n -1) es análoga a la relación entre ausencia de envidia y proporcionalidad, lo que demuestra que PROP*( n -1) es una relajación más natural de la proporcionalidad que PROP1.
  • Además, para cualquier entero c ≥ 0, EF c implica PROP*(( n -1) c ). La implicación opuesta es cierta cuando n =2, pero no cuando n >2. [ 12 ] : Lem.2.3

Las siguientes aproximaciones de participación maximin están implícitas en PROP*( n -1): [ 12 ] : Lem.2.7

  • Aproximación multiplicativa: MMS de fracción 1/ n (el 1/ n es ajustado); [ 12 ] : Prop.3.6
  • Aproximación ordinal: 1 de (2 n -1) MMS (el 2 n -1 es ajustado). De manera similar, para cada entero c , PROP* c implica 1 de ( c + n ) MMS.
  • MMS cuando la función de valor es binaria. La implicación opuesta también es válida.

Asignaciones de PROPx

Una asignación se denomina proporcional hasta el peor elemento (PROPx) si para cada agente i , para cualquier subconjunto con un elemento no asignado a i , si el subconjunto se le da a i , entonces su valor aumenta al menos a 1/ n del total. Formalmente, para todo i : [ 13 ]

  • ∀Y⊆METRO∖incógnitai:   |Y|=1,   Vi(incógnitai∪Y)≥Vi(METRO)/norte{\displaystyle \forall Y\subseteq M\setminus X_{i}:~~~|Y|=1,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}

Una definición equivalente es: el valor de cada agente i es al menos (1/ n del total) menos (el elemento menos valioso no asignado a i ):

  • Vi(incógnitai) ≥ Vi(METRO)/norte − minY⊆METRO∖incógnitai,|Y|=1Vi(Y){\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\min _{Y\subseteq M\setminus X_{i},|Y|=1}V_{i}(Y)}

Obviamente, PROPx es más fuerte que PROP1. Además, mientras que las asignaciones de PROP1 siempre existen, las asignaciones de PROPx pueden no existir. [ 13 ] [ 10 ]

asignaciones de PROPm

Una asignación se denomina proporcional hasta el elemento maximin (PROPm) si el valor de cada agente i es al menos (1/ n del total) menos (el elemento maximin no asignado a i ), donde el elemento maximin es el máximo sobre todos los demás n -1 agentes j , del elemento menos valioso asignado a j . Formalmente: [ 14 ]

  • Vi(incógnitai) ≥ Vi(METRO)/norte − máximoj≠iminY⊆incógnitaj,|Y|=1Vi(Y){\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{j\neq i}\min _{Y\subseteq X_{j},|Y|=1}V_{i}(Y)}

Obviamente, PROPx es más fuerte que PROPm, que a su vez es más fuerte que PROP1. Existe una asignación PROPm cuando el número de agentes es como máximo 5. [ 14 ]

Referencias

  1. ↑ Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice . Cambridge University Press. ISBN 9781107060432.
  2. ↑ Suksompong, Warut (2016). "Existencia asintótica de asignaciones proporcionalmente justas". Ciencias Sociales Matemáticas . 81 : 62–65 . arXiv : 1806.00218 . doi : 10.1016/j.mathsocsci.2016.03.007 . S2CID 14055462 . 
  3. ↑ Bouveret, Sylvain; Lemaître, Michel (2015). "Caracterización de conflictos en la división justa de bienes indivisibles mediante una escala de criterios". Autonomous Agents and Multi-Agent Systems . 30 (2): 259. doi : 10.1007/s10458-015-9287-3 . S2CID 16041218 . 
  4. ↑ Pruhs, Kirk; Woeginger, Gerhard J. (2012). "Divorciarse es fácil" . En Kranakis, Evangelos; Krizanc, Danny; Luccio, Flaminia (eds.). Diversión con algoritmos . Lecture Notes in Computer Science. Vol. 7288. Berlín, Heidelberg: Springer. pp. 305–314 . doi : 10.1007/978-3-642-30347-0_30 . ISBN   978-3-642-30347-0.
  5. 1 2 Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (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 . S2CID 1408197 . 
  6. 1 2 Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2016). "Toma de decisiones públicas justas | Actas de la Conferencia ACM de 2017 sobre Economía y Computación". arXiv : 1611.04034 . doi : 10.1145/3033274.3085125 . S2CID 30188911 . {{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  7. ↑ Barman, Siddharth; Krishnamurthy, Sanath Kumar (2019-07-17). "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 .  
  8. ↑ Brânzei, Simina; Sandomirskiy, Fedor (3 de julio de 2019). "Algoritmos para la división competitiva de tareas". arXiv : 1907.01766 [ cs.GT ].
  9. ↑ Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (2018-12-11). "Asignación justa de combinaciones de bienes y tareas indivisibles". arXiv : 1807.10684 [ cs.GT ].
  10. 1 2 Aziz, Haris; Moulin, Herve; Sandomirskiy, Fedor (2019-09-02). "Un algoritmo de tiempo polinomial para calcular una asignación Pareto óptima y casi proporcional". arXiv : 1909.00740 [ cs.GT ].
  11. ↑ Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (2023). "Cálculo del bienestar: maximización de asignaciones justas de bienes indivisibles". European Journal of Operational Research . 307 (2): 773– 784. arXiv : 2012.03979 . doi : 10.1016/j.ejor.2022.10.013 .
  12. 1 2 3 4 Segal-Halevi, Erel; Suksompong, Warut (2019-12-01). "Asignación democrática justa de bienes indivisibles". Inteligencia Artificial . 277 103167. arXiv : 1709.02564 . doi : 10.1016/j.artint.2019.103167 . ISSN 0004-3702 . S2CID 203034477 .  
  13. 1 2 Moulin, Hervé (2019-08-02). "División justa en la era de Internet" . Annual Review of Economics . 11 (1): 407– 441. doi : 10.1146/annurev-economics-080218-025559 . ISSN 1941-1383 . S2CID 189297304 .  
  14. 1 2 Baklanov, Artem; Garimidi, Pranav; Gkatzelis, Vasilis; Schoepflin, Daniel (2021-01-14). "Lograr proporcionalidad hasta el elemento maximin con bienes indivisibles". arXiv : 2009.09508 [ cs.GT ].