Asignación proporcional de artículos

La asignación proporcional de elementos es un problema de asignación justa de elementos , 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}

Como los ítems son indivisibles, puede no existir una asignación proporcional. El caso más simple es cuando hay un solo ítem y al menos dos agentes: si el ítem se asigna a un agente, el otro tendrá un valor de 0, que es menor que 1/2. Por lo tanto, la literatura considera varias relajaciones del requisito de proporcionalidad.

Asignación proporcional

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

$V_{i}(X_{i})\geq V_{i}(M)/n$ .

Puede que no exista una división proporcional. Por ejemplo, si el número de personas es mayor que el número de objetos, algunas personas no recibirán ningún objeto y su valor será cero. Sin embargo, dicha división existe con alta probabilidad para objetos indivisibles bajo ciertos supuestos 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 ítems. Entonces, el problema de decidir si existe una asignación proporcional es NP-completo : puede reducirse a partir del problema de partición . ^[3]

Cómo decidir si existe una asignación PROP: clasificaciones ordinales

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

Pruhs y Woeginger ^[4] presentan un algoritmo politemporal para decidir si existe una asignación proporcional necesaria cuando los agentes tienen clasificaciones estrictas. El algoritmo es más simple 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 verificar si un gráfico bipartito admite un b-matching factible (un matching cuando los bordes 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 el número de agentes es constante . Es abierto si el problema está en P cuando el número de agentes es variable y las preferencias tienen indiferencias. ^[5]

Relación con otros criterios de equidad

Con valoraciones aditivas:

Toda asignación de ítems sin envidia también es proporcional. La implicación opuesta es cierta cuando n = 2, pero no cuando n > 2.
Toda asignación proporcional satisface la cuota máxima . La implicación opuesta no es cierta.

Asignaciones de PROP1

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

$\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 ):

$V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{Y\subseteq M\setminus X_{i},|Y|\leq c}V_{i}(Y)$

PROP0 es equivalente a proporcionalidad, que podría no existir. Por el contrario, una asignación PROP1 siempre existe y se puede encontrar, por ejemplo, mediante la asignación de ítems por turnos . La pregunta 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 PROP1 que también es PE.

Barman y Krishnamurthy ^[7] presentaron un algoritmo de tiempo strongy-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 :

$\exists Y\subseteq X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\setminus Y)\geq V_{i}(M)/n$ .

Presentaron un algoritmo que determina una asignación de tareas PE+PROP1. El algoritmo es fuertemente polinomial en el tiempo 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 del conjunto de i, o añadimos un elemento positivo al conjunto de i, entonces la utilidad de i es al menos 1/ n del total. Su algoritmo 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 fraccionalmente 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:

Toda asignación EF1 también es PROP1, pero lo opuesto no es necesariamente cierto incluso con dos agentes. ^[11]^{: App.A}
Lo mismo es cierto para cualquier c ≥ 1: cada asignación de EF c también es PROP c , pero lo opuesto no es necesariamente cierto incluso con dos agentes.

APUNTALAR*(norte-1) asignaciones

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

$\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 ítems por turnos .

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 la ausencia de envidia y la 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 verdadera cuando n = 2, pero no cuando n > 2. ^[12]^{: Lem.2.3}

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

Aproximación multiplicativa: 1/ n -fracción MMS (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 entrega a i , entonces lleva su valor a al menos 1/ n del total. Formalmente, para todos los i : ^[13]

$\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 ):

$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, si bien siempre existen asignaciones de PROP1, es posible que no existan asignaciones de PROPx. ^[13]^[10]

Asignaciones de PROPm

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

$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 de PROPm cuando el número de agentes es como máximo 5. ^[14]

Referencias

^ Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional. Cambridge University Press. ISBN 9781107060432.(versión gratuita en línea)
^ 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.
^ Bouveret, Sylvain; Lemaître, Michel (2015). "Caracterización de los conflictos en la división justa de bienes indivisibles utilizando una escala de criterios". Agentes autónomos y sistemas multiagente . 30 (2): 259. doi :10.1007/s10458-015-9287-3. S2CID 16041218.
^ Pruhs, Kirk; Woeginger, Gerhard J. (2012). "El divorcio es fácil". En Kranakis, Evangelos; Krizanc, Danny; Luccio, Flaminia (eds.). Diversión con algoritmos . Apuntes de clase en informática. Vol. 7288. Berlín, Heidelberg: Springer. págs. 305–314. doi :10.1007/978-3-642-30347-0_30. ISBN 978-3-642-30347-0.
^ ab 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.
^ ab Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2016). "Toma de decisiones públicas justa | 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}}: Requiere citar revista |journal=( ayuda )
^ 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.
^ Brânzei, Simina; Sandomirskiy, Fedor (3 de julio de 2019). "Algoritmos para la división competitiva de tareas". arXiv : 1907.01766 [cs.GT].
^ Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (11 de diciembre de 2018). "Asignación justa de combinaciones de bienes y tareas indivisibles". arXiv : 1807.10684 [cs.GT].
^ ab 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].
^ Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (2023). "Computing welfare-Maximizing fair assignments of indivisible goods" (Cálculo del bienestar: maximización de asignaciones justas de bienes indivisibles). Revista Europea de Investigación Operativa . 307 (2): 773–784. arXiv : 2012.03979 . doi :10.1016/j.ejor.2022.10.013.
^ abcd Segal-Halevi, Erel; Suksompong, Warut (1 de diciembre de 2019). "Asignación justa y democrática de bienes indivisibles". Inteligencia artificial . 277 : 103167. arXiv : 1709.02564 . doi :10.1016/j.artint.2019.103167. ISSN 0004-3702. S2CID 203034477.
^ ab Moulin, Hervé (2019-08-02). "División justa en la era de Internet". Revista Anual de Economía . 11 (1): 407–441. doi : 10.1146/annurev-economics-080218-025559 . ISSN 1941-1383. S2CID 189297304.
^ ab Baklanov, Artem; Garimidi, Pranav; Gkatzelis, Vasilis; Schoepflin, Daniel (14 de enero de 2021). "Lograr la proporcionalidad hasta el ítem máximo con bienes indivisibles". arXiv : 2009.09508 [cs.GT].