stringtranslate.com

El precio de la justicia

En la teoría de la división justa , el precio de la justicia (POF) es la relación entre el máximo bienestar económico que se puede obtener mediante una división y el bienestar económico obtenido mediante una división justa . El POF es una medida cuantitativa de la pérdida de bienestar que la sociedad debe asumir para garantizar la justicia.

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

El precio exacto varía mucho según el tipo de división, el tipo de equidad y el tipo de bienestar social que nos interesa.

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

Ejemplo numérico

En este ejemplo nos centramos en el precio utilitario de proporcionalidad , o UPOP.

Consideremos un terreno heterogéneo que debe dividirse entre 100 socios, todos los cuales lo valoran en 100 (o el valor se normaliza a 100). Veamos primero algunos casos extremos.

Límite superior

Los casos extremos descritos anteriormente ya nos dan un límite superior trivial: UPOP ≤ 10000/100 = 100. Pero podemos obtener un límite superior más estricto.

Supongamos que tenemos una división eficiente de un terreno entre 100 socios, con un bienestar utilitario U . Queremos convertirlo en una división proporcional. Para ello, agrupamos a los socios según su valor actual:

Hay dos casos:

En resumen: el UPOP siempre es menor que 20, independientemente de las medidas de valor de los socios.

Límite inferior

El UPOP puede ser tan bajo como 1. Por ejemplo, si todos los socios tienen la misma medida de valor, entonces en cualquier división, independientemente de la equidad, el bienestar utilitario es 100. Por lo tanto, UPOP=100/100=1.

Sin embargo, nos interesa un UPOP en el peor de los casos, es decir, una combinación de medidas de valor en las que el UPOP es grande. A continuación se muestra un ejemplo.

Supongamos que hay dos tipos de socios:

Considere las dos particiones siguientes:

En este ejemplo, el UPOP es 1000/190=5,26. Por lo tanto, 5,26 es un límite inferior del UPOP del peor caso (donde el "peor caso" se toma sobre todas las combinaciones posibles de medidas de valor).

Conjunto

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

Este ejemplo es típico de los argumentos utilizados para acotar el POF. Para demostrar un límite inferior, es suficiente describir un solo ejemplo; para demostrar un límite superior, se debe presentar un algoritmo u otro argumento sofisticado.

Corte de pastelcon piezas generales

Precio utilitario deproporcionalidad

El ejemplo numérico descrito anteriormente se puede generalizar de 100 a n socios, lo que da los siguientes límites para el UPOP en el peor de los casos:

n /2 ≤ UPOP ≤ 2√ n -1
UPOP = Θ(√ n )

Para dos socios, un cálculo más detallado da un límite de: 8-4*√3 ≅ 1,07. [1]

Precio utilitario deenvidiar

Cuando se divide todo el pastel, una división sin envidias siempre es proporcional. Por lo tanto, el límite inferior del UPOP del peor caso (√ n /2) también se aplica aquí. Por otro lado, como límite superior solo tenemos un límite débil de n -1/2. [1] Por lo tanto:

n /2 ≤ UPOV ≤ n -1/2
Ω(√ norte ) ≤ UPOV ≤ O( norte )

Para dos socios, un cálculo más detallado da un límite de: 8-4*√3 ≅ 1,07. [1]

Precio utilitario de la equidad

Para dos socios, un cálculo más detallado arroja un límite de: 9/8=1,125. [1]

Asignación de bienes indivisibles

En el caso de los bienes indivisibles, no siempre existe una asignación que satisfaga la proporcionalidad, la ausencia de envidia o la equidad (para dar un ejemplo sencillo, imaginemos a dos socios que intentan dividir un único bien valioso). Véase también asignación justa de bienes . En consecuencia, en los cálculos del precio de la justicia, no se consideran los casos en los que ninguna asignación satisface la noción de justicia pertinente. Un breve resumen de los resultados: [1]

UPOP = n - 1 + 1/ n ; para dos personas: 3/2.
(3 n +7)/9-O(1/ n ) ≤ UPOV ≤ n -1/2; para dos personas: 3/2
UPOQ=Infinito; para dos personas: 2

Reducción de tareas domésticascon piezas generales

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

( n + 1)^2/4 n ≤ UPOP ≤ n ; para dos personas: 9/8
(n+1)^2/4n ≤ UPOV ≤ infinito; para dos personas: 9/8
UPOQ= n

Asignación indivisible de males

UPOP = n
UPOV = infinito
UPOQ = infinito

Corte de pastel con piezas conectadas

El problema de la distribución justa de las piezas tiene una variante en la que las piezas deben estar conectadas. En esta variante, tanto el denominador como el nominador en la fórmula POF son más pequeños (ya que el máximo se toma sobre un conjunto más pequeño), por lo que a priori no está claro si la fórmula POF debería ser más pequeña o más grande que en el caso desconectado.

Precio utilitario de la justicia

Tenemos los siguientes resultados para el bienestar utilitarista: [2]

UPOP = Θ(√ n )
UPOV = Θ(√ n )
n -1+1/ n ≤ EPOQ ≤ n
EPOQ = Θ( n )

Precio igualitario de la justicia

En una división proporcional , el valor de cada socio es al menos 1/ n del total. En particular, el valor del agente menos afortunado (que se denomina bienestar igualitario de la división) es al menos 1/ n . Esto significa que en una división igualitaria óptima, el bienestar igualitario es al menos 1/ n , por lo que una división igualitaria óptima siempre es proporcional. Por lo tanto, el precio igualitario de proporcionalidad (EPOP) es 1:

EPOP = 1

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

EPOQ = 1

El precio igualitario de no tener envidia es mucho mayor: [2]

EPOV = n /2

Este es un resultado interesante, ya que implica que la insistencia en el criterio de ausencia de envidia aumenta las brechas sociales y perjudica a los ciudadanos más desfavorecidos. El criterio de proporcionalidad es mucho menos dañino.

El precio de maximizar el bienestar

En lugar de calcular la pérdida de bienestar debido a la equidad, podemos calcular la pérdida de equidad debido a la optimización del bienestar. Obtenemos los siguientes resultados: [2]

precio proporcional del igualitarismo = 1
precio-de-la-envidia-del-igualitarismo = n -1
precio proporcional del utilitarismo = infinito
envidia-precio-del-igualitarismo = infinito

Asignación de bienes indivisibles con bloques conectados

Al igual que en el caso del corte de torta, para la asignación de elementos indivisibles existe una variante en la que los elementos se encuentran sobre una línea y cada pieza asignada debe formar un bloque sobre la línea. Un breve resumen de los resultados: [3]

UPOP = n - 1 + 1/ n
UPOV = Θ(√ n )
UPOQ = infinito; para dos personas: 3/2
EPOP = 1
EPOV = n /2
EPOQ = infinito; para dos personas: 1

Corte de tareas con piezas conectadas

Un breve resumen de los resultados: [4]

n /2 ≤ UPOP ≤ n
UPOV = infinito
UPOQ = n
EPOP = 1
EPOV = infinito
EPOQ = 1

Asignación homogénea de recursos

El precio de la justicia también se ha estudiado en el contexto de la asignación de recursos homogéneos divisibles, como el petróleo o la madera. Los resultados conocidos son: [5] [6]

UPOV = UPOP = Θ(√ n )

Esto se debe a que la regla de equilibrio competitivo a partir de ingresos iguales produce una asignación libre de envidia y su precio utilitario es O(√ n ).

Otros contextos

El precio de justicia se ha estudiado en el contexto del problema de la suma de subconjuntos justos .

El precio de la representación justificada es la pérdida de la satisfacción media debido al requisito de tener una representación justificada en un entorno de votación de aprobación . [7]

Véase también

Referencias

  1. ^ abcdef Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M. (2011). "La eficiencia de la división justa". Teoría de los Sistemas Computacionales . 50 (4): 589. CiteSeerX  10.1.1.475.9976 . doi :10.1007/s00224-011-9359-y. S2CID  8755258.
  2. ^ abc Aumann, Y.; Dombb, Y. (2010). "La eficiencia de la división justa con piezas conectadas" . Internet and Network Economics. Lecture Notes in Computer Science. Vol. 6484. pp. 26. CiteSeerX 10.1.1.391.9546 . doi :10.1007/978-3-642-17572-5_3. ISBN .  978-3-642-17571-8.
  3. ^ Suksompong, W. (2019). "Asignación justa de bloques contiguos de elementos indivisibles". Matemáticas Aplicadas Discretas . 260 : 227–236. arXiv : 1707.00345 . doi :10.1016/j.dam.2019.01.036. S2CID  126658778.
  4. ^ Heydrich, S.; van Stee, R. (2015). "Dividir tareas conectadas de manera justa". Ciencias de la computación teórica . 593 : 51–61. doi : 10.1016/j.tcs.2015.05.041 . hdl : 2381/37387 .
  5. ^ Bertsimas, D.; Farías, VF; Trichakis, N. (2011). "El precio de la justicia". Investigación de Operaciones . 59 : 17–31. doi :10.1287/opre.1100.0865. hdl : 1721.1/69093 .
  6. ^ Bertsimas, D.; Farías, VF; Trichakis, N. (2012). "Sobre el equilibrio entre eficiencia y equidad". Ciencias de la gestión . 58 (12): 2234. CiteSeerX 10.1.1.380.1461 . doi :10.1287/mnsc.1120.1549. 
  7. ^ Elkind, Edith; Faliszewski, Piotr; Igarashi, Ayumi; Manurangsi, Pasin; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (2024). "El precio de la representación justificada". ACM Transactions on Economics and Computation . arXiv : 2112.05994 . doi :10.1145/3676953.