Reparto equitativo del pastel

El reparto equitativo de un pastel (EQ) es un tipo de problema de reparto justo de un pastel , en el que el criterio de justicia es la equidad . Se trata de una asignación de pastel en la que el valor subjetivo de todos los socios es el mismo, es decir, cada socio está igualmente satisfecho con su parte. Matemáticamente, esto significa que para todos los socios $i$ y $j$ :

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

Dónde:

$X_{i}$ es el trozo de pastel asignado al socio $i$ ;
$V_{i}$ es la medida de valor del socio $i$ . Es una función de valor real que, para cada trozo de pastel, devuelve un número que representa la utilidad del socio $i$ de ese trozo. Normalmente, estas funciones se normalizan de tal manera que $V_{i}(\emptyset)=0$ y $V_{i}(Pastel Completo)=1$ por cada $i$ .

Consulte la página sobre equidad para ver ejemplos y comparaciones con otros criterios de justicia.

Encontrar una forma equitativa de repartir el pastel entre dos socios.

Un corte, revelación completa

Cuando hay 2 socios, es posible obtener una división EQ con un solo corte, pero requiere un conocimiento completo de las valoraciones de los socios. ^{[ 1 ]} Supongamos que el pastel es el intervalo [0,1]. Para cada $x\in [0,1]$ calcular $u_{1}([0,x])$ y $u_{2}([x,1])$ y represéntalas en el mismo gráfico. Observa que el primer gráfico aumenta de 0 a 1 y el segundo disminuye de 1 a 0, por lo que tienen un punto de intersección. Cortar el pastel en ese punto produce una división equitativa. Esta división tiene varias propiedades adicionales:

Es EF, ya que cada socio recibe un valor de al menos 1/2.
No es EX, ya que el valor por socio puede ser superior a 1/2.
Es eficiente en el sentido de Pareto (PE) entre todas las divisiones que utilizan un solo corte. Sin embargo, puede haber divisiones más eficientes que utilicen dos o más cortes. ^{[ 2 ]}
Si la dirección del pastel se elige al azar (es decir, se puede voltear de manera que 0 se convierta en 1 y 1 en 0), entonces este procedimiento también es débilmente veraz, en el siguiente sentido: solo al presentar medidas de probabilidad sinceras, un participante puede asegurarse de recibir al menos la mitad del pastel. ^{[ 1 ]}

El mismo procedimiento puede utilizarse para dividir las tareas domésticas (con utilidad negativa).

Variante de equidad proporcional

El procedimiento de revelación completa tiene una variante ^{[ 3 ]} que satisface un tipo de equidad más débil y un tipo de veracidad más fuerte. El procedimiento primero encuentra los puntos medianos de cada socio. Supongamos que el punto mediano del socio A es $a$ y del socio B es $b$ , con $0<a<b<1$ . Luego, A recibe $[0,a]$ y B recibe $[b,1]$ Ahora hay un excedente. $[a,b]$ El excedente se divide entre los socios en proporciones iguales . Por ejemplo, si A valora el excedente en 0,4 y B lo valora en 0,2, entonces A recibirá el doble de valor de $[a,b]$ que B. Por lo tanto, este protocolo no es equitativo, pero sigue siendo EF. Es débilmente veraz en el siguiente sentido: un jugador reacio al riesgo tiene un incentivo para informar su verdadera valoración, porque informar una valoración falsa podría dejarlo con un valor menor.

Dos cortes - cuchillo en movimiento

El procedimiento de Austin con cuchilla móvil asigna a cada uno de los dos socios una pieza con un valor subjetivo exacto de 1/2. Por lo tanto, la división es EQ, EX y EF. Requiere dos cortes y le da a uno de los socios dos piezas desconectadas.

Muchos cortes - revelación completa

Cuando se permiten más de dos cortes, es posible lograr una división que no solo sea EQ sino también EF y PE . Algunos autores llaman a dicha división "perfecta". ^{[ 4 ]}

El número mínimo de cortes necesarios para una división PE-EF-EQ depende de las valoraciones de los socios. En la mayoría de los casos prácticos (incluidos todos los casos en que las valoraciones son lineales a trozos), el número de cortes necesarios es finito. En estos casos, es posible encontrar tanto el número óptimo de cortes como su ubicación exacta. El algoritmo requiere un conocimiento completo de las valoraciones de los socios. ^{[ 4 ]}

Tiempo de ejecución

Todos los procedimientos anteriores son continuos: el segundo requiere un movimiento continuo de la cuchilla, y los demás requieren una representación gráfica continua de las dos medidas de valor. Por lo tanto, no pueden llevarse a cabo en un número finito de pasos discretos.

Esta propiedad de infinito es característica de los problemas de división que requieren un resultado exacto. Véase División exacta#Imposibilidad .

Un solo recorte: una división casi equitativa.

Una división casi equitativa es una división en la que los valores de los socios difieren como máximo en $\epsilon$ , para cualquier dado $\epsilon >0$ Se puede encontrar una división casi equitativa para dos socios en un tiempo finito y con un solo corte. ^{[ 5 ]}

Encontrar una división equitativa para tres o más socios.

Procedimientos de movimiento del cuchillo

El procedimiento de Austin se puede extender a n socios . Le da a cada socio una pieza con un valor subjetivo de exactamente $1/n$ Esta división es EQ, pero no necesariamente EX o EF o PE (ya que algunos socios pueden valorar la participación otorgada a otros socios como más que $1/n$ ).

Existe otro procedimiento, que utiliza n -1 cuchillas móviles, que puede emplearse para encontrar una asignación equitativa conectada para cualquier ordenación de los agentes. ^{[ 6 ]}^{: Sec.6.2}

Piezas conectadas: revelación completa

El procedimiento de revelación completa de Jones puede extenderse a $n$ socios de la siguiente manera: ^{[ 3 ]}

Para cada uno de los $n!$ posibles ordenamientos de los socios, escriba un conjunto de $n-1$ ecuaciones en $n-1$ variables: las variables son las $n-1$ puntos de corte, y las ecuaciones determinan la equidad para socios adyacentes. Por ejemplo, si hay 3 socios y el orden es A:B:C, entonces las dos variables son $x_{AB}$ (el punto de corte entre A y B) y $x_{BC}$ y las dos ecuaciones son $V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})$ y $V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)$ Estas ecuaciones tienen al menos una solución en la que todos los términos tienen el mismo valor.
De todos $n!$ en los pedidos, elija el pedido en el que el valor (igual) de todos los socios sea el mayor.

Tenga en cuenta que el valor equitativo máximo debe ser al menos $1/n$ , porque ya sabemos que una división proporcional (dando a cada socio al menos $1/n$ ) es posible.

Si las medidas de valor de los socios son absolutamente continuas entre sí (es decir, tienen el mismo soporte), entonces cualquier intento de aumentar el valor de un socio debe disminuir el de otro. Esto significa que la solución es PE entre las soluciones que dan piezas conexas.

Resultados de imposibilidad

Brams, Jones y Klamler estudian una división que comprende EQ, PE y EF (ellos llaman a dicha división "perfecta").

Primero demuestran que, para 3 socios que deben obtener piezas conectadas, una división EQ+EF puede no existir. ^{[ 3 ]} Lo hacen describiendo 3 medidas de valor específicas en un pastel unidimensional, en el que cada asignación EQ con 2 cortes no es EF.

Luego demuestran que, para 3 o más socios, una división PE+EF+EQ puede no existir incluso con piezas desconectadas. ^{[ 2 ]} Lo hacen describiendo 3 medidas de valor específicas en un pastel unidimensional, con las siguientes propiedades:

Con 2 recortes, cada asignación de EQ no es EF ni PE (pero hay asignaciones que son EF y 2-PE, o EQ y 2-PE).
Con 3 recortes, no todas las asignaciones de EQ son PE (pero hay una asignación de EQ+EF).
Con 4 recortes, no todas las asignaciones de EQ son EF (pero hay una asignación de EQ+PE).

Corte de pastel

Un pastel es un pastel con forma de círculo unidimensional (ver corte de pastel justo ).

Barbanel, Brams y Stromquist estudian la existencia de divisiones de un pastel que son tanto EQ como EF. Se demuestran los siguientes resultados de existencia sin proporcionar un algoritmo de división específico: ^{[ 7 ]}

Para dos socios, siempre existe una partición de un pastel que es a la vez libre de envidia y equitativa. Cuando las medidas de valor de los socios son absolutamente continuas entre sí (es decir, cada porción que tiene un valor positivo para un socio también lo tiene para el otro), entonces existe una partición que es libre de envidia, equitativa y no dominada.
Para tres o más socios, puede resultar imposible encontrar una distribución que sea a la vez libre de envidias y equitativa. Sin embargo, siempre existe una división que es equitativa y no está dominada.

bienes divisibles

El procedimiento del ganador ajustado calcula una división equitativa, libre de envidias y eficiente de un conjunto de bienes divisibles entre dos socios.

Complejidad de la consulta

No se puede encontrar una asignación equitativa de pastel utilizando un protocolo finito en el modelo de consulta de Robertson-Webb , incluso para 2 agentes. ^{[ 8 ]} Además, para cualquier ε > 0:

Un reparto de pasteles ε-equitativo conectado requiere al menos Ω(log ε ⁻¹ ) consultas. ^{[ 9 ]} Para 2 agentes, existe un protocolo O(log ε ^{−1 ).}^{[ 5 ]} Para 3 o más agentes, el mejor protocolo conocido requiere O( n (log n + log ε ⁻¹ )) consultas. ^{[ 10 ]}
Incluso sin conectividad, el reparto equitativo de pasteles ε requiere al menos Ω(log ε ⁻¹ / log log ε ⁻¹ ) consultas. ^{[ 8 ]}

Propiedades de las reglas de asignación máximamente equitativas

La regla de división máximamente equitativa es una regla que selecciona, entre todas las asignaciones equitativas de pastel, aquella en la que el valor común de los agentes es máximo. Tiene dos variantes:

La regla de equidad absoluta iguala los valores absolutos (no normalizados);
La regla de equidad relativa iguala los valores relativos (normalizados).

Siempre existe una asignación equitativa máxima conectada (tanto absoluta como relativa), y se puede encontrar utilizando un procedimiento generalizado de cuchillas móviles .

La regla de equidad absoluta es débilmente óptima en el sentido de Pareto y monótona en cuanto a recursos , pero no proporcional .
La regla de equidad relativa es débilmente Pareto-óptima y proporcional, pero no monótona en cuanto a recursos. ^{[ 6 ]}

Tabla resumen

Véase también

Reparto igualitario de la tarta : una asignación que maximiza la utilidad mínima de un agente. A menudo, la asignación igualitaria coincide con la equitativa, ya que si las utilidades son diferentes, la utilidad menor puede mejorarse transfiriendo parte de la tarta del agente con mayor utilidad.

Referencias

1 2 3 Jones, MA (2002). "Corte de pastel equitativo, libre de envidia y eficiente para dos personas y su aplicación a bienes divisibles". Mathematics Magazine . 75 (4): 275– 283. doi : 10.2307/3219163 . JSTOR 3219163 .
1 2 Steven j. Brams; Michael a. Jones; Christian Klamler (2013). "Corte de pastel para N personas: puede que no exista una división perfecta". The American Mathematical Monthly . 120 : 35. doi : 10.4169/amer.math.monthly.120.01.035 . S2CID 7929917 .
1 2 3 4 Steven J. Brams; Michael A. Jones; Christian Klamler (2007). "Mejores maneras de cortar un pastel - Revisado" (PDF) . Avisos de la AMS . Archivado del original (PDF) el 4 de marzo de 2016. Recuperado el 3 de agosto de 2015 .
1 2 3 Barbanel, Julius B.; Brams, Steven J. (2014). "Corte de pastel entre dos personas: el número óptimo de cortes". The Mathematical Intelligencer . 36 (3): 23. CiteSeerX 10.1.1.361.366 . doi : 10.1007/s00283-013-9442-0 . S2CID 189867346 .
1 2 3 Cechlárová, Katarína; Pillárová, Eva (2012). "Un algoritmo de corte de pasteles para dos personas casi equitativo". Optimización . 61 (11): 1321. doi : 10.1080/02331934.2011.563306 . S2CID 120300612 .
^ Segal - Halevi , Erel; Sziklai, Balázs R. (1 de septiembre de 2018). "Monotonicidad de recursos y monotonicidad de población en el corte de pasteles conectado" . Ciencias Sociales Matemáticas . 95 : 19– 30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .
↑ Barbanel, JB; Brams, SJ; Stromquist, W. (2009). "Cortar un pastel no es pan comido". American Mathematical Monthly . 116 (6): 496. CiteSeerX 10.1.1.579.5005 . doi : 10.4169/193009709X470407 .
1 2 Procaccia, Ariel D.; Wang, Junxing (2017-06-20). "Un límite inferior para el reparto equitativo de un pastel" . Actas de la Conferencia ACM de 2017 sobre Economía y Computación . EC '17. Cambridge, Massachusetts, EE. UU.: Association for Computing Machinery. págs. 479–495 . doi : 10.1145/3033274.3085107 . ISBN 978-1-4503-4527-9. S2CID 9834718 .
↑ Brânzei, Simina; Nisan, Noam (2018-07-13). "La complejidad de la consulta de Cake Cutting". arXiv : 1705.02946 [ cs.GT ].
↑ Cechlárová, Katarína; Pillárová, Eva (1 de noviembre de 2012). «Sobre la computabilidad de las divisiones equitativas» . Optimización discreta . 9 (4): 249– 257. doi : 10.1016/j.disopt.2012.08.001 . ISSN 1572-5286 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

