División equitativa

La división equitativa (DB, inglés equitable division , EQ) es una partición de un objeto no homogéneo (por ejemplo, un pastel ), como resultado de lo cual los valores subjetivos de todos los participantes son los mismos, es decir, cada participante está igualmente satisfecho con su parte. Matemáticamente, esto significa que para todos los participantes i y j ,

V_{i}(X_{i})=V_{j}(X_{j})

dónde

$X_{yo}$ es pan comido asignado al participante i ;
$V_i$ es la función de puntuación del participante i . Esta es una función de valor real que, para cada porción del pastel, devuelve un número que representa la cantidad de utilidad para el miembro i de esa porción. Por lo general, estas funciones se normalizan de modo que y (el pastel completo) para cualquier i . $V_{i}(\emptyset)=0$ $V_{i}=1$

Comparación con otros criterios

La imparcialidad (DB) compara las puntuaciones de diferentes personas de diferentes fragmentos;
La ausencia de envidia (OZ, inglés Envy-freeness , EF) compara las valoraciones de una persona de varias piezas;
La división exacta (TD, ing. División exacta , EX) compara las estimaciones de diferentes personas de las mismas piezas.

La siguiente tabla muestra la diferencia. En todos los ejemplos, hay dos participantes, Alice y Bob. Alice obtiene el lado izquierdo y Bob obtiene el lado derecho.

división

DB?

¿ONZ?

TD?

A:	cincuenta%	cincuenta%
B:	cincuenta%	cincuenta%

A:	60%	40%
B:	40%	60%

(Alice y Bob no están de acuerdo en la evaluación de las piezas).

A:	40%	60%
B:	60%	40%

(Alice y Bob están celosos el uno del otro).

A:	70%	treinta%
B:	40%	60%

(Alice está más complacida con su parte que Bob con la de él).

A:	60%	40%
B:	60%	40%

(Bob está celoso de Alice).

A:	60%	40%
B:	70%	treinta%

Tenga en cuenta que la tabla tiene solo 6 filas, ya que 2 combinaciones son imposibles: la división TD + OD debe ser un DB y la división TD + DB debe ser un CV.

Encontrar una división igual para dos participantes

Un corte - información completa

Cuando hay dos participantes, es posible obtener una división imparcial con un solo corte, pero esto requiere un conocimiento completo de las puntuaciones de los participantes [1] . Suponga que el pastel es el segmento [0,1]. Para cada , los calculamos y los marcamos en el mismo gráfico. Tenga en cuenta que el primer gráfico aumenta de 0 a 1 y el segundo gráfico disminuye de 1 a 0, por lo que tienen un punto de intersección. Cortar el pastel en este punto da una división imparcial. Este corte tiene una serie de propiedades adicionales: $x\en[0,1]$ $u_{1}([0,x])$ ${\ estilo de visualización u_ {2} ([x, 1])}$

El corte es EP porque cada participante obtiene un valor de al menos 1/2.
El corte no es un no-AP, ya que el valor para cada participante puede ser mayor a 1/2.
El corte es eficiente en el sentido de Pareto ( PE) entre todas las divisiones usando un solo corte . Sin embargo, puede haber cortes más eficientes utilizando dos o más cortes [2] .
Si la dirección del pastel se elige al azar (es decir, el pastel se puede voltear para que 0 se convierta en 1 y 1 se convierta en 0), entonces este procedimiento es nuevamente débilmente cierto en el siguiente sentido: solo al proporcionar medidas de probabilidad justas pueden los participantes ser asegúrese de recibir al menos la mitad del pastel [1] .

El mismo procedimiento se puede aplicar a la división del trabajo rutinario (si la evaluación de la pieza se toma con signo contrario).

Versión proporcionalmente imparcial

El procedimiento de información completa tiene una variante [3] que satisface los tipos más débiles de imparcialidad y los tipos más estrictos de precisión. El procedimiento primero encuentra la mediana para cada participante. Suponga que la mediana del miembro A es , y la mediana del miembro B es , donde . Entonces A obtiene y B obtiene . Ahora queda un saldo que se reparte entre los participantes en proporciones iguales . Entonces, por ejemplo, si A estima que el resto es 0.4 y B estima que es 0.2, entonces A obtendrá el doble de valor que B. Por lo tanto, el protocolo no será imparcial, pero seguirá siendo OZ. Es débilmente honesto en el siguiente sentido: el jugador adverso al riesgo tiene un incentivo para indicar la estimación verdadera, ya que puede recibir un valor más bajo al indicar una estimación que no corresponde a la verdad. $a$ $b$ ${\ estilo de visualización 0 <a <b <1}$ $[0, un]$ ${\ estilo de visualización [b, 1]}$ $[a,b]$ $[a,b]$

Dos cortes - cuchillo en movimiento

El procedimiento "Moving Knife" de Austin le da a cada uno de los dos participantes una pieza con un valor subjetivo de exactamente 1/2. Así, esta división es la DB, TD y OZ. El procedimiento requiere dos cortes y le da a uno de los participantes dos piezas desconectadas.

Muchos cortes: preferencias completamente abiertas

Si se permite hacer más de dos cortes, es posible lograr una división, que será no solo la DB, sino también la OZ y la EP . Algunos autores llaman a tal división "perfecta" [4] .

El número mínimo de cortes necesarios para una división EP-OZ-DB depende de las puntuaciones de los participantes. En la mayoría de los casos prácticos (incluidos los casos en los que las estimaciones son lineales por partes), el número de cortes necesarios es finito. En estos casos, se puede encontrar tanto el número óptimo de cortes como su ubicación exacta. El algoritmo requiere un conocimiento completo de las puntuaciones de los participantes [4] .

Tiempo de ejecución del algoritmo

Todos los procedimientos anteriores son continuos: el segundo procedimiento requiere que la cuchilla se mueva continuamente, otros requieren que los gráficos de las dos medidas de evaluación sean continuos. Por lo tanto, estos procedimientos no pueden completarse en un número finito de pasos discretos.

Esta propiedad del infinito es una característica de los problemas de división que requieren resultados exactos (ver el artículo División exacta: imposibilidad ).

Un corte es una división casi imparcial

Una división casi imparcial es una división en la que las puntuaciones de cada jugador difieren en no más que para cualquier número fijo . Se puede encontrar una división casi imparcial para dos jugadores en tiempo finito para la condición de corte de unidad [5] . $\epsilon$ ${\ estilo de visualización \ épsilon > 0}$

Encontrar una división justa para tres o más participantes

El procedimiento del cuchillo móvil

El procedimiento de Austin se puede extender a n participantes. El procedimiento otorga a cada participante un valor subjetivo de exactamente . Esta división es un DB, pero no necesariamente un TD, OZ o EP (porque algunos participantes pueden valorar la participación transferida a otros participantes más que ). $1/n$ $1/n$

Los fragmentos conectados son preferencias completamente abiertas

El procedimiento Johnson de preferencia totalmente abierta se puede extender a los participantes de la siguiente manera [3] : $norte$

Para cada uno de los ordenamientos de los participantes, escribimos un conjunto de ecuaciones con variables: las variables son puntos de corte y las ecuaciones determinan la imparcialidad para los participantes vecinos. por ejemplo, si hay 3 participantes en el orden A:B:C, entonces hay dos variables (punto de corte para A y B) y , y las dos ecuaciones serían y . Estas ecuaciones tienen al menos una solución en la que todos los participantes tienen el mismo valor. $¡norte!$ $n-1$ $n-1$ $n-1$ $x_{AB}$ $x_{BC}$ $V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})$ $V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)$
De todos los pedidos, elegimos el orden en el que el (mismo) valor para todos los participantes fue mayor. $¡norte!$

Tenga en cuenta que el valor máximo imparcial debe ser al menos , dado que ya sabemos que la división proporcional (dar a cada participante al menos ) es posible. $1/n$ $1/n$

Si las puntuaciones de los participantes son absolutamente continuas entre sí, cualquier intento de aumentar el valor de un participante debe disminuir el valor de otro participante. Esto significa que esta solución tiene la propiedad EP entre todas las soluciones con piezas conectadas.

Imposibilidad

Brahms, Jones y Klamler estudiaron la división, que es tanto DB como EP y OZ (llamaron a esa división "perfecta").

Primero, probaron que para 3 participantes, si tuvieran piezas conectadas, el corte DB+OZ podría no existir [3] . Hicieron esto describiendo 3 medidas específicas de puntaje para un pastel unidimensional para el cual cualquier división DB de 2 cortes no sería un EP.

Luego probaron que para 3 o más participantes de EP+OD+DB, la división puede no existir incluso si se resuelven piezas desconectadas [2] . Lo hicieron describiendo 3 medidas de evaluación específicas para un pastel unidimensional con las siguientes propiedades:

Para 2 cortes, cualquier corte de DB no será ni OZ ni EP (pero hay cortes que son OZ y 2-EP o DB y 2-EP).
Para 3 cortes, cualquier corte de DB no será un EP (pero hay cortes de DB + OZ).
Para 4 cortes, cualquier corte DB no será OC (pero hay cortes DB+EP).

Repartiendo el pastel

Un pastel es un pastel en forma de un círculo unidimensional (ver el problema del corte justo del pastel ).

Barbanel, Brahms y Stromqvist han estudiado la existencia de un corte circular que es tanto DB como OZ. Los siguientes resultados han sido probados sin dar un algoritmo de división específico [6] :

Para dos participantes siempre hay un reparto imparcial del pastel, en el que no hay envidia. Si las medidas de los puntajes de preferencia de los participantes son absolutamente continuas entre sí (es decir, cualquier pieza que tiene un valor positivo para un participante también tiene un valor positivo para otros participantes), hay una distribución de torta libre de envidia que es a la vez imparcial y no dominado.
Para 3 o más participantes, puede que no sea posible encontrar una distribución de pasteles imparcial que esté libre de envidia. Sin embargo, siempre hay una división que es a la vez imparcial y no dominante.

División de objetos divisibles

El procedimiento Ganador ajustable calcula una división de objetos divisibles entre dos participantes imparcial, libre de envidia y eficiente en el sentido de Pareto.

Mesa final

Nombre	Tipo de	Número de participantes	número de cortes	Propiedades
Algoritmo de Jones [1]	Preferencias completamente abiertas	2	1 (óptimo)	BD, OZ, 1 EP
Procedimiento Brahms-Jones-Klumler [ 3]	Preferencias completamente abiertas	norte	n −1 (óptimo)	DB, ( n −1)-EP
Procedimiento de Austin	Procedimiento para mover el cuchillo	2	2	DB, OZ, DT
Procedimiento de Austin	Procedimiento para mover el cuchillo	norte	un monton de	base de datos
Procedimiento de Barbanel-Brahms [4]	Preferencias completamente abiertas	2	un monton de	DB, OZ, EP
Procedimiento Cheklarova- Pillarova [5]	Aproximación discreta	2	1 (óptimo)	casi DB

Notas

↑ 1 2 3 Jones, 2002 , pág. 275–283.
↑ 1 2 Brams, Jones, Klamler, 2013 , pág. 35.
↑ 1 2 3 4 Brams, Jones, Klamler, 2007 .
↑ 1 2 3 Barbanel, Brams, 2014 , pág. 23
↑ 1 2 Cechlárová, Pillárová, 2012 , pág. 1321.
↑ Barbanel, Brams, Stromquist, 2009 , pág. 496.

Literatura

Jones MA Corte de pastel equitativo, sin envidia y eficiente para dos personas y su aplicación a bienes divisibles // Revista de matemáticas. - 2002. - T. 75 , núm. 4 . — Pág. 275–283 . -doi : 10.2307/ 3219163 . — .
Steven J. Brams, Michael A. Jones, Christian Klamler. Mejores formas de cortar un pastel: revisado // Avisos de la AMS. — 2007.
Julius B. Barbanel, Steven J. Brams. Corte de pastel de dos personas: el número óptimo de cortes // The Mathematical Intelligencer. - 2014. - T. 36 , núm. 3 . -doi : 10.1007/ s00283-013-9442-0 .
Katarina Cechlárová, Eva Pillárová. Un algoritmo de corte de pastel de 2 personas casi equitativo // Optimización. - 2012. - T. 61 , núm. 11 _ -doi : 10.1080/ 02331934.2011.563306 .
Barbanel JB, Brams SJ, Stromquist W. Cortar un pastel no es pan comido // American Mathematical Monthly. - 2009. - T. 116 , núm. 6 _ -doi : 10.4169 / 193009709X470407 .
Steven J. Brams, Michael A. Jones, Christian Klamler. Corte de pastel de N personas: puede que no haya una división perfecta // The American Mathematical Monthly. - 2013. - T. 120 . doi : 10.4169 / amer.math.monthly.120.01.035 .