Derecho (reparto equitativo)

El Talmud contiene varios ejemplos en los que los derechos no se deciden de forma proporcional.

• El problema de la prenda en disputa. Si una persona reclama la totalidad de una tela y otra la mitad, entonces se divide en 3/4 y 1/4. ^{[ 3 ]}
• El problema de la división de la herencia. Tres esposas tienen reclamaciones sobre 100, 200 y 300 zuz . Se consideran tres casos: si la herencia es de 100 zuz, cada una recibe 33 y un tercio; si es de 200, 50, 75 y 75; y si es de 300, 50, 100 y 150. ^{[ 4 ]}
• Ganancias de un fondo común. Si dos personas aportan 200 y 100 a un fondo y compran un buey para arar y lo utilizan para tal fin, deben repartirse las ganancias a partes iguales. Pero si, en cambio, sacrifican el buey, las ganancias se dividen proporcionalmente. Esto se analiza en el Talmud babilónico (justo después del problema de la división de la herencia). ^{[ 4 ]}
• El problema de Ibn Ezra. Este es un problema posterior de división de herencia que se resolvió de manera diferente. Un hombre con una herencia de 120 muere legando 120, 60, 40 y 30 a sus cuatro hijos. La recomendación fue otorgar (120–60)/1+(60–40)/2+(40–30)/3+(30–0)/4 al primero y sumas con los términos iniciales eliminados para el resto, terminando con 30/4 para el último. Esta asignación es diferente de la división de herencia anterior. ^{[ 4 ]}

Todas estas soluciones pueden modelarse mediante juegos cooperativos . El problema de la división de propiedades tiene una amplia bibliografía y fue fundamentado teóricamente en la teoría de juegos por Robert J. Aumann y Michael Maschler en 1985. ^{[ 5 ]} Véase Regla de vestimenta en disputa .

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. Este es un problema de distribución de elementos idénticos e indivisibles (los escaños) entre agentes con diferentes derechos. Se denomina problema de reparto .

La asignación de escaños según el tamaño de la población puede dejar a las circunscripciones pequeñas sin voz alguna. La solución más sencilla es crear circunscripciones de igual tamaño. Sin embargo, a veces esto resulta imposible, como en la Unión Europea o en Estados Unidos . Garantizar que el poder de voto sea proporcional al tamaño de las circunscripciones es un problema de derechos.

Existen diversos métodos para calcular el poder de voto en circunscripciones de distinto tamaño o ponderación. Los principales son el índice de poder de Shapley-Shubik y el índice de poder de Banzhaf . Estos índices parten de la premisa de que las circunscripciones pueden unirse de forma aleatoria y se aproximan a la raíz cuadrada de la ponderación, según el método de Penrose . Esta premisa no se corresponde con la práctica real y es discutible que las circunscripciones más grandes reciban un trato injusto.

En el contexto más complejo de la asignación equitativa de artículos , existen múltiples artículos diferentes con valores posiblemente distintos para diferentes personas.

Aziz, Gaspers, Mackenzie y Walsh ^{[ 9 ] : sec.7.2} definen la proporcionalidad y la ausencia de envidia para agentes con diferentes derechos, cuando los agentes revelan solo 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 los 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 ^{[ 10 ]} definieron la Participación Maximin Ponderada (WMMS) como una generalización de la participación maximin para agentes con diferentes derechos. Demostraron que la mejor garantía multiplicativa alcanzable para la 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 la WMMS del agente. Aziz, Chan y Li ^{[ 11 ]} adaptaron la noción de WMMS a tareas domésticas (elementos con utilidades negativas). Demostraron que, incluso para dos agentes, es imposible garantizar más de 4/3 de la WMMS (nótese que con tareas domésticas, las razones de aproximación son mayores que 1, y menor es 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 del WMMS que se puede obtener en el caso dado. Presentan un algoritmo de tiempo polinomial que logra una aproximación de cuatro factores del OWMMS.

El WMMS es una noción cardinal , ya que si las utilidades cardinales de un agente cambian, entonces el conjunto de cestas que satisfacen el WMMS para el agente puede cambiar. Babaioff, Nisan y Talgam-Cohen ^{[ 12 ]} introdujeron otra adaptación del MMS para agentes con diferentes derechos, que se basa únicamente en la clasificación ordinal de las cestas del agente. Demuestran que esta noción de equidad se alcanza mediante un equilibrio competitivo con diferentes presupuestos, donde los presupuestos son proporcionales a los derechos. Esta noción de equidad es denominada Participación Maximina Ordinal (OMMS) por Chakraborty, Segal-Halevi y Suksompong. ^{[ 13 ]} La relación entre varias aproximaciones ordinales del MMS es estudiada con mayor profundidad por Segal-Halevi. ^{[ 14 ] [ 15 ]}

Babaioff, Ezra y Feige ^{[ 16 ]} presentan otra noción ordinal, más fuerte que OMMS, que denominan Participación a Cualquier Precio (APS) . Muestran un algoritmo de tiempo polinomial que alcanza una fracción de 3/5 de la APS.

Aziz, Moulin y Sandomirskiy ^{[ 17 ]} 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 relajaciones de WEF solo se han estudiado para bienes. Chakraborty, Igarashi y Suksompong ^{[ 18 ]} introdujeron el algoritmo round-robin ponderado para WEF(1,0). En un trabajo posterior, Chakraborty, Schmidt-Kraepelin y Suksompong generalizaron el algoritmo round-robin ponderado a secuencias de selección generales y estudiaron diversas propiedades de monotonicidad de estas secuencias.

En el problema de la asignación equitativa de bienes y dinero , las transferencias monetarias pueden utilizarse para lograr una distribución justa y exacta de bienes indivisibles.

Corradi y Corradi ^{[ 19 ]} 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 dado a i ) es r t _i u _i (TodosLosArtículos), 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 .