El precio de la justicia

El precio de la equidad ( ing. Price of fairness , POF) en problemas de una división justa es la relación entre el beneficio económico máximo obtenido después de la división y el beneficio económico máximo obtenido bajo la condición de una división justa . POF es una medida cuantitativa de la pérdida de un bien que la sociedad debe pagar para garantizar la equidad.

En general, POF se define mediante la siguiente fórmula:

{\displaystyle POF={\frac {\max_{D\in Divisiones}{(bienestar(D))))){\max_{D\in FairDivisions}{(bienestar(D)))))))

Aquí bienestar(D) = beneficio bajo la división D, Divisiones = conjunto de todas las divisiones, FairDivisions = conjunto de divisiones justas.

El precio exacto varía mucho según el tipo de división, el tipo de patrimonio y el tipo de bien público que estemos considerando.

El tipo de bien social más estudiado es el bien social utilitario , definido como la suma de las utilidades (normalizadas) de todos los agentes. Otro tipo es el bien público igualitario , definido como la utilidad mínima (normalizada) por agente.

Ejemplo numérico

En este ejemplo, nos estamos enfocando en el precio utilitario de proporcionalidad ( UPOP) .

Considere una propiedad heterogénea de la tierra que se dividirá entre 100 participantes, cada uno de los cuales valora la totalidad de la tierra en 100 unidades (o un valor normalizado a 100). Considere primero algunos casos extremos.

El bien utilitario máximo posible es 10 000. Este valor solo se puede lograr en casos extremadamente raros cuando todos los participantes desean recibir diferentes lotes de tierra.
En la participación proporcional, cada participante recibe un valor de al menos 1, por lo que la utilidad del bien no será inferior a 100.

Límite superior

Los casos extremos descritos anteriormente ya dan un límite superior trivial: . Sin embargo, podemos dar un límite superior más preciso. $UPOP\leqslant 10000/100=100$

Supongamos que tenemos una división eficiente de la propiedad de la tierra en 100 participantes con un bien utilitario U . Queremos convertirlo en una división proporcional. Para ello, agrupamos a los participantes según sus valores actuales:

Los participantes cuyo valor actual sea al menos 10 serán llamados afortunados .
El resto de los participantes serán llamados perdedores .

Hay dos casos:

Si hay menos de 10 afortunados, simplemente descartamos la división existente y realizamos una nueva división proporcional (por ejemplo, usando el protocolo "último en reducir" ). En una división proporcional, cada participante obtiene un valor que es al menos 1, por lo que el valor total es al menos 100. El valor de la división original fue menor que (10*100+90*10)=1900, por lo que UPOP no supere los 19.
Si hay al menos 10 afortunados, creamos una división proporcional de acuerdo con la siguiente variante del protocolo "último en reducir" :
- Cada afortunado asigna 0,1 de su parte y permite que uno de los perdedores se lleve esta parte asignada.
- Esto continúa hasta que cada uno (pero no más de) 90 perdedores haya recibido sus acciones. Ahora cada uno de los (al menos) 10 afortunados tiene al menos 0,1 de su valor inicial, y cada uno de los perdedores tiene al menos su valor anterior, por lo que UPOP no supera los 10.

En resumen, UPOP siempre es inferior a 20, independientemente de las medidas de calificación de los participantes.

Límite inferior

UPOP puede ser igual a 1. Por ejemplo, si todos los participantes tienen las mismas medidas de evaluación, entonces para cualquier división, independientemente del concepto de justicia, el bien utilitario será igual a 100, y por lo tanto UPOP=100/100=1.

Sin embargo, estamos interesados en el peor caso de UPOP, por ejemplo, una combinación de medidas en las que UPOP es grande. A continuación se muestra un ejemplo de tal caso.

Imagina que hay dos tipos de socios:

90 socios indiferentes para quienes el valor de todo el terreno es uniforme (por ejemplo, cuando el valor de un terreno es proporcional a su tamaño).
10 socios objetivo , cada uno de los cuales valora solo un pedazo de tierra, que es 0.1 de la parcela completa.

Considere las siguientes dos particiones:

División justa : divida la tierra en partes iguales, dando a cada participante 0,01 de la tierra y los socios seleccionados reciben 0,01 de la tierra deseada. La división es justa, el valor de cada participante indiferente es 1, mientras que el valor de cada participante objetivo es 10, por lo que el bien de utilidad es 190.
División eficiente : Divida toda la tierra entre los participantes objetivo, dando a cada uno de ellos el área deseada completa. El bien de utilidad es 100*10=1000.

