stringtranslate.com

Precio de la justicia

En la teoría de la división justa , el precio de la equidad (POF) es la relación entre el mayor bienestar económico alcanzable mediante una división y el bienestar económico alcanzado mediante una división justa . El POF es una medida cuantitativa de la pérdida de bienestar que la sociedad tiene que soportar 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 justicia y el tipo de bienestar social que nos interesa.

El tipo de bienestar social mejor 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.

Considere un terreno heterogéneo que debe dividirse entre 100 socios, todos los cuales lo valoran como 100 (o el valor se normaliza a 100). Primero, veamos 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 patrimonio territorial entre 100 socios, con un bienestar utilitario U . Queremos convertirlo a una división proporcional. Para ello agrupamos a los socios según su valor actual:

Hay dos casos:

En resumen: el UPOP es siempre inferior a 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, estamos interesados ​​en un UPOP en el peor de los casos, es decir, una combinación de medidas de valor en las que el UPOP es grande. He aquí un ejemplo de ello.

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 en el peor caso UPOP (donde el "peor caso" se toma sobre todas las combinaciones posibles de medidas de valor).

Conjunto

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

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

Corte de torta con piezas generales

Precio utilitario de la proporcionalidad

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

norte /2 ≤ UPOP ≤ 2√ norte -1
UPOP = Θ(√ 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 envidia

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

norte /2 ≤ UPOV ≤ norte -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 da un límite de: 9/8=1,125. [1]

Asignación de bienes indivisibles

Para los artículos indivisibles, no siempre existe una asignación que satisfaga la proporcionalidad, la ausencia de envidia o la equidad (por ejemplo, imaginemos dos socios que intentan dividir un solo artículo valioso). Véase también asignación justa de artículos . En consecuencia, en los cálculos del precio de equidad, no se consideran los casos en los que ninguna asignación satisface la noción de equidad relevante. Un breve resumen de los resultados: [1]

UPOP = norte - 1 + 1/ norte ; 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

Corte de tareas con piezas generales.

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

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

Asignación de males indivisibles

UPOP = n
UPOV = infinito
UPOQ = infinito

Cortar pasteles con piezas conectadas

El problema del corte justo de un pastel tiene una variación en la que las piezas deben estar conectadas. En esta variación, tanto el denominador como el denominador 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 el POF debe ser menor o mayor que en el caso desconectado.

Precio utilitario de la justicia

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

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

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 (lo 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 es siempre proporcional. Por tanto, el precio igualitario de proporcionalidad (EPOP) es 1:

EPOP = 1

Se aplican consideraciones similares al precio igualitario de la equidad (EPOQ):

EPOQ = 1

El precio igualitario de estar libre de envidia es mucho mayor: [2]

EPOV = n /2

Este es un resultado interesante, ya que implica que la insistencia en el criterio de no tener envidia aumenta las brechas sociales y perjudica a los ciudadanos más desafortunados. El criterio de proporcionalidad es mucho menos perjudicial.

El precio de la maximización del bienestar

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

precio-proporcional-del-igualitarismo = 1
envidia-precio-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 corte de pasteles, para la asignación de artículos indivisibles hay una variación en la que los artículos se encuentran en una línea y cada pieza asignada debe formar un bloque en la línea. Un breve resumen de los resultados: [3]

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

Cortar tareas con piezas conectadas

Un breve resumen de los resultados: [4]

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

Asignación homogénea de recursos

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

UPOV = UPOP = Θ(√ norte )

Esto se debe a que la regla del 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 equidad se ha estudiado en el contexto del problema de la suma del subconjunto justo .

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

Ver 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 y economía de redes. Apuntes de conferencias sobre informática. vol. 6484. págs. 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ática Aplicada Discreta . 260 : 227–236. arXiv : 1707.00345 . doi :10.1016/j.dam.2019.01.036. S2CID  126658778.
  4. ^ Heydrich, S.; van Stee, R. (2015). "Dividir equitativamente las tareas conectadas". Informática 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". La 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 (13 de diciembre de 2021). "El precio de la representación justificada". arXiv : 2112.05994 [cs.GT].