Una división equitativa (EQ) es una división de un objeto heterogéneo (por ejemplo, un pastel ), en el que el valor subjetivo de todos los socios es el mismo, es decir, cada socio está igualmente feliz con su parte. Matemáticamente, eso significa que para todos los socios i y j :
Dónde:
- es el pedazo de pastel asignado al socio i ;
- es la función de valor del socio i . Es una función de valor real que, por cada pedazo de pastel, devuelve un número que representa la utilidad del socio i de ese pedazo. Por lo general, estas funciones se normalizan de manera que y por cada i .
Comparación con otros criterios
- Equidad (EQ) compara los valores de diferentes personas con diferentes piezas;
- Envy-freeness (EF) compara los valores de la misma persona con diferentes piezas;
- La división exacta (EX) compara los valores de diferentes personas con las mismas piezas.
La siguiente tabla ilustra la diferencia. En todos los ejemplos hay dos socios, Alice y Bob. Alice recibe la parte izquierda y Bob recibe la parte derecha.
División | EQ? | EF? | ¿EX? | |||||||
---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||
| (Alice y Bob no están de acuerdo con los valores de las piezas). | |||||||||
| (Alice y Bob se envidian mutuamente). | |||||||||
| (Alice disfruta de su parte más de lo que Bob disfruta de su parte). | |||||||||
| (Bob envidia a Alice). | |||||||||
|
Tenga en cuenta que la tabla tiene solo 6 filas, porque 2 combinaciones son imposibles: una división EX + EF debe ser EQ y una división EX + EQ debe ser EF.
Encontrar una división equitativa para dos socios
Un corte: revelación completa
Cuando hay 2 socios, es posible obtener una división de EQ 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, calcular y y trazarlos 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 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 Pareto eficiente (PE) entre todas las divisiones que utilizan un solo corte. Sin embargo, puede haber divisiones más eficientes que usen dos o más cortes. [2]
- Si la dirección del pastel se elige al azar (es decir, se puede voltear 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: solo mediante la presentación de 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 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. Suponga que el punto medio 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 deque B. Por lo tanto, este protocolo no es equitativo, pero sigue siendo EF. Es débilmente veraz en el siguiente sentido: un jugador con aversión al riesgo tiene un incentivo para informar su valoración real, porque informar una valoración falsa podría dejarlo con un valor menor.
Dos cortes: cuchillo móvil
El procedimiento de Austin con cuchilla móvil le da a cada uno de los dos socios una pieza con un valor subjetivo de exactamente 1/2. Por tanto, 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 solo sea EQ sino también EF y PE . Algunos autores llaman "perfecta" a esta división. [4]
El número mínimo de recortes 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 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 cuchillo que se mueva continuamente, los otros requieren un trazado continuo de las dos medidas de valor. Por tanto, no se pueden realizar 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. Ver 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, para cualquier dado . 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
Procedimiento de cuchilla móvil
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 o EF o PE (ya que algunos socios pueden valorar la participación entregada a otros socios como más de).
Piezas conectadas: revelación total
El procedimiento de revelación completo de Jones puede extenderse a socios de la siguiente manera: [3]
- Para cada uno de los posibles pedidos de los socios, escriba un conjunto de ecuaciones en variables: las variables son las 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 (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.
- Fuera de todo 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 , porque ya sabemos que una división proporcional (dando a cada socio al menos) es posible.
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 el 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 socios que deben tener piezas conectadas, es posible 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 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 tarta
Un pastel es un pastel con la forma de un 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. Los siguientes resultados de existencia se prueban sin proporcionar un algoritmo de división específico: [6]
- Para 2 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 pieza que tiene un valor positivo para un socio también tiene un valor positivo para el otro socio), entonces existe una partición libre de envidia, equitativa y no dominado.
- Para 3 o más socios, puede ser imposible encontrar una asignación que sea equitativa y sin envidias. Pero siempre existe una división que es equitativa y no dominada.
Bienes divisibles
El procedimiento de ganador ajustado calcula una división equitativa, sin envidia 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 usando un protocolo finito en el modelo de consulta de Robertson-Webb , incluso para 2 agentes. [7] Además, para cualquier ε> 0:
- Un corte de torta ε-equitativo conectado requiere al menos consultas Ω (log ε −1 ). [8] 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 ε −1 )). [9]
- Incluso sin conectividad, el corte de torta ε-equitativo requiere al menos consultas Ω (log ε −1 / log log ε −1 ). [7]
Tabla de resumen
Nombre | Tipo | # socios | # cortes | Propiedades |
---|---|---|---|---|
Jones [1] | Proceso de revelación completa | 2 | 1 (óptimo) | Ecualizador, EF, 1-PE |
Brams-Jones-Klamler [3] | Proceso de revelación completa | norte | n −1 (óptimo) | Ecualizador, ( n −1) -PE |
Austin | Proc de cuchilla móvil | 2 | 2 | EQ, EF, EX |
Austin | Proc de cuchilla móvil | norte | muchos | Ecualizador |
Barbanel-Brams [4] | Proceso de revelación completa | 2 | muchos | EQ, EF, PE |
Cechlárová-Pillárová [5] | Proc de aproximación discreta | 2 | 1 (óptimo) | near-EQ |
Referencias
- ↑ a b c Jones, MA (2002). "Corte de torta equitativo, sin envidias 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 .
- ^ a b Steven j. Brams; Michael a. Jones; Christian Klamler (2013). "Corte de pastel de N-persona: puede que no haya una división perfecta". The American Mathematical Monthly . 120 : 35. doi : 10.4169 / amer.math.monthly.120.01.035 . S2CID 7929917 .
- ^ a b c d Steven J. Brams; Michael A. Jones; Christian Klamler (2007). "Mejores formas de cortar un pastel: revisado" (PDF) . Avisos del AMS .
- ^ a b c Barbanel, Julius B .; Brams, Steven J. (2014). "Corte de pastel para 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 .
- ^ a b c d Cechlárová, Katarína; Pillárová, Eva (2012). "Un algoritmo casi equitativo de corte de pasteles para 2 personas". Optimización . 61 (11): 1321. doi : 10.1080 / 02331934.2011.563306 . S2CID 120300612 .
- ^ Barbanel, JB; Brams, SJ; Stromquist, W. (2009). "Cortar una tarta no es pan comido". American Mathematical Monthly . 116 (6): 496. CiteSeerX 10.1.1.579.5005 . doi : 10.4169 / 193009709X470407 .
- ^ a b Procaccia, Ariel D .; Wang, Junxing (20 de junio de 2017). "Un límite inferior para un corte de pastel equitativo" . Actas de la Conferencia ACM 2017 sobre Economía y Computación . EC '17. Cambridge, Massachusetts, EE. UU.: Asociación de Maquinaria de Computación: 479–495. doi : 10.1145 / 3033274.3085107 . ISBN 978-1-4503-4527-9. S2CID 9834718 .
- ^ Brânzei, Simina; Nisan, Noam (13 de julio de 2018). "La complejidad de la consulta del corte de pasteles". 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 .CS1 maint: varios nombres: lista de autores ( enlace )