En este ejemplo, UPOP es . Por lo tanto, 5.26 es un límite inferior en el peor caso UPOP (donde se elige el "peor caso" entre todas las posibles combinaciones de medidas de evaluación). ${\tfrac {1000}{190}}\cong 5,26$

Combinando

Combinando todos estos resultados, obtenemos que en el peor de los casos UPOP está entre 5 y 20.

Este ejemplo es típico de los argumentos de límite POF. Para probar el límite inferior, basta con dar un solo ejemplo, y para probar el límite superior, es necesario proponer un algoritmo u otro argumento sofisticado.

Corte justo con piezas genéricas

El precio de utilidad de la proporcionalidad

El ejemplo numérico descrito anteriormente se puede generalizar de 100 a n participantes, dando los siguientes límites de UPOP en el peor de los casos:

{\tfrac {\sqrt {n}}{2}}\leqslant UPOP\leqslant 2{\sqrt {n}}-1

UPOP=\Theta ({\sqrt {n)))

Para dos participantes, cálculos más detallados dan un límite [1] . $8-4{\sqrt {3}}\cong 1.07$

El precio de utilidad de la envidia

Cuando se divide toda la torta, el corte sin envidia siempre es proporcional. Por lo tanto, el límite inferior del peor de los casos también se aplica aquí. Por otro lado, desde arriba solo tenemos un límite débil [1] . Como consecuencia, $UPOP({\tfrac {\sqrt {n}}{2}})$ $n-{\tfrac {1}{2))$

{\tfrac {\sqrt {n}}{2}}\leqslant UPOV\leqslant n-{\tfrac {1}{2}}

\Omega ({\sqrt {n)))\leqslant UPOV\leqslant O(n)

Aquí UPOV significa inglés. Precio utilitario de la envidia , es decir, el precio utilitario de la envidia.

Para dos participantes, cálculos más cuidadosos dan un límite [1] . $8-4{\sqrt {3}}\cong 1.07$

El precio de utilidad de la imparcialidad

{\tfrac {(n+1)^{2}}{4n}}\leqslant UPOQ\leqslant n

UPOQ=\Theta (n)

Aquí UPOQ significa inglés. Precio utilitario de la equitabilidad , es decir, el precio utilitario de la imparcialidad.

Para dos participantes, cálculos más cuidadosos dan un límite de 9/8=1,125 [1] .

Finalidad de los objetos indivisibles

Para los objetos indivisibles, no siempre existe una distribución que satisfaga la proporcionalidad, la falta de envidia o la imparcialidad (como un ejemplo simple, imagine dos participantes en la división tratando de compartir un objeto valioso indivisible). Por lo tanto, al calcular el precio de la justicia, no consideramos los casos en los que ninguna división satisface el concepto de justicia elegido. Breve resumen de resultados [1] :

UPOP=n-1+{\tfrac{1}{n))

, para dos personas: 3/2.

(3n+7)/9-O({\tfrac {1}{/}}{n})\leqslant UPOV\leqslant n-{\tfrac {1}{2}}

, para dos personas: 3/2

UPOQ=\infty

, para dos personas: 2

División de tareas divisibles

Para el problema de dividir el pastel, cuando el "pastel" no es deseable (por ejemplo, cortar el césped), tenemos los siguientes resultados [1] :

(n+1)^{\tfrac {2}{4n}}\leqslant UPOP\leqslant n

, para dos personas: 9/8

(n+1)^{\tfrac {2}{4n}}\leqslant UPOV\leqslant \infty

, para dos personas: 9/8

UPOQ=n

Asignación de tareas indivisibles

UPOP=n

UPOV=\infty

UPOQ=\infty

Cortar el pastel en piezas conectadas

El problema del corte justo de la torta tiene variaciones, cuando las piezas seleccionadas deben estar conectadas (individuales, no constan de partes separadas). En este caso, tanto el numerador como el denominador en la fórmula POF son más pequeños (debido a que se toma el máximo en un conjunto más pequeño), por lo que no está claro a priori si la POF será más pequeña o más grande que en el caso desconectado.

El precio de utilidad de la justicia

Se tienen los siguientes resultados con respecto al bien utilitario [2] :

UPOP=\Theta ({\sqrt {n)))

UPOV=\Theta ({\sqrt {n)))