[jones2002-1] 1 2 3 Jones, MA (2002). "Corte de pastel equitativo, libre de envidia y eficiente para dos personas y su aplicación a bienes divisibles". Mathematics Magazine . 75 (4): 275– 283. doi : 10.2307/3219163 . JSTOR 3219163 .

[bjk2011-2] 1 2 Steven j. Brams; Michael a. Jones; Christian Klamler (2013). "Corte de pastel para N personas: puede que no exista una división perfecta". The American Mathematical Monthly . 120 : 35. doi : 10.4169/amer.math.monthly.120.01.035 . S2CID 7929917 .

[bjk07-3] 1 2 3 4 Steven J. Brams; Michael A. Jones; Christian Klamler (2007). "Mejores maneras de cortar un pastel - Revisado" (PDF) . Avisos de la AMS . Archivado del original (PDF) el 4 de marzo de 2016. Recuperado el 3 de agosto de 2015 .

[bb2014-4] 1 2 3 Barbanel, Julius B.; Brams, Steven J. (2014). "Corte de pastel entre dos personas: el número óptimo de cortes". The Mathematical Intelligencer . 36 (3): 23. CiteSeerX 10.1.1.361.366 . doi : 10.1007/s00283-013-9442-0 . S2CID 189867346 .

[cp11-5] 1 2 3 Cechlárová, Katarína; Pillárová, Eva (2012). "Un algoritmo de corte de pasteles para dos personas casi equitativo". Optimización . 61 (11): 1321. doi : 10.1080/02331934.2011.563306 . S2CID 120300612 .

[:3-6] Segal - Halevi , Erel; Sziklai, Balázs R. (1 de septiembre de 2018). "Monotonicidad de recursos y monotonicidad de población en el corte de pasteles conectado" . Ciencias Sociales Matemáticas . 95 : 19– 30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .

[bbs09-7] Barbanel, JB; Brams, SJ; Stromquist, W. (2009). "Cortar un pastel no es pan comido". American Mathematical Monthly . 116 (6): 496. CiteSeerX 10.1.1.579.5005 . doi : 10.4169/193009709X470407 .

[:2-8] 1 2 Procaccia, Ariel D.; Wang, Junxing (2017-06-20). "Un límite inferior para el reparto equitativo de un pastel" . Actas de la Conferencia ACM de 2017 sobre Economía y Computación . EC '17. Cambridge, Massachusetts, EE. UU.: Association for Computing Machinery. págs. 479–495 . doi : 10.1145/3033274.3085107 . ISBN 978-1-4503-4527-9. S2CID 9834718 .

[:0-9] Brânzei, Simina; Nisan, Noam (2018-07-13). "La complejidad de la consulta de Cake Cutting". arXiv : 1705.02946 [ cs.GT ].

[:1-10] Cechlárová, Katarína; Pillárová, Eva (1 de noviembre de 2012). «Sobre la computabilidad de las divisiones equitativas» . Optimización discreta . 9 (4): 249– 257. doi : 10.1016/j.disopt.2012.08.001 . ISSN 1572-5286 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 7 ]