Hispanopedia Wiki
Articulo de referencia

Asignación justa de artículos

La asignación equitativa de artículos es un tipo de problema de división equitativa en el que los artículos a dividir son discretos en lugar de continuos. Los artículos deben di...

Hispanopedia WikiContenido en espanolLectura gratuita

La asignación equitativa de artículos es un tipo de problema de división equitativa en el que los artículos a dividir son discretos en lugar de continuos. Los artículos deben dividirse entre varios socios que potencialmente los valoran de manera diferente , y cada artículo debe entregarse en su totalidad a una sola persona. [ 1 ] Esta situación surge en diversos escenarios de la vida real:

La indivisibilidad de los bienes implica que una división justa puede no ser posible. Como ejemplo extremo, si solo hay un bien (por ejemplo, una casa), debe entregarse a un solo socio, lo cual no es justo para los demás. Esto contrasta con el problema del reparto equitativo de un pastel , donde el dividendo es divisible y siempre existe una división justa. En algunos casos, el problema de la indivisibilidad puede mitigarse mediante pagos monetarios o 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 deberá 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 equitativa.

Preferencias

Preferencias combinatorias

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

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

El primer problema motiva el uso de la utilidad ordinal en lugar de la utilidad cardinal . En el modelo ordinal, cada socio solo debe expresar una clasificación sobre la2metro{\displaystyle 2^{m}}diferentes combinaciones, es decir, determinar cuál es la mejor, cuál la segunda mejor, y así sucesivamente. Esto puede ser más sencillo que calcular cifras exactas, pero sigue siendo difícil si la cantidad de elementos es grande.

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

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

Bajo supuestos adecuados, es posible elevar las preferencias sobre artículos a preferencias sobre 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 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 (es decir, no son bienes sustitutivos ni 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 ciertas 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; por ejemplo, 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 participante siempre puede elegir un "elemento preferible" del conjunto de elementos sobre la mesa, y esta elección es independiente de los demás elementos que pueda tener. Esta propiedad se utiliza en algunos algoritmos de asignación justa que se describirán a continuación. [ 2 ] : 287–288

Lenguajes de representación de preferencias compactas

Se han desarrollado lenguajes de representación de preferencias compactos como un compromiso entre la expresividad completa de las preferencias combinatorias y la simplicidad de las preferencias aditivas. Proporcionan una representación concisa 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 participante informa un valor para cada paquete de tamaño máximo 2. El valor de un paquete se calcula sumando los valores de los elementos individuales que lo componen y sumando los valores de los pares que lo conforman. Generalmente, 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 cualquier 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 participante describe conjuntos de datos mediante una fórmula de lógica de primer orden y puede asignar un valor a cada fórmula. Por ejemplo, un participante 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 conjuntos: x, xy, xz, yz, xyz.
  • Lenguajes de puja : se han estudiado numerosos lenguajes para representar preferencias combinatorias en el contexto de las subastas combinatorias . Algunos de estos lenguajes pueden adaptarse al entorno de asignación de artículos.

Criterios de equidad

Criterios de garantía individual

Un criterio de garantía individual es un criterio que debe cumplirse para cada socio, siempre que este declare verazmente sus preferencias. A continuación se presentan cinco de estos criterios, ordenados del más débil al más fuerte (suponiendo que las valoraciones son aditivas): [ 7 ]

Participación de Maximin

La participación maximin (también llamada garantía de participación justa máxima-mínima) de un agente es el paquete más preferido que podría garantizarse como divisor en un sistema de divide y elige frente a oponentes adversarios. Una asignación se denomina MMS-justa si cada agente recibe un paquete que prefiere débilmente sobre su MMS. [ 8 ]

Reparto justo proporcional (PFS)

La parte proporcional justa de un agente es 1/ n de su utilidad respecto al conjunto total de bienes. Una asignación se denomina proporcional si cada agente recibe una cesta de bienes cuyo valor es al menos igual a su parte proporcional justa.

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

La participación justa min-max 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 justa mFS si todos los agentes reciben un paquete que prefieren débilmente sobre su mFS. [ 7 ] La justicia mFS 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 objetaría una asignación solo si en todas las particiones hay un paquete que prefiere fuertemente sobre su paquete actual. Una asignación es justa mFS si y solo si ningún agente objeta, es decir, para cada agente hay una partición en la que todos los paquetes son débilmente peores que su parte actual.

Para cada agente con utilidad subaditiva , el mFS vale al menos1/norte{\displaystyle 1/n}Por lo tanto, cada asignación justa de mFS es proporcional. Para cada agente con utilidad superaditiva , el MMS vale como máximo1/norte{\displaystyle 1/n}Por lo tanto, toda 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 ]

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 elementos 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 artículo a cada agente es justa según el sistema MMS.
  • Toda asignación que dé el primer y el segundo artículo a Bob y Carl y el tercer artículo a Alice es proporcional.
  • Ninguna asignación es justa para mFS.