n-1+{\tfrac {1}{n}}\leqslant EPOQ\leqslant n

EPOQ=\Theta (''n'')

El precio igualitario de la justicia

Con la división proporcional , el valor para cada participante no es inferior a 1/ n del total de recursos estimados. En particular, el valor para el agente menos feliz (lo que se llama el bien igualitario del compartir) es al menos 1/ n . Esto significa que en una división óptima igualitaria, el bien igualitario es al menos 1/ n , y por lo tanto la división óptima igualitaria es siempre proporcional. Por lo tanto, el precio igualitario de proporcionalidad ( EPOP ) es igual a 1:

{\ estilo de visualización EPOP = 1}

Argumentos similares se aplican al precio igualitario de la equidad ( EPOQ ):

EPOQ=1

El costo igualitario de no envidiar es mucho mayor [2] :

EPOV={\tfrac{n}{2))

Este es un resultado interesante, porque se sigue que el criterio obligatorio de la ausencia de envidia aumenta los abismos sociales y perjudica a la mayoría de los residentes desafortunados. El criterio de proporcionalidad es mucho menos dañino.

El precio de maximizar un bien

En lugar de calcular la pérdida del bien para garantizar la equidad, podemos calcular la pérdida de la equidad al optimizar el bien. Obtenemos los siguientes resultados [2] :

precio de proporcionalidad por igualitarismo = 1 el costo de no envidiar según el igualitarismo = n -1 precio de proporcionalidad por utilidad

=\infty

el precio de la falta de envidia por la utilidad

=\infty

Asignación de objetos indivisibles a partes conectadas

Como en el caso de cortar el pastel para asignar objetos indivisibles, existen variaciones en las que los objetos se encuentran en una línea y cada pieza a seleccionar debe ser un segmento de línea. Breve resumen de resultados [3] :

UPOP=n-1+{\tfrac{1}{n))

UPOV=\Theta ({\sqrt {n)))

UPOQ=\infty

; para dos personas: 3/2

{\ estilo de visualización EPOP = 1}

EPOV={\tfrac{n}{2))

EPOQ=\infty

; para dos personas: 1

Distribución de tareas con piezas conectadas

Breve resumen de los resultados [4] :

{\tfrac {n}{2}}\leqslant UPOP\leqslant n

UPOV=\infty

UPOQ=n

{\ estilo de visualización EPOP = 1}

EPOV=\infty

EPOQ=1

Otros resultados

El costo de la equidad también se ha estudiado en el contexto de la asignación de recursos [5] [6] .

Véase también

Notas

↑ 1 2 3 4 5 6 Caragiannis, Kaklamanis et al., 2011 , pág. 589.
↑ 1 2 3 Aumann, Dombb, 2010 , pág. 26
↑ Suksompong, 2019 , pág. 227–236.
↑ Heydrich, van Stee, 2015 , pág. 51–61.
↑ Bertsimas, Farias, Trichakis, 2011 , p. 17–31.
↑ Bertsimas, Farias, Trichakis, 2012 , p. 2234.

Literatura

Caragiannis I., Kaklamanis C., Kanellopoulos P., Kyropoulou M. La eficiencia de la división justa // Teoría de los sistemas informáticos. - 2011. - T. 50 , núm. 4 . -doi : 10.1007 / s00224-011-9359-y .
Aumann Y., Dombb Y. Internet y economía de redes . - 2010. - T. 6484. - (Apuntes de cátedra en Informática). — ISBN 978-3-642-17571-8 . -doi : 10.1007 / 978-3-642-17572-5_3 .
Suksompong W. Asignación justa de bloques contiguos de elementos indivisibles // Matemáticas aplicadas discretas. - 2019. - T. 260 . -doi : 10.1016/ j.dam.2019.01.036 . -arXiv : 1707.00345 . _
Heydrich S., van Stee R. Dividir las tareas relacionadas de manera justa // Ciencias de la computación teórica. - 2015. - T. 593 . -doi : 10.1016/ j.tcs.2015.05.041 .
Bertsimas D., Farias VF, Trichakis N. El precio de la equidad // Investigación de operaciones. - 2011. - T. 59 . doi : 10.1287 / opre.1100.0865 .
Bertsimas D., Farias VF, Trichakis N. Sobre el equilibrio entre eficiencia y equidad // Ciencias de la gestión. - 2012. - T. 58 , núm. 12 _ -doi : 10.1287/ mnsc.1120.1549 .