Reparto equitativo de la torta

El reparto equitativo de la torta (EQ) es un tipo de problema de reparto justo de la torta , en el que el criterio de equidad es la equidad . Es una distribución de la torta 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, eso significa que para todos los socios i y j :

${\displaystyle V_{i}(X_{i})=V_{j}(X_{j})}$

Dónde:

• ${\displaystyle X_{i}}$es el trozo de pastel asignado al socio i ;
• ${\displaystyle V_{i}}$es la medida del valor del socio i . Es una función de valor real que, para cada porción de pastel, devuelve un número que representa la utilidad del socio i a partir de esa porción. Por lo general, estas funciones se normalizan de modo que y para cada i . ${\displaystyle V_{i}(\emptyset )=0}$ ${\displaystyle V_{i}(EntireCake)=1}$

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

Encontrar un reparto equitativo de la torta para dos socios

Un corte - revelación completa

Cuando hay 2 socios, es posible obtener una división equitativa con un solo corte, pero requiere un conocimiento completo de las valoraciones de los socios. ^[1] Suponga que la torta es el intervalo [0,1]. Para cada , calcule y y grafíquelos 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 la torta en ese punto produce una división equitativa. Esta división tiene varias propiedades adicionales: ${\displaystyle x\in [0,1]}$ ${\displaystyle u_{1}([0,x])}$ ${\displaystyle u_{2}([x,1])}$

• 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 mayor a 1/2.
• Es Pareto eficiente (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 dar vuelta de tal manera que 0 se convierta en 1 y 1 se convierta en 0), entonces este procedimiento también es débilmente veraz, en el siguiente sentido: solo presentando medidas de probabilidad sinceras, un socio puede asegurar que recibe al menos la mitad del pastel. ^[1]

El mismo procedimiento se puede utilizar para dividir las tareas (con utilidad negativa).

Variante de proporcionalidad-equidad

El procedimiento de revelación completa tiene una variante ^[3] que satisface un tipo más débil de equidad y un tipo más fuerte de veracidad. El procedimiento primero encuentra los puntos medianos de cada socio. Supongamos que el punto mediano del socio A es y del socio B es , con . Entonces, A recibe y B recibe . Ahora hay un excedente - . El excedente se divide entre los socios en proporciones iguales . Entonces, por ejemplo, si A valora el excedente como 0,4 y B valora el excedente como 0,2, entonces A recibirá el doble de valor de 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 valoración verdadera, porque informar una valoración falsa podría dejarlo con un valor menor. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 0<a<b<1}$ ${\displaystyle [0,a]}$ ${\displaystyle [b,1]}$ ${\displaystyle [a,b]}$ ${\displaystyle [a,b]}$

Dos cortes - cuchillo en movimiento

El procedimiento de cuchilla móvil de Austin otorga a cada uno de los dos socios una pieza con un valor subjetivo de exactamente 1/2. Por lo tanto, la división es EQ, EX y EF. Requiere 2 cortes y le otorga 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 sólo sea EQ sino también EF y PE . Algunos autores llaman a esta 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 los que las valoraciones son lineales por partes), el número de cortes necesarios es finito. En estos casos, es posible encontrar tanto el número óptimo de cortes como sus ubicaciones exactas. 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 cuchillo que se mueve continuamente, los otros requieren un trazado continuo de las dos medidas de valor. Por lo tanto, no se pueden llevar a cabo en un número finito de pasos discretos.

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

Un corte: 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 , para cualquier . Una división casi equitativa para dos socios se puede encontrar en un tiempo finito y con un solo corte. ^[5] ${\displaystyle \epsilon }$ ${\displaystyle \epsilon >0}$

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

Procedimientos para mover cuchillos

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

Hay otro procedimiento, que utiliza n -1 cuchillos móviles, que se puede utilizar para encontrar una asignación equitativa conectada para cualquier ordenamiento de los agentes. ^{[6] : Sec.6.2}

Piezas conectadas - revelación completa

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

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

Nótese que el valor equitativo máximo debe ser al menos , porque ya sabemos que es posible una división proporcional (dando a cada socio al menos ). ${\displaystyle 1/n}$ ${\displaystyle 1/n}$

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

Resultados de imposibilidad

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

Primero prueban que, para 3 socios que deben obtener piezas conectadas, puede no existir una división EQ+EF. ^[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 prueban 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 una torta unidimensional, con las siguientes propiedades:

• Con 2 cortes, 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 cortes, cada asignación de EQ no es PE (pero hay una asignación de EQ+EF).
• Con 4 cortes, cada asignación de EQ no es EF (pero hay una asignación de EQ+PE).

Corte de pastel

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

Barbanel, Brams y Stromquist estudian la existencia de divisiones de un gráfico circular, 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 no genera envidia y es 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 tiene un valor positivo para el otro socio), entonces existe una partición que no genera envidia, es equitativa y no está dominada.
• Para tres o más socios, puede resultar imposible encontrar una distribución que sea a la vez justa y libre de envidias, pero siempre existe una división que sea a la vez justa y no dominada.

Bienes divisibles

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

Complejidad de la consulta

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

• Un corte de torta ε-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 protocolo más conocido requiere O( n (log n + log ε ⁻¹ )) consultas. ^[10]
• Incluso sin conectividad, el corte de pastel ε-equitativo requiere al menos Ω(log ε ⁻¹ / log log ε ⁻¹ ) consultas. ^[8]

Propiedades de las reglas de asignación de máxima equidad

La regla de reparto máximo-equitativo es una regla que selecciona, de entre todas las asignaciones de torta equitativas, aquella en la que el valor común de los agentes sea 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 máxima equitativa conectada (tanto absoluta como relativa), y se puede encontrar utilizando un procedimiento generalizado de cuchillos móviles .

• La regla de equidad absoluta es débilmente Pareto-óptima 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 torta : asignación que maximiza la utilidad más pequeña de un agente. A menudo, la asignación igualitaria coincide con la asignación equitativa, ya que si las utilidades son diferentes, la utilidad más pequeña puede mejorarse transfiriendo una parte de la torta del agente con la utilidad más grande.

Referencias

1. Jones, MA (2002). "Corte de torta equitativo, sin envidia y eficiente para dos personas y su aplicación a bienes divisibles". Revista de Matemáticas . 75 (4): 275–283. doi :10.2307/3219163. JSTOR  3219163.
2. Steven J. Brams; Michael A. Jones; Christian Klamler (2013). "Corte de la torta entre personas N: 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.
3. Steven J. Brams; Michael A. Jones; Christian Klamler (2007). "Mejores formas de cortar un pastel: revisitado" (PDF) . Avisos de la AMS .
4. 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. 
5. 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.
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.
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. 
8. Procaccia, Ariel D.; Wang, Junxing (20 de junio de 2017). "Un límite inferior para un reparto equitativo de los gastos". 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  .
9. Brânzei, Simina; Nisan, Noam (13 de julio de 2018). "La complejidad de la consulta del corte de pastel". arXiv : 1705.02946 [cs.GT].
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 )