Las implicaciones anteriores no se cumplen cuando las valoraciones de los agentes no son subaditivas/superaditivas. [ 9 ]

Ausencia de envidia (AE)

Cada agente prefiere débilmente su propio conjunto de artículos a cualquier otro. Toda asignación libre de envidia de todos los artículos es justa según el criterio mFS; esto se deduce directamente de las definiciones ordinales y no depende de la aditividad. Si las valoraciones son aditivas, entonces una asignación EF también es proporcional y justa según el criterio MMS. De lo contrario, una asignación EF puede no ser proporcional e incluso no ser MMS. [ 9 ]

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

  • Libre de envidia excepto 1 (EF1) : para cada par de agentes A y B, si se elimina 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 hacia B es como máximo el valor de un solo elemento). Bajo la monotonicidad, siempre existe una asignación EF1.
  • Ausencia de envidia excepto el más barato (EFx) : Para cada par de agentes A y B, si se elimina del conjunto de B el elemento menos valioso para A, entonces A no envidia a B. EFx es estrictamente más fuerte que EF1. Se desconoce si las asignaciones EFx existen siempre.

Equilibrio competitivo a partir de la igualdad de ingresos (CEEI)

Este criterio se basa en el siguiente argumento: el proceso de asignación debe considerarse como una búsqueda de 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 EF independientemente de la aditividad. Cuando las preferencias de los agentes son aditivas y estrictas (cada cesta 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 basándose en una función de bienestar social dada :

  • El bienestar social igualitario es la utilidad mínima de un solo agente. Una asignación de elementos se denomina óptima igualitaria si alcanza el máximo bienestar igualitario posible, es decir, si maximiza la utilidad del agente más pobre. Dado que puede haber varias asignaciones diferentes que maximicen la utilidad mínima, la optimalidad igualitaria se suele refinar a la optimalidad leximin : del subconjunto de asignaciones que maximizan la utilidad mínima, se seleccionan aquellas que maximizan la segunda utilidad mínima, luego la tercera, 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 poseen 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 el sentido de Pareto .

Algoritmos de asignación

En las páginas dedicadas a criterios de equidad específicos se analizan diversos algoritmos para la asignación justa de elementos:

Entre lo divisible y lo indivisible

Los estudios tradicionales sobre asignación equitativa parten de la base de que todos los elementos son divisibles o indivisibles. Algunos estudios recientes analizan situaciones en las que la distinción entre divisible e indivisible es más difusa.

Limitar la cantidad de veces que se comparte

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

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

  • Sandomirskiy y Segal-Halevi [ 14 ] estudian la minimización de la compartición en asignaciones que son justas y fraccionalmente Pareto eficientes (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 enumerarlas todas 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-difícil. Presentan evidencia empírica de que, en casos realistas, a menudo existe una asignación con comparticiones sustancialmente menores 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 fPO con 0 participaciones. También demuestran un enfoque alternativo para enumerar grafos de consumo distintos para asignaciones con un número pequeño de participaciones.
  • Goldberg, Hollender, Igarashi, Manurangsi y Suksompong [ 15 ] estudian la minimización de compartición en la división de consenso . Demuestran que, para agentes con utilidades aditivas , existe un algoritmo de tiempo polinomial para calcular una división de consenso con a lo sumo n comparticiones, y para calcular una división de consenso k con a lo sumo ( k − 1) n cortes. Pero la minimización de 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 división de consenso cuando las utilidades de los agentes se extraen de distribuciones probabilísticas. Para agentes con utilidades monótonas no aditivas, la división de 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 planificación de máquinas idénticas , y también el entorno más general de planificación de máquinas uniformes . Estudian la complejidad de 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 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.
  • Bismuth, Bliznets y Segal-Halevi [ 18 ] también estudian la complejidad del tiempo de ejecución para decidir la existencia de una asignación justa con s participaciones u objetos compartidos, donde las valoraciones no son idénticas pero tienen otras propiedades estructurales (valoraciones binarias, valoraciones binarias generalizadas de suma igual o no degeneradas).

Mezcla de bienes divisibles e indivisibles

  • Bei, Li, Liu, Liu y Lu [ 19 ] estudian una mezcla de bienes indivisibles y divisibles (objetos con utilidades positivas). Definen una aproximación a la ausencia de envidia llamada EFM (ausencia de envidia para artículos mixtos), que generaliza tanto la ausencia de envidia para artículos divisibles como EF1 para artículos indivisibles. Demuestran que siempre existe una asignación EFM para cualquier número de agentes con valoraciones aditivas. Presentan algoritmos eficientes para calcular 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 épsilon .
  • Bei, Liu, Lu y Wang [ 20 ] estudian el mismo escenario, centrándose en la equidad de participación maximin . Proponen un algoritmo que calcula una asignación MMS aproximada 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 MMS.
  • Bhaskar, Sricharan y Vaish [ 21 ] estudian una mezcla de tareas indivisibles (objetos con utilidades negativas) y un pastel divisible (con utilidad positiva). Presentan un algoritmo para encontrar una asignación EFM en dos casos especiales: cuando cada agente tiene la misma clasificación de preferencia 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 [ 22 ] estudian mecanismos veraces para EFM. Demuestran que, en general, no existe un 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 [ 23 ] estudian las propiedades de la asignación de bienestar de Nash máximo (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 de EFM, que denominan "ausencia de envidia hasta cualquier bien para bienes mixtos". Sus resultados son válidos no solo para el bienestar de Nash máximo, sino también para una noción general de equidad basada en la minimización de una función simétrica estrictamente convexa. Para valoraciones aditivas generales, demuestran que una asignación MNW satisface una aproximación EF más débil que la de EFM.
  • Kawase, Nishimura y Sumita [ 24 ] 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 igualitaria de artículos 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 resoluble en tiempo polinomial. Demuestran que, con bienes mixtos, el problema es NP-difícil 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 polinomial.
  • Bei, Liu y Lu [ 25 ] estudian un escenario más general, en el que el mismo objeto puede ser divisible para algunos agentes e indivisible para otros. Demuestran 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 de 1/2-MMS. También demuestran que EFM es incompatible con la no desperdicia.
  • Li, Li, Liu y Wu [ 26 ] estudian un escenario en el que cada agente puede tener una "proporción de indivisibilidad" diferente (= proporción de elementos indivisibles). A cada agente se le garantiza una asignación que es EF/PROP salvo una fracción de un elemento, donde la fracción depende de la proporción de indivisibilidad del agente. Los resultados son ajustados salvo una constante para EF y asintóticamente ajustados para PROP.
  • Li, Liu, Lu, Tao y Tao [ 27 ] estudian el precio de la equidad en la asignación de artículos tanto indivisibles como mixtos. Proporcionan límites para el precio de EF1, EFx, EFM y EFxM. Ofrecen límites ajustados para dos agentes y límites asintóticamente ajustados para n agentes, tanto para utilidades escaladas como no escaladas.

Liu, Lu, Suzuki y Walsh [ 28 ] analizan algunos resultados recientes sobre ítems 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 en las asignaciones de EFM?
  3. ¿Existen algoritmos limitados o incluso finitos para calcular las asignaciones de EFM en el modelo de consulta de Robertson-Webb ?
  4. ¿Siempre existe una asignación para gastos médicos especiales cuando hay tareas indivisibles y un pastel?
  5. En términos más generales: ¿existe siempre una asignación 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, 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. [ 29 ] Es habitual suponer que cada partido debería recibir ministerios en proporción al 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; [ 30 ] [ 31 ]
  • Nociones basadas en la ausencia de envidia ponderada; [ 32 ] [ 33 ] [ 34 ]
  • Nociones basadas en la participación justa ponderada; [ 35 ]

Asignación a grupos

En esta variante, los paquetes se asignan a grupos de agentes en lugar de a individuos. Algunos ejemplos de uso comunes son: la distribución de herencias entre familias o la asignación de instalaciones entre departamentos universitarios. 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 unitarios.

En los grupos, puede ser imposible garantizar la imparcialidad unánime (imparcialidad a los ojos de todos los agentes de cada grupo), por lo que a menudo se opta por la imparcialidad democrática (imparcialidad a los ojos, por ejemplo, de al menos la mitad de los agentes de cada grupo). [ 36 ]

Asignación de bienes públicos

En esta variante, cada elemento proporciona utilidad no solo a un agente, sino a todos los agentes. Diferentes agentes pueden atribuir diferentes utilidades al mismo elemento. El grupo debe elegir un subconjunto de elementos que cumplan 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 esta última el número de candidatos electos 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 debe 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. [ 37 ]
  • El coste 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 reducido posible, siempre y cuando 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. [ 38 ]

La asignación de bienes privados puede considerarse un caso especial de asignación de bienes públicos: dado un problema de bienes privados con n agentes y m artículos, donde el agente i valora el artículo j en v ij , se construye un problema de bienes públicos con n · m artículos, donde el agente i valora cada artículo i,j en v ij y los demás artículos en 0. El artículo i,j representa esencialmente la decisión de dar el artículo 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 . [ 37 ]

Los conceptos de solución comunes para la asignación de bienes públicos son la estabilidad central (que implica tanto eficiencia de Pareto como proporcionalidad), [ 38 ] bienestar máximo de Nash, optimalidad leximin y proporcionalidad hasta un elemento. [ 37 ]

Toma de decisiones públicas

En esta variante, varios agentes deben aceptar decisiones sobre varios asuntos. Un caso de uso común es una familia que debe decidir qué actividad realizar cada día (aquí cada asunto es un día). Cada agente asigna diferentes utilidades a las distintas opciones en cada asunto. La configuración clásica de asignación de elementos corresponde al caso especial en el que cada asunto corresponde a un elemento, cada opción de decisión corresponde a dar ese elemento a un agente en particular, y las utilidades de los agentes son cero para todas las opciones en las que el elemento se da a otra persona. En este caso, la 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 al elegir la mejor opción en cada asunto. La proporcionalidad puede ser inalcanzable, pero PROP1 es alcanzable mediante la asignación de elementos Round-robin . [ 39 ]

Asignación repetida

A menudo, se asignan repetidamente los mismos elementos. Por ejemplo, las tareas domésticas recurrentes. Si el número de repeticiones es múltiplo del número de agentes, entonces es posible encontrar en tiempo polinomial una secuencia de asignaciones libre de envidia y completa, y en tiempo exponencial una secuencia proporcional y óptima de Pareto. Sin embargo, una secuencia libre de envidia y óptima 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 de Pareto. [ 40 ]

Asignaciones estocásticas de bienes indivisibles

Las asignaciones estocásticas de bienes indivisibles [ 41 ] 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:

A={(A1,…,Anorte)∣∀i∈[norte]:Ai⊆[metro],∀i≠j∈[norte]:Ai∩Aj=∅,∪i=1norteAi=[metro]}{\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 conjuntoA{\displaystyle {\mathcal {A}}}. 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:

D={d∣pagd:A→[0,1],∑A∈Apagd(A)=1}{\displaystyle {\mathcal {D}}=\{d\mid p_{d}\colon {\mathcal {A}}\to [0,1],\sum _{A\in {\mathcal {A}}}p_{d}(A)=1\}}

Cada agente tiene dos funciones relacionadas: una función de utilidad asociada a una asignación determinista.túi:A→R+{\displaystyle u_{i}\colon {\mathcal {A}}\to \mathbb {R} _{+}}y una función de utilidad esperada asociada a una asignación estocástica.mii:D→R+{\displaystyle E_{i}\colon {\mathcal {D}}\to \mathbb {R} _{+}}que se define segúntúi{\displaystyle u_{i}}como sigue:

mii(d)=∑A∈Apagd(A)⋅túi(A){\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 un entorno determinista también pueden considerarse en un entorno estocástico:

  • Regla utilitarista : esta regla establece que la sociedad debe elegir la solución que maximice la suma de las utilidades. Es decir, elegir una asignación estocástica.d∗∈D{\displaystyle d^{*}\in {\mathcal {D}}}que maximiza el bienestar utilitario :d∗=argmaxd∈D∑i=1norte∑A∈A(pagd(A)⋅túi(A)){\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)} Kawase y Sumita [ 41 ] muestran que la maximización del bienestar utilitario en el entorno estocástico siempre se puede lograr con una asignación determinista . La razón es que el valor utilitario de la asignación deterministaA∗=argmaxA∈A:pagd∗(A)>0∑i=1nortetúi(A){\displaystyle A^{*}={\underset {A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}{\operatorname {argmax} }}\sum _{i=1}^{n}u_{i}(A)}es al menos el valor utilitario ded∗{\displaystyle d^{*}}:∑i=1norte∑A∈A(pagd∗(A)⋅túi(A))=∑A∈Apagd∗(A)∑i=1nortetúi(A)≤máximoA∈A:pagd∗(A)>0∑i=1nortetúi(A){\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 establece 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.d∗∈D{\displaystyle d^{*}\in {\mathcal {D}}}que maximiza el bienestar igualitario :d∗=argmaxd∈Dmini=1,…,norte∑A∈A(pagd(A)⋅túi(A)){\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)} A diferencia de la regla utilitarista, aquí, el entorno estocástico permite a la sociedad alcanzar un mayor valor [ 41 ] — como ejemplo, considérese el caso en el que hay dos agentes idénticos y solo un elemento que vale100. Es fácil ver que en el entorno determinista el valor igualitario es0 , mientras que en el entorno estocástico es50 .
    • Dificultad: Kawase y Sumita [ 41 ] 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 respecto al presupuesto ; y también, que es NP-difícil aproximar el bienestar igualitario a un factor mejor que1−1mi{\displaystyle 1-{\tfrac {1}{e}}}incluso cuando todos los agentes tienen la misma función de utilidad submodular .
    • Algoritmo: Kawase y Sumita [ 41 ] presentan un algoritmo que, dado un algoritmo para encontrar una asignación determinista que aproxime el bienestar utilitario a un factor α , encuentra una asignación estocástica que aproxime el bienestar igualitario al mismo factor α .

Véase también

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. 1 2 3 Sylvain Bouveret, 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.
  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 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". Theory and Decision . 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. 1 2 3 4 5 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 . 
  8. ↑ Budish, E. (2011). "El problema de la asignación combinatoria: equilibrio competitivo aproximado a partir de ingresos iguales". Journal of Political Economy . 119 (6): 1061– 1103. CiteSeerX 10.1.1.357.9766 . doi : 10.1086/664613 . S2CID 154703357 .  
  9. 1 2 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. 1 2 Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La equidad irrazonable del bienestar máximo de Nash (PDF) . Actas de la Conferencia ACM de 2016 sobre Economía y Computación - EC '16. pág. 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". Annals of Mathematics and Artificial Intelligence . 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". Autonomous Agents and Multi-Agent Systems . 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 mediante la relación de envidia y el promedio de Nash en la asignación de recursos multiagente . AAMAS 13.
  14. 1 2 Sandomirskiy, Fedor; Segal-Halevi, Erel (mayo de 2022). "División justa y eficiente con reparto mínimo" . Operations Research . 70 (3): 1762– 1782. arXiv : 1908.01669 . doi : 10.1287/opre.2022.2279 . ISSN 0030-364X . 
  15. 1 2 Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). "Consensus Halving for Sets of Items". Mathematics of Operations Research . 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 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 . Lecture Notes in Computer Science. Vol. 12607. Cham: Springer International Publishing. pp. 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 (2023-11-08), Partición asimétrica de números con objetivos de división e intervalo , arXiv : 2204.11753
  18. ↑ Bismuth, Samuel; Bliznets, Ivan; Segal-Halevi, Erel (2024). "División justa con reparto limitado: valoraciones binarias y no degeneradas". En Schäfer, Guido; Ventre, Carmine (eds.). Teoría de juegos algorítmicos: 17.º Simposio Internacional, SAGT 2024, Ámsterdam, Países Bajos, 3-6 de septiembre de 2024, Actas . Lecture Notes in Computer Science. Springer. pp. 89-107 . doi : 10.1007/978-3-031-71033-9_6 . 
  19. ↑ 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 .
  20. ↑ Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang; Wang, Hongao (30 de junio de 2021). "Maximin equidad con bienes mixtos divisibles e indivisibles" . Autonomous Agents and Multi-Agent Systems . 35 (2): 34. arXiv : 2002.05245 . doi : 10.1007/s10458-021-09517-7 . ISSN 1573-7454 . 
  21. ↑ 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 . Leibniz International Proceedings in Informatics (LIPIcs). 207. Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 1:1–1:23. doi : 10.4230/LIPIcs.APPROX/RANDOM.2021.1 . ISBN 978-3-95977-207-5.
  22. ↑ Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai (19 de agosto de 2023). «Mecanismos justos y veraces para la asignación de bienes mixtos divisibles e indivisibles» . Actas de la Trigésimo Segunda Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI '23. Macao, República Popular China. págs. 2808–2816 . doi : 10.24963/ijcai.2023/313 . ​​ISBN  978-1-956792-03-4.{{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  23. ↑ Nishimura, Koichi; Sumita, Hanna (2025), "Ausencia de envidia y bienestar máximo de Nash para bienes mixtos divisibles e indivisibles", Mathematical Social Sciences 102449, arXiv : 2302.13342 , doi : 10.1016/j.mathsocsci.2025.102449
  24. ↑ Kawase, Yasushi; Nishimura, Koichi; Sumita, Hanna (2023-11-08), Asignación justa con valoraciones binarias para bienes mixtos divisibles e indivisibles , arXiv : 2306.05986
  25. ↑ Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang (2025), "División justa con divisibilidad subjetiva", Games and Economic Behavior , 151 : 127–147 , arXiv : 2310.00976 , doi : 10.1016/j.geb.2025.03.004
  26. ↑ Li, Bo; Li, Zihao; Liu, Shengxin; Wu, Zekai (2024-04-28), Asignación de bienes mixtos con equidad personalizada y ratio de indivisibilidad , arXiv : 2404.18132
  27. ^ 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
  28. ↑ Liu, Shengxin; Lu, Xinhang; Suzuki, Mashbat; Walsh, Toby (24 de marzo de 2024). "División justa mixta: una revisión" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 38 (20): 22641– 22649. arXiv : 2306.09564 . doi : 10.1609/aaai.v38i20.30274 . ISSN 2374-3468 . 
  29. ↑ Brams, Steven J.; Kaplan, Todd R. (2004). "Dividiendo lo indivisible". Journal of Theoretical Politics . 16 (2): 143. doi : 10.1177/0951629804041118 . hdl : 10036/26974 . S2CID 154854134 . 
  30. ↑ Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (2017-03-23). ​​"Equilibrio competitivo con bienes indivisibles y presupuestos genéricos". arXiv : 1703.08150 [ cs.GT ].
  31. ↑ Segal-Halevi, Erel (09-07-2018). "Equilibrio competitivo para casi todos los niveles de ingresos" . Actas de AAMAS 2018. Aamas '18. Fundación Internacional para Agentes Autónomos y Sistemas Multiagente. págs. 1267–1275 . 
  32. ↑ Chakraborty, Mithun; Igarashi, Ayumi; Suksompong, Warut; Zick, Yair (2021-08-16). "Weighted Envy-freeness in Indivisible Item Allocation" . ACM Transactions on Economics and Computation . 9 (3): 18:1–18:39. arXiv : 1909.10502 . doi : 10.1145/3457166 . ISSN 2167-8375 . S2CID 202719373 .  
  33. ↑ Chakraborty, Mithun; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (2021-12-01). "Selección de secuencias y monotonicidad 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 .  
  34. ↑ Chakraborty, Mithun; Segal-Halevi, Erel; Suksompong, Warut (2022-06-28). "Nociones de equidad ponderada para elementos indivisibles revisadas" . 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 .  
  35. ↑ Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2021-11-15). "Asignaciones de participación justa para agentes con derechos arbitrarios". arXiv : 2103.04304 [ cs.GT ].
  36. ↑ 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 .  
  37. 1 2 3 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) . Actas Internacionales Leibniz en Informática (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. S2CID 236154847 . 
  38. 1 2 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. S2CID 3331859 ​​. 
  39. ↑ Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2017). «Toma de decisiones públicas justas». En Daskalakis, Constantinos; Babaioff, Moshe; Moulin, Hervé (eds.). Actas de la Conferencia ACM de Economía y Computación de 2017, EC '17, Cambridge, MA, EE. UU., 26-30 de junio de 2017. {ACM}. págs. 629–646 . arXiv : 1611.04034 . doi : 10.1145/3033274.3085125 . ISBN  978-1-4503-4527-9.
  40. ↑ Igarashi, Ayumi; Lackner, Martin; Nardi, Oliviero; Novaro, Arianna (2023-04-04). "Repeated Fair Allocation of Indivisible Items". arXiv : 2304.01644 [ cs.GT ].
  41. 1 2 3 4 5 Kawase, Yasushi; Sumita, Hanna (2020). "Sobre la asignación estocástica justa Max-Min de bienes indivisibles" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 2070– 2078. doi : 10.1609/AAAI.V34I02.5580 . S2CID 214407880 . 
Lecturas relacionadas
6 articulos
JustoJustoUna feria (arcaicamente: faire o fayre ) es una reunión de personas para una variedad de actividades comerciales o de entretenimiento. Las ferias s...División justaLa división justa es el problema de la teoría de juegos que consiste en dividir un conjunto de recursos entre varias personas que tienen derecho a ...Funciones de utilidad sobre bienes indivisiblesAlgunas ramas de la economía y la teoría de juegos se ocupan de bienes indivisibles , es decir, artículos discretos que solo pueden intercambiarse ...Juego de intercambio de regalosJuego de intercambio de regalosEl juego del intercambio de regalos, también conocido como el dilema del intercambio de regalos , es un juego económico común introducido por Georg...Intercambio de regalos de elefante blancoIntercambio de regalos de elefante blancoUn intercambio de regalos de elefante blanco , [1] Yankee swap [2] o Dirty Santa [3] [nb 1] es un juego de fiesta en el que se intercambian regalos...Problema de asignaciónProblema de asignaciónEl problema de asignación es un problema fundamental de optimización combinatoria . En su forma más general, el problema es el siguiente: