El derecho en división justa describe la proporción de los recursos o bienes a dividir que un jugador puede esperar recibir. En muchos entornos de división justa, todos los agentes tienen los mismos derechos , lo que significa que cada agente tiene derecho a 1/ n del recurso. Pero hay entornos prácticos en los que los agentes tienen diferentes derechos . Algunos ejemplos son:
La idea se basa en la idea normal de derecho . Los derechos se pueden determinar acordando un juego cooperativo y utilizando su valor como derecho.
Cuando los agentes tienen iguales derechos, es razonable exigir que la solución satisfaga el axioma de anonimato (también llamado: simetría), es decir, los agentes son tratados sólo por sus valoraciones y no por sus nombres. Por el contrario, cuando los agentes tienen diferentes derechos, el anonimato ya no es válido y las soluciones deben ser asimétricas .
Se han estudiado varios problemas de división equitativa con diferentes derechos.
Incluso cuando sólo se va a dividir dinero y se ha especificado una cantidad fija para cada destinatario, el problema puede ser complejo. Las cantidades especificadas pueden ser mayores o menores que la cantidad de dinero, y entonces será necesario repartir las ganancias o pérdidas. La regla proporcional se utiliza normalmente en el derecho hoy en día y es el supuesto por defecto en la teoría de la quiebra . Sin embargo, a menudo se utilizan otras reglas, por ejemplo:
El Talmud tiene una serie de ejemplos en los que los derechos no se deciden de forma proporcional.
Todas estas soluciones pueden modelarse mediante juegos cooperativos . El problema de la división de bienes tiene una amplia literatura y Robert J. Aumann y Michael Maschler le dieron por primera vez una base teórica en la teoría de juegos en 1985. [6] Véase Regla de la prenda en disputa .
Cortar el pastel de manera justa es el problema de dividir un recurso continuo heterogéneo. Siempre existe un reparto proporcional respecto de los distintos derechos. Las dos preguntas principales de la investigación son (a) ¿cuántos cortes se requieren para una división justa? (b) ¿cuántas consultas se necesitan para calcular una división? Ver:
Los entornos de computación en la nube requieren dividir múltiples recursos divisibles y homogéneos (por ejemplo, memoria o CPU) entre los usuarios, donde cada usuario necesita una combinación diferente de recursos. [7] El contexto en el que los agentes pueden tener diferentes derechos ha sido estudiado por [8] y. [9]
En las democracias parlamentarias con representación proporcional , cada partido tiene derecho a escaños en proporción a su número de votos. En los sistemas de circunscripciones múltiples, cada circunscripción tiene derecho a escaños en proporción a su población. Se trata de un problema de dividir elementos indivisibles idénticos (los puestos) entre agentes con diferentes derechos. Se llama problema de reparto .
La asignación de escaños según el tamaño de la población puede dejar a los pequeños distritos sin voz alguna. La solución más sencilla es tener distritos electorales del mismo tamaño. A veces, sin embargo, esto puede resultar imposible, por ejemplo en la Unión Europea o los Estados Unidos . Garantizar que el "poder de voto" sea proporcional al tamaño de los distritos electorales es un problema de derechos.
Hay varios métodos que calculan el poder de voto para distritos electorales de diferentes tamaños o ponderaciones. Los principales son el índice de poder de Shapley-Shubik , el índice de poder de Banzhaf . Estos índices de poder suponen que los distritos electorales pueden unirse de cualquier forma aleatoria y aproximarse a la raíz cuadrada de la ponderación dada por el método de Penrose . Esta suposición no se corresponde con la práctica real y se puede argumentar que los grupos más grandes reciben un trato injusto por parte de ellos.
En el entorno más complejo de la asignación justa de artículos , hay múltiples artículos diferentes con valores posiblemente diferentes para diferentes personas.
Aziz, Gaspers, Mackenzie y Walsh [10] : la sección 7.2 define la proporcionalidad y la ausencia de envidia para agentes con diferentes derechos, cuando los agentes revelan sólo una clasificación ordinal de los elementos, en lugar de sus funciones de utilidad completas. Presentan un algoritmo de tiempo polinomial para comprobar si existe una asignación que sea posiblemente proporcional (proporcional según al menos un perfil de utilidad consistente con las clasificaciones de agentes), o necesariamente proporcional (proporcional según todos los perfiles de utilidad consistentes con las clasificaciones).
Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin, Seddighin y Yami [11] definieron la participación máxima ponderada (WMMS) como una generalización de la participación maximina a agentes con diferentes derechos. Demostraron que la mejor garantía multiplicativa alcanzable para el WMMS es 1/ n en general, y 1/2 en el caso especial en el que el valor de cada bien para cada agente es como máximo el WMMS del agente. Aziz, Chan y Li [12] adaptaron la noción de WMMS a las tareas del hogar (elementos con utilidades negativas). Demostraron que, incluso para dos agentes, es imposible garantizar más de 4/3 del WMMS (tenga en cuenta que con las tareas domésticas, las proporciones de aproximación son mayores que 1, y cuanto más pequeño, mejor). Presentan un algoritmo de aproximación 3/2-WMMS para dos agentes y un algoritmo WMMS para n agentes con valoraciones binarias. También definen el OWMMS, que es la aproximación óptima de WMMS que se puede lograr en el caso dado. Presentan un algoritmo de tiempo polinomial que logra una aproximación de 4 factores del OWMMS.
El WMMS es una noción cardinal en el sentido de que, si las utilidades cardinales de un agente cambian, entonces el conjunto de paquetes que satisfacen el WMMS para el agente puede cambiar. Babaioff, Nisan y Talgam-Cohen [13] introdujeron otra adaptación del MMS para agentes con diferentes derechos, que se basa únicamente en la clasificación ordinal de los paquetes del agente. Muestran que esta noción de equidad se logra mediante un equilibrio competitivo con diferentes presupuestos, donde los presupuestos son proporcionales a los derechos. Chakraborty, Segal-Halevi y Suksompong denominan esta noción de equidad Ordinal Maximin Share (OMMS). [14] Segal-Halevi estudia más a fondo la relación entre varias aproximaciones ordinales de MMS. [15] [16]
Babaioff, Ezra y Feige [17] presentan otra noción ordinal, más fuerte que OMMS, a la que llaman AnyPrice Share (APS) . Muestran un algoritmo de tiempo polinomial que alcanza una fracción de 3/5 del APS.
Aziz, Moulin y Sandomirskiy [18] presentan un algoritmo de tiempo fuertemente polinomial que siempre encuentra una asignación óptima de Pareto y WPROP(0,1) para agentes con diferentes derechos y valoraciones arbitrarias (positivas o negativas).
Hasta ahora, las flexibilizaciones del FEM se han estudiado sólo para bienes. Chakraborty, Igarashi y Suksompong [19] introdujeron el algoritmo round-robin ponderado para WEF(1,0). En un trabajo de seguimiento, Chakraborty, Schmidt-Kraepelin y Suksompong generalizaron el algoritmo round-robin ponderado a secuencias generales de selección y estudiaron varias propiedades de monotonicidad de estas secuencias.
En el problema de la asignación justa de bienes y dinero , las transferencias monetarias pueden utilizarse para lograr la equidad exacta de bienes indivisibles.
Corradi y Corradi [20] definen una asignación como equitativa si la utilidad de cada agente i (definida como el valor de los artículos más el dinero entregado a i ) es r t i u i (AllItems), donde r es el mismo para todos los agentes. .
Presentan un algoritmo que encuentra una asignación equitativa con r >= 1, lo que significa que la asignación también es proporcional .
La negociación cooperativa es el problema abstracto de seleccionar un vector factible de utilidades, en función del conjunto de vectores de utilidad factibles (la división justa es un caso especial de negociación).
Tres soluciones de negociación clásicas tienen variantes para agentes con diferentes derechos. En particular: