Corte de pastel equitativo

La reducción del pastel equitativa (EQ) es una especie de problema de reducción del pastel justo , en el que el criterio de equidad es la equitatividad . Es una distribución del 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, 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 pedazo 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, por cada trozo de pastel, devuelve un número que representa la utilidad del socio i de ese trozo. Por lo general, estas funciones están normalizadas 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 compararlos con otros criterios de equidad.

Encontrar un corte de pastel equitativo para dos socios

Un corte: revelación completa

Cuando hay 2 socios, es posible obtener una división EQ con un solo corte, pero requiere pleno conocimiento de las valoraciones de los socios. ^[1] Supongamos que la torta es el intervalo [0,1]. Para cada uno , calcule y tráquelos en la misma gráfica. 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 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 superior a 1/2.
• Es eficiente en 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 invertir de modo 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: sólo presentando medidas de probabilidad sinceras, un socio puede asegúrese de que reciba al menos la mitad del pastel. ^[1]

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

Variante de equidad proporcional

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 superávit - . El excedente se divide entre los socios en proporciones iguales . Entonces, por ejemplo, si A valora el excedente en 0,4 y B valora el excedente en 0,2, entonces A recibirá el doble de valor que B. Entonces, 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 cuchillo móvil de Austin le da a cada uno de los dos socios una pieza con un valor subjetivo de exactamente 1/2. Así la división es EQ, EX y EF. Requiere 2 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 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 recortes requeridos 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 su ubicación exacta. El algoritmo requiere pleno conocimiento 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 demás requieren un trazado continuo de las dos medidas de valor. Por lo tanto, no pueden llevarse a cabo en un número finito de pasos discretos.

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

Un recorte: 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 un determinado . Se puede encontrar una división casi equitativa para dos socios en un tiempo finito y con una sola parte. ^[5] ${\displaystyle \epsilon }$ ${\displaystyle \epsilon >0}$

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

Procedimientos con cuchillo en movimiento

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

Existe otro procedimiento, que utiliza n -1 cuchillas móviles, que se puede utilizar para encontrar una asignación equitativa conectada para cualquier orden de los agentes. ^{[6] : Sección 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, escriba 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 pedidos, elija el orden en el que el valor (igual) de todos los socios sea mayor. ${\displaystyle n!}$

Tenga en cuenta 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 apoyo), entonces cualquier intento de aumentar el valor de un socio debe disminuir el valor de 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 (a esta división la llaman "perfecta").

Primero prueban que, para 3 compañeros que deben conectar piezas, puede que no exista 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 de 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 valores específicos en un pastel 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 un pastel con forma de círculo unidimensional (ver corte de pastel justo ).

Barbanel, Brams y Stromquist estudian la existencia de divisiones de una tarta, que son a la vez EQ y EF. Los siguientes resultados de existencia se prueban sin proporcionar un algoritmo de división específico: ^[7]

• Para dos socios, siempre existe una división del 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 pieza que tiene un valor positivo para un socio también lo tiene para el otro), entonces existe una partición equitativa y libre de envidia. y no dominado.
• Para 3 o más socios, puede resultar imposible encontrar una asignación que sea equitativa y libre de envidia. Pero siempre existe una división que es a la vez equitativa y no 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 de pastel equitativa utilizando un protocolo finito en el modelo de consulta de Robertson-Webb , ni siquiera para 2 agentes. ^[8] Además, para cualquier ε > 0:

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

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

La regla de división máxima equitativa es una regla que selecciona, entre todas las asignaciones de pastel equitativas, 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 máxima equitativa conectada (tanto absoluta como relativa), y se puede encontrar mediante un procedimiento generalizado de cuchillos 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 óptima en términos de Pareto y proporcional, pero no monótona en cuanto a recursos. ^[6]

tabla resumen

Ver también

• Recorte igualitario : una 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 menor puede mejorarse moviendo una parte del pastel del agente con mayor utilidad.

Referencias

1. Jones, MA (2002). "Corte de pasteles equitativo, sin envidias y eficiente para dos personas y su aplicación a bienes divisibles". Revista Matemáticas . 75 (4): 275–283. doi :10.2307/3219163. JSTOR  3219163.
2. Steven j. bramas; Miguel a. Jones; Christian Klamler (2013). "Corte de pasteles de N personas: puede que no haya una división perfecta". El Mensual Matemático Estadounidense . 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: revisadas" (PDF) . Avisos de la AMS .
4. Barbanel, Julio B.; Brams, Steven J. (2014). "Corte de pastel entre dos personas: el número óptimo de cortes". El inteligente matemático . 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". Mensual Matemático Estadounidense . 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 corte de pasteles equitativo". Actas de la Conferencia ACM de 2017 sobre Economía y Computación . CE '17. Cambridge, Massachusetts, EE.UU.: Asociación de Maquinaria de Computación. págs. 479–495. doi :10.1145/3033274.3085107. ISBN 978-1-4503-4527-9. S2CID  9834718.
9. Brânzei, Simina; Nisán, Noam (13 de julio de 2018). "La complejidad de la consulta del corte de pasteles". 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}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )