Asignación justa de artículos

Problema de división justa en el que los elementos a dividir son discretos en lugar de continuos

La asignación justa de elementos es un tipo de problema de división justa en el que los elementos a dividir son discretos en lugar de continuos. Los elementos deben dividirse entre varios socios que potencialmente los valoran de manera diferente, y cada elemento debe entregarse en su totalidad a una sola persona. ^[1] Esta situación se presenta en varios escenarios de la vida real:

• Varios herederos quieren dividir la propiedad heredada, que contiene por ejemplo una casa, un coche, un piano y varios cuadros.
• Varios profesores desean dividir los cursos impartidos en su facultad. Cada profesor puede impartir uno o varios cursos completos.
• Fiestas de intercambio de regalos de elefante blanco

La indivisibilidad de los bienes implica que una división justa puede no ser posible. Como ejemplo extremo, si solo hay un único bien (por ejemplo, una casa), debe entregarse a un solo socio, pero esto no es justo para los demás socios. Esto contrasta con el problema del corte justo de la torta , donde el dividendo es divisible y siempre existe una división justa. En algunos casos, el problema de la indivisibilidad se puede mitigar introduciendo pagos monetarios o una rotación basada en el tiempo , o descartando algunos de los bienes. ^{[2] : 285} Pero tales soluciones no siempre están disponibles.

Un problema de asignación de elementos tiene varios ingredientes:

1. Los socios deben expresar sus preferencias por los diferentes paquetes de artículos.
2. El grupo debe decidir un criterio de equidad .
3. En función de las preferencias y el criterio de equidad, se debe ejecutar un algoritmo de asignación justa para calcular una división justa.

Estos ingredientes se explican en detalle a continuación.

Preferencias

Preferencias combinatorias

Una forma ingenua de determinar las preferencias es pedir a cada socio que proporcione un valor numérico para cada posible combinación. Por ejemplo, si los artículos a dividir son un automóvil y una bicicleta, un socio puede valorar el automóvil en 800, la bicicleta en 200 y la combinación {automóvil, bicicleta} en 900 (consulte Funciones de utilidad sobre bienes indivisibles para obtener más ejemplos). Este enfoque presenta dos problemas:

1. Puede resultar difícil para una persona calcular valores numéricos exactos de los paquetes.
2. La cantidad de combinaciones posibles puede ser enorme: si hay artículos, entonces hay combinaciones posibles. Por ejemplo, si hay 16 artículos, entonces cada socio deberá presentar sus preferencias utilizando 65536 números. ${\displaystyle m}$ ${\displaystyle 2^{m}}$

El primer problema motiva el uso de la utilidad ordinal en lugar de la utilidad cardinal . En el modelo ordinal, cada socio sólo debería expresar una clasificación sobre los diferentes paquetes, es decir, decir qué paquete es el mejor, cuál es el segundo mejor, y así sucesivamente. Esto puede ser más fácil que calcular números exactos, pero sigue siendo difícil si el número de artículos es grande. ${\displaystyle 2^{m}}$

El segundo problema suele solucionarse trabajando con elementos individuales en lugar de con paquetes:

• En el enfoque cardinal, cada socio debe informar una valoración numérica para cada artículo;
• En el enfoque ordinal, cada socio debe informar una clasificación de los elementos, es decir, decir cuál elemento es el mejor, cuál es el segundo mejor, etc.

Bajo supuestos adecuados, es posible elevar las preferencias sobre los artículos a preferencias sobre los paquetes. ^{[3] : 44–48} Luego, los agentes informan sus valoraciones/clasificaciones sobre artículos individuales, y el algoritmo calcula para ellos sus valoraciones/clasificaciones sobre los paquetes.

Preferencias aditivas

Para simplificar el problema de asignación de artículos, es común suponer que todos los artículos son bienes independientes (por lo que no son bienes sustitutos ni bienes complementarios ). ^[4] Entonces:

• En el enfoque cardinal, cada agente tiene una función de utilidad aditiva (también llamada función de utilidad modular ). Una vez que el agente informa un valor para cada artículo individual, es fácil calcular el valor de cada paquete sumando los valores de sus artículos.
• En el enfoque ordinal, la aditividad nos permite inferir algunas clasificaciones entre conjuntos. Por ejemplo, si una persona prefiere w a x, a y, a z, entonces necesariamente prefiere {w,x} a {w,y} o a {x,y}, y {w,y} a {x}. Esta inferencia es solo parcial, es decir, no podemos saber si el agente prefiere {w} a {x,y} o incluso {w,z} a {x,y}. ^{[5] [6]}

La aditividad implica que cada socio siempre puede elegir un "elemento preferible" del conjunto de elementos de la mesa, y esta elección es independiente de los otros elementos que pueda tener el socio. Esta propiedad es utilizada por algunos algoritmos de asignación justa que se describirán a continuación. ^{[2] : 287–288}

Lenguajes de representación de preferencias compactas

Los lenguajes de representación de preferencias compactos se han desarrollado como un compromiso entre la expresividad total de las preferencias combinatorias y la simplicidad de las preferencias aditivas. Proporcionan una representación sucinta de algunas clases naturales de funciones de utilidad que son más generales que las utilidades aditivas (pero no tan generales como las utilidades combinatorias). Algunos ejemplos son: ^{[2] : 289–294}

• Preferencias 2-aditivas : cada socio informa un valor para cada conjunto de elementos de tamaño máximo 2. El valor de un conjunto se calcula sumando los valores de los elementos individuales del conjunto y sumando los valores de los pares del conjunto. Normalmente, cuando hay elementos sustitutos, los valores de los pares serán negativos, y cuando hay elementos complementarios, los valores de los pares serán positivos. Esta idea se puede generalizar a preferencias k-aditivas para cada entero positivo k .
• Modelos gráficos : para cada socio, existe un gráfico que representa las dependencias entre los diferentes elementos. En el enfoque cardinal, una herramienta común es la red GAI (Independencia Aditiva Generalizada). En el enfoque ordinal, una herramienta común es la red CP (Preferencias Condicionales) y sus extensiones: red TCP , red UCP , teoría CP , red CI (Importancia Condicional) y red SCI (una simplificación de la red CI).
• Lenguajes basados ​​en lógica : cada socio describe algunos paquetes utilizando una fórmula lógica de primer orden y puede asignar un valor para cada fórmula. Por ejemplo, un socio puede decir: "Para (x o (y y z)), mi valor es 5". Esto significa que el agente tiene un valor de 5 para cualquiera de los paquetes: x, xy, xz, yz, xyz.
• Lenguajes de puja : se han estudiado numerosos lenguajes para representar preferencias combinatorias en el contexto de subastas combinatorias . Algunos de estos lenguajes se pueden adaptar a la configuración de asignación de artículos.

Criterios de equidad

Criterios de garantía individuales

Un criterio de garantía individual es un criterio que debería cumplir cada socio individual, siempre que éste informe verazmente sus preferencias. A continuación se presentan cinco de esos criterios, ordenados del más débil al más fuerte (suponiendo que las valoraciones sean aditivas): ^[7]

Maximizar la cuota

La cuota máxima (también llamada: cuota máxima-mínima-justa) de un agente es el paquete más preferido que podría garantizarse como divisor en la estrategia de dividir y elegir contra oponentes adversarios. Una asignación se llama MMS-justa si cada agente recibe un paquete que prefiere débilmente sobre su MMS. ^[8]

Proporcionalreparto equitativo (PFS)

La parte proporcional-justa de un agente es 1/ n de su utilidad de todo el conjunto de elementos. Una asignación se denomina proporcional si cada agente recibe un conjunto que vale al menos su parte proporcional-justa.

Reparto justo mínimo y máximo (mFS)

La participación mínima-máxima-justa de un agente es la utilidad mínima que puede esperar obtener de una asignación si todos los demás agentes tienen las mismas preferencias que él, cuando siempre recibe la mejor parte. También es la utilidad mínima que un agente puede obtener con seguridad en el juego de asignación “Alguien corta, yo elijo primero”. Una asignación es mFS-justa si todos los agentes reciben un paquete que prefieren débilmente sobre su mFS. ^[7] La ​​mFS-justa puede describirse como el resultado del siguiente proceso de negociación. Se sugiere una cierta asignación. Cada agente puede objetarla exigiendo que otro agente haga una asignación diferente, dejándole elegir primero. Por lo tanto, un agente se opondría a una asignación solo si en todas las particiones hay un paquete que prefiere fuertemente sobre su paquete actual. Una asignación es mFS-justa si ningún agente se opone a ella, es decir, para cada agente existe una partición en la que todos los paquetes son débilmente peores que su participación actual.

Para cada agente con utilidad subaditiva , el mFS vale al menos . Por lo tanto, cada asignación mFS-justa es proporcional. Para cada agente con utilidad superaditiva , el MMS vale como máximo . Por lo tanto, cada asignación proporcional es MMS-justa. Ambas inclusiones son estrictas, incluso cuando cada agente tiene utilidad aditiva . Esto se ilustra en el siguiente ejemplo: ^[7] ${\displaystyle 1/n}$ ${\displaystyle 1/n}$

Hay tres agentes y tres elementos:

• Alice valora los elementos como 2,2,2. Para ella, MMS=PFS=mFS=2.
• Bob valora los elementos como 3, 2, 1. Para él, MMS=1, PFS=2 y mFS=3.
• Carl valora los ítems como 3, 2, 1. Para él, MMS=1, PFS=2 y mFS=3.

Las posibles asignaciones son las siguientes:

• Cada asignación que otorga un elemento a cada agente es justa para MMS.
• Toda asignación que otorga el primer y segundo artículo a Bob y Carl y el tercer artículo a Alice es proporcional.
• Ninguna asignación es mFS-justa.

Las implicaciones anteriores no se sostienen cuando las valoraciones de los agentes no son sub/superaditivas. ^[9]

Libre de envidia(E.F.)

Cada agente prefiere débilmente su propio conjunto de elementos a cualquier otro conjunto de elementos. Toda asignación libre de envidia de todos los elementos es equitativa en términos de mFS; esto se desprende directamente de las definiciones ordinales y no depende de la aditividad. Si las valoraciones son aditivas, entonces una asignación de EF también es proporcional y equitativa en términos de MMS. De lo contrario, una asignación de EF puede no ser proporcional e incluso no ser equitativa en términos de MMS. ^[9]

Las versiones más débiles de EF incluyen: ^[10]

• Sin envidia excepto 1 (EF1) : para cada dos agentes A y B, si eliminamos del conjunto de B el elemento más valioso para A, entonces A no envidia a B (en otras palabras, el "nivel de envidia" de A en B es como máximo el valor de un único elemento). En condiciones de monotonía, siempre existe una asignación EF1.
• Sin envidia, excepto el más barato (EFx) : para cada dos agentes A y B, si eliminamos del conjunto de B el elemento menos valioso para A, entonces A no envidia a B. EFx es estrictamente más fuerte que EF1. No se sabe si siempre existen asignaciones de EFx.

Equilibrio competitivode Ingresos Iguales (CEEI)

Este criterio se basa en el siguiente argumento: el proceso de asignación debe considerarse como una búsqueda de un equilibrio entre la oferta (el conjunto de objetos, cada uno con un precio público) y la demanda (los deseos de los agentes, cada agente con el mismo presupuesto para comprar los objetos). Se alcanza un equilibrio competitivo cuando la oferta coincide con la demanda. El argumento de equidad es sencillo: los precios y los presupuestos son los mismos para todos. CEEI implica FE independientemente de la aditividad. Cuando las preferencias de los agentes son aditivas y estrictas (cada paquete tiene un valor diferente), CEEI implica eficiencia de Pareto . ^[7]

Criterios de optimización global

Un criterio de optimización global evalúa una división en función de una función de bienestar social dada :

• El bienestar social igualitario es la utilidad mínima de un solo agente. Una asignación de ítems se denomina igualitaria-óptima si alcanza el máximo bienestar igualitario posible, es decir, maximiza la utilidad del agente más pobre. Dado que puede haber varias asignaciones diferentes que maximicen la utilidad más pequeña, la optimalidad igualitaria suele refinarse hasta convertirse en leximin-optimalidad : del subconjunto de asignaciones que maximizan la utilidad más pequeña, selecciona aquellas asignaciones que maximizan la segunda utilidad más pequeña, luego la tercera utilidad más pequeña, y así sucesivamente.
• El bienestar social de Nash es el producto de las utilidades de los agentes. Una asignación se denomina óptima de Nash o de máximo bienestar de Nash si maximiza el producto de las utilidades. Las asignaciones óptimas de Nash tienen algunas propiedades de equidad interesantes. ^[10]

Una ventaja de los criterios de optimización global sobre los criterios individuales es que las asignaciones que maximizan el bienestar son eficientes en términos de Pareto .

Algoritmos de asignación

En las páginas sobre criterios de equidad específicos se analizan diversos algoritmos para la asignación justa de artículos:

• Asignación de artículos con máxima participación ;
• Asignación proporcional de artículos ;
• Asignación de elementos de minimax-share: el problema de calcular el mFS de un agente es coNP-completo . El problema de decidir si existe una asignación de mFS está en , pero su complejidad computacional exacta aún se desconoce. ^[7] ${\displaystyle NP^{NP}}$
• Asignación de artículos sin envidia ;
• Asignación de artículos aproximadamente justa y eficiente ;
• Asignación igualitaria de artículos ;
• Asignación óptima de Nash: ^[11] y ^[12] demuestran la dificultad de calcular asignaciones utilitaristas óptimas y óptimas de Nash. ^[13] presentan un procedimiento de aproximación para asignaciones óptimas de Nash.
• Secuencia de selección : protocolo simple en el que los agentes se turnan para seleccionar elementos, según una secuencia de turnos preestablecida. El objetivo es diseñar la secuencia de selección de manera que maximice el valor esperado de una función de bienestar social (por ejemplo, igualitaria o utilitaria) bajo ciertos supuestos probabilísticos sobre las valoraciones de los agentes.
• Equilibrio competitivo: en el artículo sobre el mercado de Fisher se describen varios algoritmos para encontrar una asignación de CE .

Entre divisible e indivisible

Los trabajos tradicionales sobre asignación justa suponen que todos los elementos son divisibles o que todos los elementos son indivisibles. Algunos trabajos recientes estudian situaciones en las que la distinción entre divisible e indivisible es más difusa.

Limitar la cantidad de compartición

Varios trabajos suponen que todos los objetos pueden dividirse si es necesario (por ejemplo, mediante propiedad compartida o tiempo compartido), pero compartir es costoso o indeseable. Por lo tanto, se desea encontrar una asignación justa con el menor número posible de objetos compartidos o de comparticiones. Existen límites superiores estrictos en la cantidad de objetos compartidos/comparticiones necesarios para varios tipos de asignaciones justas entre n agentes:

• Para una asignación proporcional , libre de envidia , equitativa e igualitaria , n −1 comparticiones/objetos compartidos son siempre suficientes, y pueden ser necesarios; ^[14]
• Para dividir por consenso en k partes, n ( n −1) comparticiones/objetos compartidos son siempre suficientes y pueden ser necesarios. ^[15]

Esto plantea la cuestión de si es posible lograr asignaciones justas con menos participaciones que el límite superior del peor caso:

• Sandomirskiy y Segal-Halevi ^[14] estudian la minimización de la compartición en asignaciones que son a la vez justas y fraccionalmente eficientes en el sentido de Pareto (fPO). Demuestran que, si las valoraciones de los agentes no son degeneradas, el número de asignaciones fPO es polinomial en el número de objetos (para un número fijo de agentes). Por lo tanto, es posible enumerarlos todos en tiempo polinomial y encontrar una asignación que sea justa y fPO con el menor número de comparticiones. Por el contrario, si las valoraciones son degeneradas, el problema se vuelve NP-hard. Presentan evidencia empírica de que, en casos realistas, a menudo existe una asignación con sustancialmente menos comparticiones que el límite del peor caso.
• Misra y Sethia ^[16] complementan su resultado demostrando que, cuando n no es fijo, incluso para valoraciones no degeneradas, es NP-difícil decidir si existe una asignación libre de envidia de fPO con 0 participaciones. También demuestran un enfoque alternativo para enumerar gráficos de consumo distintos para asignaciones con una pequeña cantidad de participaciones.
• Goldberg, Hollender, Igarashi, Manurangsi y Suksompong ^[15] estudian la minimización de la compartición en la división del consenso . Demuestran que, para agentes con utilidades aditivas , existe un algoritmo de tiempo polinomial para calcular una reducción a la mitad del consenso con como máximo n comparticiones, y para calcular una k -división de consenso con como máximo ( k −1) n cortes. Pero la minimización de la compartición es NP-difícil: para cualquier n fijo , es NP-difícil distinguir entre una instancia que requiere n comparticiones y una instancia que requiere 0 comparticiones. Probabilísticamente, n comparticiones son casi seguramente necesarias para la reducción a la mitad del consenso cuando las utilidades de los agentes se extraen de distribuciones probabilísticas. Para agentes con utilidades monótonas no aditivas, la reducción a la mitad del consenso es PPAD-difícil, pero existen algoritmos de tiempo polinomial para un número fijo de agentes.
• Bismuth, Makarov, Shapira y Segal-Halevi ^[17] estudian la asignación justa con valoraciones idénticas, que es equivalente a la programación de máquinas idénticas , y también la configuración más general de la programación de máquinas uniformes . Estudian la complejidad en tiempo de ejecución de decidir la existencia de una asignación justa con s comparticiones u objetos compartidos, donde s es menor que el límite superior del peor caso de n −1. Demuestran que, para las comparticiones, el problema es NP-difícil para cualquier s ≤ n −2; pero para objetos compartidos y n ≥ 3, el problema es polinomial para s = n −2 y NP-difícil para cualquier s ≤ n −3. Cuando n no es fijo, el problema es fuertemente NP-difícil.

Mezcla de bienes divisibles e indivisibles

• Bei, Li, Liu, Liu y Lu ^{[18] estudian una mezcla de} bienes indivisibles y divisibles (objetos con utilidades positivas). Definen una aproximación a la ausencia de envidia llamada EFM (envy-freeness for mixed items), que generaliza tanto la ausencia de envidia para los bienes divisibles como EF1 para los bienes indivisibles. Demuestran que siempre existe una asignación EFM para cualquier número de agentes con valoraciones aditivas. Presentan algoritmos eficientes para calcular las asignaciones EFM para dos agentes con valoraciones aditivas generales y para n agentes con valoraciones lineales por partes sobre los bienes divisibles. También presentan un algoritmo eficiente que encuentra una asignación EFM aproximada en épsilon .
• Bei, Liu, Lu y Wang ^[19] estudian el mismo escenario, centrándose en la equidad de participación máxima . Proponen un algoritmo que calcula una asignación de MMS aproximada a alfa para cualquier número de agentes, donde alfa es una constante entre 1/2 y 1, que aumenta monótonamente con el valor de los bienes divisibles en relación con los valores de MMS.
• Bhaskar, Sricharan y Vaish ^{[20] estudian una mezcla de} tareas indivisibles (objetos con utilidades negativas) y una torta divisible (con utilidad positiva). Presentan un algoritmo para hallar una asignación EFM en dos casos especiales: cuando cada agente tiene el mismo ranking de preferencias sobre el conjunto de tareas y cuando el número de elementos es como máximo el número de agentes más 1.
• Li, Liu, Lu y Tao ^[21] estudian mecanismos veraces para el EFM. Muestran que, en general, no existe ningún algoritmo EFM veraz, incluso si solo hay un bien indivisible y un bien divisible y solo dos agentes. Pero, cuando los agentes tienen valoraciones binarias sobre bienes indivisibles y valoraciones idénticas sobre un solo bien divisible, existe un EFM y un mecanismo veraz. Cuando los agentes tienen valoraciones binarias sobre bienes divisibles e indivisibles, existe un EFM y un mecanismo veraz cuando solo hay dos agentes, o cuando hay un solo bien divisible.
• Nishimura y Sumita ^[22] estudian las propiedades de la asignación máxima de bienestar de Nash (MNW) para bienes mixtos. Demuestran que, cuando las valoraciones de todos los agentes son binarias y lineales para cada bien, una asignación MNW satisface una propiedad más fuerte que la EFM, a la que llaman "ausencia de envidia hasta cualquier bien para bienes mixtos". Sus resultados son válidos no sólo para el bienestar máximo de Nash, sino también para una noción general de equidad basada en la minimización de una función estrictamente convexa simétrica. Para valoraciones aditivas generales, demuestran que una asignación MNW satisface una aproximación EF que es más débil que la EFM.
• Kawase, Nishimura y Sumita ^[23] estudian la asignación óptima de bienes mixtos, donde el vector de utilidad debe minimizar una función simétrica estrictamente convexa (esta es una generalización de la asignación de bienes igualitaria y el bienestar máximo de Nash). Suponen que todos los agentes tienen valoraciones binarias. Se sabe que, si solo existen bienes divisibles o solo bienes indivisibles, el problema es solucionable en tiempo polivalente. Muestran que, con bienes mixtos, el problema es NP-hard incluso cuando todos los bienes indivisibles son idénticos. Por el contrario, si todos los bienes divisibles son idénticos, existe un algoritmo de tiempo polivalente.
• Bei, Liu y Lu ^[24] estudian un contexto más general, en el que el mismo objeto puede ser divisible para algunos agentes e indivisible para otros. Muestran que la mejor aproximación posible para MMS es 2/3, incluso para dos agentes; y presentan algoritmos que alcanzan este límite para 2 o 3 agentes. Para cualquier número de agentes, presentan una aproximación 1/2-MMS. También muestran que el EFM es incompatible con la no generación de desperdicios.
• Li, Li, Liu y Wu ^[25] estudian un contexto en el que cada agente puede tener una "ratio de indivisibilidad" diferente (= proporción de elementos que son indivisibles). A cada agente se le garantiza una asignación que es EF/PROP hasta una fracción de un elemento, donde la fracción depende del ratio de indivisibilidad del agente. Los resultados son ajustados hasta una constante para EF y asintóticamente ajustados para PROP.
• Li, Liu, Lu, Tao y Tao ^[26] estudian el precio de la justicia tanto en la asignación de ítems indivisibles como en la mixta. Proporcionan límites para el precio de EF1, EFx, EFM y EFxM. Proporcionan límites estrictos para dos agentes y límites estrictos asintóticamente para n agentes, tanto para servicios públicos escalados como no escalados.

Liu, Lu, Suzuki y Walsh ^[27] analizan algunos resultados recientes sobre elementos mixtos e identifican varias preguntas abiertas:

1. ¿Es EFM compatible con la eficiencia de Pareto ?
2. ¿Existen algoritmos eficientes para maximizar el bienestar social utilitarista entre las asignaciones del EFM?
3. ¿Existen algoritmos acotados o incluso finitos para calcular las asignaciones de EFM en el modelo de consulta de Robertson-Webb ?
4. ¿Siempre existe una asignación de EFM cuando hay tareas indivisibles y una tarta?
5. De manera más general: ¿existe siempre una asignación de EFM cuando tanto los elementos divisibles como los indivisibles pueden ser positivos para algunos agentes y negativos para otros?
6. ¿Existe un algoritmo EFM veraz para agentes con valoraciones aditivas binarias?

Variantes y extensiones

Diferentes derechos

En esta variante, los distintos agentes tienen derecho a distintas fracciones del recurso. Un caso de uso común es la división de los ministerios del gabinete entre los partidos de la coalición. ^[28] Es común suponer que cada partido debería recibir ministerios de acuerdo con el número de escaños que tiene en el parlamento. Las distintas nociones de equidad deben adaptarse en consecuencia. Se consideraron varias clases de nociones de equidad:

• Nociones basadas en el equilibrio competitivo ponderado; ^{[29] [30]}
• Nociones basadas en la ausencia ponderada de envidia; ^{[31] [32] [33]}
• Nociones basadas en la cuota justa ponderada; ^[34]

Asignación a grupos

En esta variante, los paquetes no se entregan a agentes individuales, sino a grupos de agentes. Los casos de uso más comunes son: dividir la herencia entre familias o dividir las instalaciones entre los departamentos de una universidad. Todos los agentes del mismo grupo consumen el mismo paquete, aunque pueden valorarlo de forma diferente. La configuración clásica de asignación de elementos corresponde al caso especial en el que todos los grupos son singletons.

En el caso de los grupos, puede resultar imposible garantizar la justicia unánime (justicia a los ojos de todos los agentes de cada grupo), por lo que a menudo se flexibiliza hasta alcanzar la justicia democrática (justicia a los ojos de, por ejemplo, al menos la mitad de los agentes de cada grupo). ^[35]

Asignación de bienes públicos

En esta variante, cada elemento proporciona utilidad no sólo a un único agente, sino a todos los agentes. Diferentes agentes pueden atribuir distintas utilidades al mismo elemento. El grupo debe elegir un subconjunto de elementos que satisfagan ciertas restricciones, por ejemplo:

• Se pueden seleccionar como máximo k elementos. Esta variante está estrechamente relacionada con la votación multiganador , excepto que en la votación multiganador el número de candidatos elegidos suele ser mucho menor que el número de votantes, mientras que en la asignación de bienes públicos el número de bienes elegidos suele ser mucho mayor que el número de agentes. Un ejemplo es una biblioteca pública que tiene que decidir qué libros comprar, respetando las preferencias de los lectores; el número de libros suele ser mucho mayor que el número de lectores. ^[36]
• El costo total de todos los artículos no debe exceder un presupuesto fijo. Esta variante se conoce a menudo como presupuesto participativo .
• El número de elementos debe ser lo más pequeño posible, siempre que todos los agentes estén de acuerdo en que el conjunto elegido es mejor que el conjunto no elegido. Esta variante se conoce como el problema del subconjunto aceptable .
• Puede haber restricciones generales de matroide , restricciones de coincidencia o restricciones de mochila en el conjunto elegido. ^[37]

La asignación de bienes privados puede verse como un caso especial de asignación de bienes públicos: dado un problema de bienes privados con n agentes y m elementos, donde el agente i valora el elemento j en v _ij , construya un problema de bienes públicos con n · m elementos, donde el agente i valora cada elemento i,j en v _ij , y los otros elementos en 0. El elemento i,j representa esencialmente la decisión de dar el elemento j al agente i . Esta idea puede formalizarse para mostrar una reducción general de la asignación de bienes privados a la asignación de bienes públicos que conserva la asignación máxima de bienestar de Nash, así como una reducción similar que conserva la asignación óptima leximin . ^[36]

Los conceptos de solución comunes para la asignación de bienes públicos son la estabilidad del núcleo (que implica tanto eficiencia de Pareto como proporcionalidad), ^[37] el máximo bienestar de Nash, la optimalidad leximin y la proporcionalidad hasta un artículo. ^[36]

Toma de decisiones públicas

En esta variante, varios agentes tienen que aceptar decisiones sobre varias cuestiones. Un caso de uso común es una familia que tiene que decidir qué actividad realizar cada día (aquí cada cuestión es un día). Cada agente asigna diferentes utilidades a las distintas opciones en cada cuestión. La configuración clásica de asignación de ítems corresponde al caso especial en el que cada cuestión corresponde a un ítem, cada opción de decisión corresponde a dar ese ítem a un agente en particular y las utilidades de los agentes son cero para todas las opciones en las que el ítem se da a otra persona. En este caso, proporcionalidad significa que la utilidad de cada agente es al menos 1/ n de su "utilidad de dictadura", es decir, la utilidad que podría obtener eligiendo la mejor opción en cada cuestión. La proporcionalidad puede ser inalcanzable, pero PROP1 es alcanzable mediante la asignación de ítems por turnos . ^[38]

Asignación repetida

A menudo, los mismos elementos se asignan repetidamente. Por ejemplo, tareas domésticas recurrentes. Si el número de repeticiones es un múltiplo del número de agentes, entonces es posible encontrar en tiempo polinomial una secuencia de asignaciones que esté libre de envidia y sea completa, y encontrar en tiempo exponencial una secuencia que sea proporcional y óptima en el sentido de Pareto. Pero una secuencia libre de envidia y óptima en el sentido de Pareto puede no existir. Con dos agentes, si el número de repeticiones es par, siempre es posible encontrar una secuencia libre de envidia y óptima en el sentido de Pareto. ^[39]

Asignaciones estocásticas de bienes indivisibles

Las asignaciones estocásticas de bienes indivisibles ^[40] son ​​un tipo de asignación justa de artículos en la que una solución describe una distribución de probabilidad sobre el conjunto de asignaciones deterministas.

Supongamos que se deben distribuir m elementos entre n agentes. Formalmente, en el contexto determinista, una solución describe una asignación factible de los elementos a los agentes: una partición del conjunto de elementos en n subconjuntos (uno para cada agente). El conjunto de todas las asignaciones deterministas se puede describir de la siguiente manera:

${\displaystyle {\mathcal {A}}=\{(A^{1},\dots ,A^{n})\mid \forall i\in [n]\colon A^{i}\subseteq [m],\quad \forall i\neq j\in [n]\colon A^{i}\cap A^{j}=\emptyset ,\quad \cup _{i=1}^{n}A^{i}=[m]\}}$

En el contexto estocástico, una solución es una distribución de probabilidad sobre el conjunto . Es decir, el conjunto de todas las asignaciones estocásticas (es decir, todas las soluciones factibles al problema) se puede describir de la siguiente manera: ${\displaystyle {\mathcal {A}}}$

${\displaystyle {\mathcal {D}}=\{d\mid p_{d}\colon {\mathcal {A}}\to [0,1],\sum _{A\in {\mathcal {A}}}p_{d}(A)=1\}}$

Hay dos funciones relacionadas con cada agente, una función de utilidad asociada a una asignación determinista ; ${\displaystyle u_{i}\colon {\mathcal {A}}\to \mathbb {R} _{+}}$ y una función de utilidad esperada asociada a una asignación estocástica que se define de la siguiente manera: ${\displaystyle E_{i}\colon {\mathcal {D}}\to \mathbb {R} _{+}}$ ${\displaystyle u_{i}}$

${\displaystyle E_{i}(d)=\sum _{A\in {\mathcal {A}}}p_{d}(A)\cdot u_{i}(A)}$

Criterios de equidad

Los mismos criterios que se sugieren para la configuración determinista también se pueden considerar en la configuración estocástica:

• Regla utilitaria : esta regla dice que la sociedad debe elegir la solución que maximice la suma de utilidades. Es decir, elegir una asignación estocástica que maximice el bienestar utilitario : Kawase y Sumita ^[40] muestran que la maximización del bienestar utilitario en el contexto estocástico siempre se puede lograr con una asignación determinista . La razón es que el valor utilitario de la asignación determinista es al menos el valor utilitario de : ${\displaystyle d^{*}\in {\mathcal {D}}}$ ${\displaystyle d^{*}={\underset {d\in {\mathcal {D}}}{\operatorname {argmax} }}\sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}$ ${\displaystyle A^{*}={\underset {A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}{\operatorname {argmax} }}\sum _{i=1}^{n}u_{i}(A)}$ ${\displaystyle d^{*}}$ ${\displaystyle \sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d^{*}}(A)\cdot u_{i}(A)\right)=\sum _{A\in {\mathcal {A}}}p_{d^{*}}(A)\sum _{i=1}^{n}u_{i}(A)\leq \max _{A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}\sum _{i=1}^{n}u_{i}(A)}$
• Regla igualitaria: esta regla dice que la sociedad debe elegir la solución que maximice la utilidad de los más pobres. Es decir, elegir una asignación estocástica que maximice el bienestar igualitario : A diferencia de la regla utilitaria, aquí, el escenario estocástico permite que la sociedad alcance un valor más alto ^[40] —como ejemplo, considere el caso en el que hay dos agentes idénticos y solo un artículo que vale ${\displaystyle d^{*}\in {\mathcal {D}}}$ ${\displaystyle d^{*}={\underset {d\in {\mathcal {D}}}{\operatorname {argmax} }}\min _{i=1,\ldots ,n}\sum _{A\in {\mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}$100. Es fácil ver que en el contexto determinista el valor igualitario es0 , mientras que en el entorno estocástico es50 .
  • Dureza: Kawase y Sumita ^[40] demuestran que encontrar una asignación estocástica que maximice el bienestar igualitario es NP-difícil incluso cuando las utilidades de los agentes son todas aditivas al presupuesto ; y también, que es NP-difícil aproximar el bienestar igualitario a un factor mejor que incluso cuando todos los agentes tienen la misma función de utilidad submodular . ${\displaystyle 1-{\tfrac {1}{e}}}$
  • Algoritmo: Kawase y Sumita ^[40] presentan un algoritmo que, dado un algoritmo para encontrar una asignación determinista que aproxima el bienestar utilitario a un factor α , encuentra una asignación estocástica que aproxima el bienestar igualitario al mismo factor α .

Véase también

• Problema de cubrimiento de contenedores y problema de empaquetado de contenedores : dos problemas de optimización bien estudiados que pueden considerarse casos especiales de asignación indivisible de bienes y de asignación indivisible de tareas , respectivamente. Muchas técnicas utilizadas para estos problemas también son útiles en el caso de la asignación justa de artículos.
• Experimentos de división justa : incluye algunos estudios de casos y experimentos de laboratorio relacionados con la asignación justa de elementos.
• Armonía de alquiler : un problema de división justa en el que los elementos indivisibles y un costo total fijo deben dividirse simultáneamente.
• Asignación aleatoria justa : un problema de división justa sin dinero, en el que la imparcialidad se logra mediante la aleatorización.
• Problema de asignación de vivienda : un problema de división justa en el que cada agente debe recibir exactamente un objeto, sin transferencias monetarias ni aleatorización.
• Asignación de cursos : un problema de división justa en el que las plazas en los cursos universitarios deberían dividirse entre los estudiantes.
• Precio de la justicia : una medida general del equilibrio entre justicia y eficiencia, con algunos resultados sobre la configuración de la asignación de elementos.
• Problema de suma de subconjuntos justos
• Rompecabezas de la herencia de 17 animales

Referencias

1. Demko, Stephen; Hill, Theodore P. (1988-10-01). "Distribución equitativa de objetos indivisibles". Ciencias Sociales Matemáticas . 16 (2): 145–158. doi :10.1016/0165-4896(88)90047-9. ISSN  0165-4896.
2. Sylvain Bouveret y Yann Chevaleyre y Nicolas Maudet, "Asignación justa de bienes indivisibles". Capítulo 12 en: 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)
3. Barberà, S.; Bossert, W.; Pattanaik, PK (2004). "Clasificación de conjuntos de objetos". (PDF) . Manual de teoría de la utilidad . Springer US.
4. Sylvain Bouveret; Ulle Endriss; Jérôme Lang (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 . Consultado el 26 de agosto de 2016 .
5. Brams, Steven J.; Edelman, Paul H.; Fishburn, Peter C. (2003). "División justa de elementos indivisibles". Teoría y decisión . 55 (2): 147. doi :10.1023/B:THEO.0000024421.85722.0a. S2CID  153943630.
6. Brams, SJ (2005). "División justa y eficiente: ¿Ayudar a los más desfavorecidos o evitar la envidia?". Rationality and Society . 17 (4): 387–421. CiteSeerX 10.1.1.118.9114 . doi :10.1177/1043463105058317. S2CID  154808734. 
7. 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.
8. Budish, E. (2011). "El problema de asignación combinatoria: equilibrio competitivo aproximado a partir de ingresos iguales". Revista de economía política . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . doi :10.1086/664613. S2CID  154703357. 
9. Heinen, Tobías; Nguyen, Nhan-Tam; Rothe, Jörg (2015). "Equidad y utilitarismo ponderado por rangos en la asignación de recursos". Teoría de la decisión algorítmica . Apuntes de conferencias sobre informática. vol. 9346. pág. 521. doi :10.1007/978-3-319-23114-3_31. ISBN 978-3-319-23113-6.
10. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La justicia irrazonable del bienestar máximo de Nash (PDF) . Actas de la Conferencia ACM de 2016 sobre Economía y Computación - EC '16. p. 305. doi :10.1145/2940716.2940726. ISBN 9781450339360.
11. Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Un estudio de los resultados de aproximabilidad e inaproximabilidad para la optimización del bienestar social en la asignación de recursos multiagente". Anales de Matemáticas e Inteligencia Artificial . 68 (1–3): 65–90. CiteSeerX 10.1.1.671.3497 . doi :10.1007/s10472-012-9328-4. S2CID  6864410. 
12. Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Complejidad computacional y aproximabilidad de la optimización del bienestar social en la asignación de recursos multiagente". Agentes autónomos y sistemas multiagente . 28 (2): 256. doi :10.1007/s10458-013-9224-2. S2CID  442666.
13. Trung Thanh Nguyen; Jörg Rothe (2013). Optimización del bienestar social por ratio de envidia y Nash promedio en la asignación de recursos de múltiples agentes . AAMAS 13.
14. Sandomirskiy, Fedor; Segal-Halevi, Erel (mayo de 2022). "División justa eficiente con mínima compartición". Investigación de operaciones . 70 (3): 1762–1782. arXiv : 1908.01669 . doi :10.1287/opre.2022.2279. ISSN  0030-364X.
15. Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). "Reducción a la mitad por consenso para conjuntos de elementos". Matemáticas de la investigación de operaciones . 47 (4): 3357–3379. arXiv : 2007.06754 . doi :10.1287/moor.2021.1249. S2CID  246764981.
16. Misra, Neeldhara; Sethia, Aditi (2021). "La división justa es difícil incluso para los agentes amistosos". En Bureš, Tomáš; Dondi, Riccardo; Gamper, Johann; Guerrini, Giovanna; Jurdziński, Tomasz; Pahl, Claus; Sikora, Florian; Wong, Prudence WH (eds.). SOFSEM 2021: Teoría y práctica de la informática . Apuntes de clase en informática. Vol. 12607. Cham: Springer International Publishing. págs. 421–430. doi :10.1007/978-3-030-67731-2_31. ISBN 978-3-030-67731-2.
17. Bismuth, Samuel; Makarov, Vladislav; Segal-Halevi, Erel; Shapira, Dana (8 de noviembre de 2023), Partición de números con división , arXiv : 2204.11753
18. Bei, Xiaohui; Li, Zihao; Liu, Shengxin; Lu, Xinhang (5 de enero de 2021). "División justa de bienes mixtos divisibles e indivisibles". Inteligencia artificial . 293 103436. Elsevier. arXiv : 1911.07048 . doi :10.1016/j.artint.2020.103436.
19. Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang; Wang, Hongao (30 de junio de 2021). "Maximización de la equidad con bienes mixtos divisibles e indivisibles". Agentes autónomos y sistemas multiagente . 35 (2): 34. arXiv : 2002.05245 . doi :10.1007/s10458-021-09517-7. ISSN  1573-7454.
20. Bhaskar, Umang; Sricharan, AR; Vaish, Rohit (2021). "Sobre la ausencia aproximada de envidia para tareas indivisibles y recursos mixtos". DROPS-IDN/V2/Document/10.4230/LIPIcs.APPROX/RANDOM.2021.1 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi : 10.4230/LIPIcs.APPROX/RANDOM.2021.1 .
21. Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai (19 de agosto de 2023). "Mecanismos veraces y justos para la asignación de bienes mixtos divisibles e indivisibles". Actas de la 32.ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI '23. Macao, República Popular de China. págs. 2808–2816. doi :10.24963/ijcai.2023/313. ​​ISBN 978-1-956792-03-4.{{cite book}}: CS1 maint: location missing publisher (link)
22. Nishimura, Koichi; Sumita, Hanna (13 de agosto de 2023), Ausencia de envidia y máximo bienestar de Nash para bienes mixtos divisibles e indivisibles , arXiv : 2302.13342
23. Kawase, Yasushi; Nishimura, Koichi; Sumita, Hanna (8 de noviembre de 2023), Asignación justa con valoraciones binarias para bienes mixtos divisibles e indivisibles , arXiv : 2306.05986
24. Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang (2023-10-02), División justa con divisibilidad subjetiva , arXiv : 2310.00976
25. Li, Bo; Li, Zihao; Liu, Shengxin; Wu, Zekai (28 de abril de 2024), Asignación de bienes mixtos con una proporción personalizada de equidad e indivisibilidad , arXiv : 2404.18132
26. Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai; Tao, Yichen (2 de enero de 2024), Un paisaje completo al precio de la ausencia de envidia , arXiv : 2401.01516
27. Liu, Shengxin; Lu, Xinhang; Suzuki, Mashbat; Walsh, Toby (24 de marzo de 2024). "División de la feria mixta: una encuesta". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 38 (20): 22641–22649. arXiv : 2306.09564 . doi :10.1609/aaai.v38i20.30274. ISSN  2374-3468.
28. Brams, Steven J.; Kaplan, Todd R. (2004). "Dividir lo indivisible". Revista de política teórica . 16 (2): 143. doi :10.1177/0951629804041118. hdl : 10036/26974 . S2CID  154854134.
29. Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (23 de marzo de 2017). "Equilibrio competitivo con bienes indivisibles y presupuestos genéricos". arXiv : 1703.08150 [cs.GT].
30. Segal-Halevi, Erel (9 de julio de 2018). "Equilibrio competitivo para casi todos los ingresos". Actas de AAMAS 2018. Aamas '18. Fundación Internacional para Agentes Autónomos y Sistemas Multiagente. págs. 1267–1275.
31. Chakraborty, Mithun; Igarashi, Ayumi; Suksompong, Warut; Zick, Yair (16 de agosto de 2021). "Libreza ponderada de envidia en la asignación de elementos indivisibles". ACM Transactions on Economics and Computation . 9 (3): 18:1–18:39. arXiv : 1909.10502 . doi :10.1145/3457166. ISSN  2167-8375. S2CID  202719373.
32. Chakraborty, Mithun; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (1 de diciembre de 2021). "Selección de secuencias y monotonía en la división justa ponderada". Inteligencia artificial . 301 : 103578. arXiv : 2104.14347 . doi :10.1016/j.artint.2021.103578. ISSN  0004-3702. S2CID  233443832.
33. Chakraborty, Mithun; Segal-Halevi, Erel; Suksompong, Warut (28 de junio de 2022). "Revisión de las nociones de equidad ponderada para elementos indivisibles". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 36 (5): 4949–4956. arXiv : 2112.04166 . doi : 10.1609/aaai.v36i5.20425 . ISSN  2374-3468. S2CID  244954009.
34. Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (15 de noviembre de 2021). "Asignaciones de participación justa para agentes con derechos arbitrarios". arXiv : 2103.04304 [cs.GT].
35. 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.
36. Garg, Jugal; Kulkarni, Pooja; Murhekar, Aniket (2021). Bojańczy, Miko\laj; Chekuri, Chandra (eds.). "Sobre asignaciones justas y eficientes de bienes públicos indivisibles". 41.ª Conferencia anual de la IARCS sobre fundamentos de la tecnología del software y la informática teórica (FSTTCS 2021) . Leibniz International Proceedings in Informatics (LIPIcs). 213. Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 22:1–22:19. doi : 10.4230/LIPIcs.FSTTCS.2021.22 . ISBN. 978-3-95977-215-0.S2CID236154847  .​
37. Fain, Brandon; Munagala, Kamesh; Shah, Nisarg (11 de junio de 2018). "Asignación justa de bienes públicos indivisibles". Actas de la Conferencia ACM de 2018 sobre Economía y Computación . EC '18. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 575–592. doi :10.1145/3219166.3219174. ISBN 978-1-4503-5829-3. Número de identificación del sujeto  3331859.
38. Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2017). "Toma de decisiones públicas justa". En Daskalakis, Constantinos; Babaioff, Moshe; Moulin, Hervé (eds.). Actas de la Conferencia ACM 2017 sobre Economía y Computación, EC '17, Cambridge, MA, EE. UU., 26-30 de junio de 2017. {ACM}. pp. 629–646. arXiv : 1611.04034 . doi :10.1145/3033274.3085125. ISBN 978-1-4503-4527-9.
39. Igarashi, Ayumi; Lackner, Martin; Nardi, Oliviero; Novaro, Arianna (4 de abril de 2023). "Asignación justa repetida de elementos indivisibles". arXiv : 2304.01644 [cs.GT].
40. Kawase, Yasushi; Sumita, Hanna (2020). "Sobre la asignación estocástica justa de máximos y mínimos de bienes indivisibles". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 2070–2078. doi : 10.1609/AAAI.V34I02.5580 . S2CID  214407880.