Una división exacta , también llamada división par o división por consenso , es una división de un recurso heterogéneo (" torta ") en varios subconjuntos de tal manera que cada una de n personas con gustos diferentes coinciden en las valoraciones de las piezas. [1] : 127
Por ejemplo, considere un pastel que es mitad chocolate y mitad vainilla. Alice valora solo el chocolate y George valora solo la vainilla. El bizcocho se divide en tres piezas: una pieza contiene el 20% del chocolate y el 20% de la vainilla, la segunda contiene el 50% del chocolate y el 50% de la vainilla, y la tercera contiene el resto del bizcocho. Esta es una división de consenso, ya que tanto Alice como George valoran las tres piezas como 20%, 50% y 30% respectivamente.
Como ilustra el ejemplo, una división por consenso no es necesariamente justa. Por ejemplo, si la parte del 20% se le da a Alice y el 50% se le da a George, esto obviamente es injusto para Alice. En la teoría del pastel , las divisiones de consenso se utilizan a menudo como subrutinas para crear divisiones justas.
Las divisiones de consenso siempre existen, pero no se pueden encontrar mediante protocolos discretos (con un número finito de consultas). En algunos casos, las divisiones exactas se pueden encontrar mediante protocolos de cuchilla móvil. Se pueden encontrar divisiones casi exactas mediante protocolos discretos.
Definiciones
Dejar sean k pesos cuya suma sea 1. Suponga que todos los n socios valoran el pastel C como 1.
Una división exacta (también conocida como división de consenso ) en las proporcioneses una partición del bizcocho en k pedazos:, de modo que para cada socio iy cada pieza j :
Es decir, existe un consenso entre todos los socios de que el valor de la pieza j es exactamente. [1] : 127
División casi exacta
Para cada , Un -división casi exacta en las proporciones es una división en la que:
Es decir, existe un consenso entre todos los socios de que el valor de la pieza j es casi exactamente , donde la diferencia es menor que . [1] : 127
División perfecta
Una división perfecta es una división en la que un recurso se divide entre n socios con valoraciones subjetivas, dando a cada socio exactamente 1 / n del recurso de acuerdo con las valoraciones de todos los socios. Es un caso especial de división exacta en el que todos los pesos son 1 / n .
División exacta con número arbitrario de cortes
Pastel homogéneo por partes, muchos socios, cualquier peso
Una torta se llama homogénea por partes si se puede dividir en R regiones, de modo que todos los socios estén de acuerdo en que la densidad de valor en cada región es uniforme. Por ejemplo, considere un pastel circular en el que cada uno de sus 4 cuartos tiene una cobertura diferente. Los socios pueden valorar cada una de las coberturas de manera diferente, pero no distinguen entre diferentes piezas que tienen la misma cobertura. Esto significa que el valor de cada pieza para cada socio solo depende de la cantidad que obtienen de cada región.
Decir que el pastel es homogéneo por partes equivale a decir que las valoraciones de los socios son constantes por partes : cada trozo del pastel es homogéneo si y solo si es la intersección de n trozos de los n socios.
siempre que el pastel sea homogéneo por partes (y las valoraciones sean constantes por partes), se puede lograr una división por consenso de la siguiente manera:
- Divida cada región en k subregiones, de modo que la subregión j contenga exactamente de las regiones.
- Deje pieza j ser la unión de la j -ésima sub-regiones en todos los R regiones. Esto define una división de consenso con los pesos dados.
Este algoritmo se puede generalizar a familias de medidas de valor ligeramente más generales, como lineal por partes. [2]
El número de cortes necesarios es , donde R es el número de regiones.
Pastel general, muchos socios, cualquier peso.
Cuando las medidas de valor son contablemente aditivas y no atómicas , existe una partición de consenso para cada conjunto de pesos cuya suma sea 1. Este es un corolario del teorema de convexidad de Dubins-Spanier .
Woodall [3] demostró que es posible construir tal división de una torta de intervalo como una unión contable de intervalos.
INTUICIÓN: Considere el procedimiento de división para pasteles homogéneos por partes descrito anteriormente. En general, la torta no es homogénea por partes. Sin embargo, debido a que las medidas de valor son continuas, es posible dividir la torta en regiones cada vez más pequeñas de modo que las regiones se vuelvan cada vez más homogéneas. Cuándo, este proceso converge hacia una división por consenso.
Fremlin demostró que es posible construir tal división como una unión finita de intervalos.
Stromquist y Woodall [4] demostraron que es posible con un número mínimo de intervalos; véase el teorema de Stromquist-Woodall .
División exacta con un número mínimo de cortes
Suponga que el pastel es un intervalo formado por n distritos (subintervalos), y cada uno de los n socios valora solo un distrito. Entonces, una división consensuada del pastel en k subconjuntos requierecortes, ya que cada uno de los distritos debe cortarse en k piezas iguales a los ojos del socio que valora este distrito. Por tanto, resulta interesante saber si siempre es posible lograr una división por consenso con este número exacto de recortes.
Pastel de intervalo, dos socios, muchos subconjuntos, cualquier peso
Dos socios pueden lograr una división por consenso utilizando el procedimiento de cuchilla móvil de Austin .
El caso más simple es cuando los pesos son 1/2, es decir, quieren cortar un trozo que ambos acuerdan que sea la mitad del valor del bizcocho. Esto se hace de la siguiente manera. Un compañero mueve dos cuchillos sobre el pastel de izquierda a derecha, siempre manteniendo el valor entre los cuchillos exactamente 1/2. Es posible probar (mediante el teorema del valor intermedio ) que en algún momento, el valor de la pieza entre los cuchillos para el otro compañero también será exactamente 1/2. El otro socio grita "¡Alto!" en ese punto y se corta la pieza.
Se puede usar el mismo protocolo para cortar una pieza en la que ambos jugadores estén de acuerdo en que su valor es exactamente .
Al combinar varias de estas piezas, es posible lograr una división de consenso con cualquier proporción que sea números racionales. Pero esto puede requerir una gran cantidad de cortes.
Una mejor manera de lograr una división por consenso es identificar los dos puntos finales del pastel y tratarlo como un círculo. Es decir, cuando el cuchillo derecho llega al lado derecho, inmediatamente va al lado izquierdo, y la pieza entre los cuchillos ahora es en realidad la unión de la pieza a la derecha del cuchillo derecho y la pieza a la izquierda. del cuchillo izquierdo. De esta manera, es posible encontrar una división de consenso para cada. Un socio mueve los cuchillos cíclicamente alrededor del pastel, siempre manteniendo el valor entre ellos exactamente en p . Es posible demostrar que en algún momento, el valor de la pieza entre los cuchillos para el otro socio también será exactamente p . [5] El otro socio grita "¡Alto!" en ese punto y se corta la pieza. Esto requiere solo dos cortes.
Aplicando repetidamente el procedimiento anterior, es posible lograr una división por consenso entre dos socios y cualquier número de subconjuntos. El número de cortes es, dónde es el número de subconjuntos.
A partir de 2015, no se conoce una generalización de este procedimiento de cuchilla móvil a más de 2 socios. [6]
Pastel de intervalo, muchos socios, dos subconjuntos, pesos iguales
Suponga que el pastel es un intervalo de valor 1. Debe dividirse en subconjuntos, cada uno de los cuales tiene un valor de exactamente 1/2 para todos los n socios. Queremos utilizar el número mínimo de cortes, que es.
Una división como esta siempre existe. [7] Este es un corolario directo del teorema de Hobby-Rice . Esto también se puede demostrar con base en el teorema de Borsuk-Ulam : [8]
- Cada partición de un intervalo usando los cortes se pueden representar como un vector de longitud , en el que los elementos son las longitudes de los subintervalos.
- Cada elemento del vector puede ser positivo (si pertenece a la pieza n. ° 1) o negativo (si pertenece a la pieza n. ° 2).
- El conjunto de todas las particiones es la esfera. .
- Definir un de la siguiente manera: para cada partición x ,es un vector cuyo i -ésimo elemento es el valor de la pieza # 1 en esa partición de acuerdo con el socio i , menos 1/2.
- La función V es continua. Además, para todo x ,.
- Por tanto, según el teorema de Borsuk-Ulam , existe una x tal que. En esa partición, todos los socios valoran la pieza n. ° 1 (y la pieza n. ° 2) como exactamente 1/2.
Se puede encontrar una división de consenso en dos subconjuntos basada en el lema de Tucker , que es la versión discreta del teorema de Borsuk-Ulam . [9]
Aunque las preferencias de los socios se modelan con medidas, las pruebas no requieren que las medidas de valor sean aditivas sobre subconjuntos. Las medidas de valor también pueden ser funciones de conjunto continuo definidas en el sigma-álgebra de Borel y que satisfagan todas las propiedades de las medidas excepto la aditividad contable. Por lo tanto, no se requiere que las valoraciones de los socios sobre subconjuntos de la torta sean separables de forma aditiva. [9]
Pastel de intervalo, muchos socios, muchos subconjuntos, pesos iguales
El teorema de existencia de la subsección anterior se puede generalizar a partir de piezas a un número arbitrario de piezas. Esto fue demostrado por Noga Alon en su artículo de 1987 sobre el problema de la división del collar .
Existen diferentes medidas en el intervalo, todas absolutamente continuas con respecto a la longitud. La medida de todo el collar, según medida., es . Entonces es posible dividir el intervalo para partes (no necesariamente contiguas), de modo que la medida de cada parte, según medida , es exactamente . A lo sumo Se necesitan cortes, y esto es óptimo.
Pastel de intervalo, muchos socios, dos subconjuntos, pesos arbitrarios
El teorema de existencia de la subsección anterior se generaliza a pesos arbitrarios mediante el teorema de Stromquist-Woodall .
Pastel multidimensional, muchos socios, muchos subconjuntos, pesos iguales
La Piedra de Tukey teorema afirma que dadas n medibles "objetos" en n - dimensional espacio, es posible dividir todos ellos en medio (con respecto a su medida , es decir, volumen) con una sola ( n - 1) -dimensional hiperplano .
Dicho de otra manera: si el pastel es el espacio , y las medidas de valor de los socios son finitas y desaparecen en cualquier hiperplano dimensional, entonces hay un medio espacio cuyo valor es exactamente 1/2 para cada socio. Por tanto, existe una división por consenso que utiliza un solo corte.
La versión original de este teorema funciona solo si el número de dimensiones del pastel es igual al número de socios. Por ejemplo, no es posible utilizar este teorema para dividir un sándwich tridimensional en 4 o más socios.
Sin embargo, hay generalizaciones que permiten tal división. No utilizan un cuchillo hiperplano sino una superficie polinomial más complicada. [10]
Procedimientos de división casi exactos
Procedimiento de migajas y envasado
Para cualquier dado , se puede dar a cada socio una pieza de modo que todos los socios crean que los valores que tienen difieren en menos de , es decir, para cada i y cada j : [1] : 127
El procedimiento de división casi exacta consta de dos pasos: desmenuzado y empaquetado .
Paso de desmenuzado : el objetivo es cortar el bizcocho en pequeños trozos ("migas") de modo que cada socio asigne un valor suficientemente pequeño a cada miga. Esto se hace de la siguiente manera. Sea k una cierta constante. Pídale al compañero # 1 que corte el pastel en k pedazos que valore como 1 / k . Pídale al socio # 2 que recorte las piezas según sea necesario (utilizando como máximo k -1 cortes) de modo que cada pieza tenga un valor de como máximo 1 / k . Estas nuevas piezas, por supuesto, todavía tienen un valor de como máximo 1 / k para el socio n. ° 1. Continúe con los socios # 3, # 4,…, # n . Finalmente, todos los n socios valoran cada miga resultante como como máximo 1 / k .
Paso de empaquetado : el objetivo aquí es dividir las migajas en n subconjuntos, de modo que la suma de valores en cada subconjunto j esté cerca de w j . Aquí hay una explicación intuitiva del paso de empaquetado para dos socios (Alice y George) cuando los pesos son 1/2. [1] : 68–71
- Consigue un cuenco vacío.
- Introduce en el bol una de las migas.
- Si el valor en el tazón se vuelve más de la mitad para cualquiera de los socios, entréguele el tazón a ese socio y entregue las otras migajas al otro socio.
- De lo contrario (el valor en el tazón es menor que 1/2 para ambos socios), si el valor en el tazón es mayor para Alice que para George, entonces encuentre una miga cuyo valor para George sea mayor que su valor para Alice (tal miga debe existir porque la suma de valores de todas las migajas es 1 tanto para Alice como para George). Agregue esta miga al tazón y regrese al paso 2.
Es posible probar por inducción que la diferencia en la valoración del cuenco entre Alice y George es siempre como máximo 1 / k . Por lo tanto, cuando uno de los socios recibe el cuenco, su valor para ambos está entre 1 / 2-1 / k y 1/2 + 1 / k .
Formalmente, cada pieza se puede representar como un vector de valores, uno por socio. La longitud de cada vector está acotada, es decir, para cada vector v :. Nuestro objetivo es crear, para cada socio j , un vector cuyos elementos estén cerca de w j . Para hacer esto, tenemos que dividir los vectores en subconjuntos, de modo que la suma de vectores en cada subconjunto j sea lo suficientemente cercana a un vector cuyos elementos son w j . Esto es posible gracias a un teorema de V.Bergström, [11] [1] : 126-128
El procedimiento Crumb-and-Pack es una subrutina del protocolo Robertson-Webb . El último protocolo genera una división que es casi exacta y sin envidia .
Brams y Taylor proporcionan una explicación diferente del procedimiento de migajas y envasado. [12]
Mecanismos veraces
Cualquier algoritmo para la división por consenso se basa en las medidas de valor informadas por los socios. Si los socios saben cómo funciona el algoritmo, pueden tener un incentivo para mentir sobre sus medidas de valor para recibir más que su peso. Para evitar esto, se debe utilizar un mecanismo veraz . [2] [13]
El mecanismo de división veraz más simple es: seleccione un solo socio al azar (con probabilidades determinadas por los pesos) y entréguele todo el pastel. Este mecanismo es trivialmente veraz porque no hace preguntas. Además, es un consenso en la expectativa: el valor esperado de cada socio es exactamente su peso, y esto es cierto de acuerdo con todas las medidas de valor. Sin embargo, la división resultante no es, por supuesto, una división por consenso.
Se puede construir un mejor mecanismo veraz, que funcione para el caso en el que todos los pesos sean 1 / n , dado cualquier algoritmo (u oráculo) existente para encontrar una división de consenso:
- Pídale a cada socio que informe su medida de valor.
- Utilice el algoritmo / oráculo existente para generar una partición en la que todas las n piezas sean exactamente 1 / n de acuerdo con las funciones de valor informadas por los socios.
- Realice una permutación aleatoria en la partición de consenso y entregue a cada socio una de las piezas.
Aquí, el valor esperado de cada socio sigue siendo 1 / n independientemente de la función de valor informado, por lo que el mecanismo sigue siendo veraz: ningún socio puede ganar nada con la mentira. Además, a un socio veraz se le garantiza un valor de exactamente 1 / n con probabilidad 1 (no solo en expectativa). Por tanto, los socios tienen un incentivo para revelar sus verdaderas funciones de valor.
Imposibilidad
Es imposible lograr una división exacta con un número finito de consultas, incluso si solo hay 2 socios y los pesos son exactamente 1/2. [1] : 103–104 Esto significa que lo mejor que podemos lograr usando un algoritmo discreto es una división casi exacta.
Prueba : cuando el protocolo está en el paso k , tiene una colección de k piezas como máximo . Para proporcionar una división exacta, el protocolo debe encontrar un subconjunto exacto - un subconjunto de las piezas que ambos socios valoran exactamente como 1/2. Vamos a demostrar que, para cada k , hay situaciones en las que en el paso k no hay un subconjunto exacto y, por lo tanto, el protocolo podría tener que continuar interminablemente.
Inicialmente, solo hay una pieza que ambos socios valoran como 1, por lo que obviamente no hay un subconjunto exacto. Después de un paso, como máximo un socio (digamos, Alice) ha tenido la opción de cortar el pastel. Incluso si Alice corta el pastel en dos partes que son iguales en su opinión, pueden ser diferentes en la opinión de George, así que nuevamente no hay un subconjunto exacto.
Supongamos ahora que estamos en el paso ky hay k piezas. Sin pérdida de generalidad, podemos suponer que cada pieza tiene un valor distinto de cero para ambos socios. Esto se debe a que, si Alice (por ejemplo) corta una pieza que valora como 0, es posible que George también valore la misma pieza como 0, por lo que podemos descartar esta pieza y continuar con las otras piezas.
El número total de subconjuntos diferentes ahora es 2 k , y según el supuesto de inducción ninguno de ellos es exacto. En el paso k , el protocolo puede pedirle a Alice o George que corten una determinada pieza en dos. Supongamos que el cortador es George y que corta la pieza X en dos subpuestos: X1 y X2. Ahora, el número total de subconjuntos es 2 k +1 : la mitad de ellos ya existían y, por supuesto, no son exactos, por lo que la única posibilidad del protocolo de encontrar un subconjunto exacto es mirar los nuevos subconjuntos. Cada nuevo subconjunto está formado por un antiguo subconjunto en el que la pieza X ha sido reemplazada por X1 o X2. Dado que George es el cortador, puede cortar de una manera que haga que uno de estos subconjuntos sea un subconjunto exacto para él (por ejemplo, si un determinado subconjunto que contiene la pieza X tiene un valor de 3/4, George puede cortar X de manera que X1 tenga un valor de 1/4 en su opinión, por lo que el nuevo subconjunto tiene un valor de exactamente 1/2). Pero, George no conoce la valoración de Alice y no puede tenerla en cuenta al cortar. Por tanto, existe una infinidad incontable de valores diferentes que las piezas X1 y X2 pueden tener para Alice. Dado que el número de subconjuntos nuevos es finito, hay un número infinito de casos en los que ningún subconjunto nuevo tiene un valor de 1/2 para Alice, por lo que ningún subconjunto nuevo es exacto.
Comparación con otros criterios
Una división exacta con pesos iguales () es, en particular, también proporcional , sin envidias y equitativo .
Sin embargo, no es necesariamente Pareto eficiente , ya que en muchos casos es posible aprovechar las valoraciones subjetivas y dividir los recursos de tal manera que todos los socios reciban más de lo que les corresponde..
Las divisiones exactas son mucho más fáciles si los participantes cooperan para establecer derechos en lugar de competir como en una división justa . Algunos autores se refieren a esto como división por consenso o reducción a la mitad por consenso . [14]
Tabla de resumen
Nombre | Tipo | Pastel | Valoraciones [15] | #partners ( n ) | #subconjuntos ( k ) | #cortes | pesos |
---|---|---|---|---|---|---|---|
Austin | Procedimiento de cuchilla móvil | Intervalo | Estafa | 2 | Muchos | (óptimo) | Alguna |
Homogéneo por partes | Procedimiento discreto | Homogéneo por partes | Con + Agregar + Pwl | Muchos | Muchos | Num. de distritos | Alguna |
Dubins – Spanier | Prueba de existencia | Alguna | Con + Agregar | Muchos | Muchos | Ilimitado | Alguna |
Reducción a la mitad del consenso | Procedimiento infinito | Intervalo | Estafa | Muchos | 2 | n (óptimo) | Igual |
División de collar | Prueba de existencia | Intervalo | Con (+ Agregar?) | Muchos | Muchos | (óptimo) | Igual |
Stromquist-Woodall | Prueba de existencia | Circulo | Con + Agregar | Muchos | 2 | (óptimo para algunos pesos) | Alguna |
Stone – Tukey | Prueba de existencia | n- dimensional | Con (+ Agregar?) | norte | 2 | 1 semiplano | Igual |
Miga y paquete | Procedimiento casi exacto | Alguna | Con + Agregar | Muchos | Muchos | Ilimitado | Alguna |
Ver también
- Corte justo de pasteles
- Problema del Nilo
- División ferial estratégica
Referencias
- ^ a b c d e f g Robertson, Jack; Webb, William (1998). Algoritmos para cortar pasteles: sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN 97041258 . OL 2730675W .
- ^ a b Chen, Yiling; Lai, John K .; Parkes, David C .; Procaccia, Ariel D. (2013). "Verdad, justicia y corte de pastel" . Juegos y comportamiento económico . 77 (1): 284-297. doi : 10.1016 / j.geb.2012.10.009 .
- ^ Woodall, DR (1980). "Dividir un pastel de forma justa" . Revista de Análisis y Aplicaciones Matemáticas . 78 : 233–247. doi : 10.1016 / 0022-247x (80) 90225-5 .
- ^ Stromquist, Walter; Woodall, DR (1985). "Conjuntos en los que coinciden varias medidas" . Revista de Análisis y Aplicaciones Matemáticas . 108 : 241–248. doi : 10.1016 / 0022-247x (85) 90021-6 .
- ^ Fischer, Daniel. "División de consenso de un pastel a dos personas en proporciones arbitrarias" . Math.SE . Consultado el 23 de junio de 2015 .
- ^ Hay una generalización que da a cada uno de n socios, una pieza que vale exactamentepara él. Pero esta no es una división por consenso, porque los socios pueden no ponerse de acuerdo sobre el valor de las otras piezas además de la pieza asignada a ellos. Consulte los procedimientos de Austin con cuchillas móviles. # Muchos socios .
- ^ Goldberg, Charles H .; West, Douglas B. (1985). "Bisección de colorantes circulares". Revista SIAM de Métodos Algebraicos y Discretos . 6 : 93-106. doi : 10.1137 / 0606010 .
- ^ Alon, Noga; West, Douglas B. (1986). "El teorema de Borsuk-Ulam y bisección de collares" . Actas de la American Mathematical Society . 98 (4): 623. doi : 10.1090 / s0002-9939-1986-0861764-9 .
- ^ a b Simmons, Forest W .; Su, Francis Edward (2003). "Consenso-reducción a la mitad a través de teoremas de Borsuk-Ulam y Tucker". Ciencias Sociales Matemáticas . 45 : 15-25. CiteSeerX 10.1.1.203.1189 . doi : 10.1016 / S0165-4896 (02) 00087-2 .
- ^ B. Grünbaum (1960). "Particiones de distribuciones de masa y cuerpos convexos por hiperplanos" . Pacific J. Math . 10 (4): 1257–1261. doi : 10.2140 / pjm.1960.10.1257 . Señor 0124818 .
- ^ V. Bergström (1930). "Zwei Sätze über ebene Vectorpolygone". Hamburgische Abhandlungen . 8 : 205–219.
- ^ Brams, Steven J .; Taylor, Alan D. (1996). División justa [ Del corte de pasteles a la resolución de disputas ]. págs. 131-133. ISBN 978-0-521-55644-6.
- ^ Mossel, Elchanan; Tamuz, Omer (2010). División justa veraz . Apuntes de conferencias en informática. 6386 . págs. 288-299. arXiv : 1003.5480 . doi : 10.1007 / 978-3-642-16170-4_25 . ISBN 978-3-642-16169-8.
- ^ de Longueville, Mark; Živaljević, Rade T. (2008). "Partiendo collares multidimensionales" . Avances en Matemáticas . 218 (3): 926–939. arXiv : matemáticas / 0610800 . doi : 10.1016 / j.aim.2008.02.003 .
- ^ Prerrequisitos sobre las funciones de valor de los socios. Menos requisitos previos significan que el resultado es más general. Con = Continuous es el más general; Con + Add = Additive es menos general; Con + Add + Pwl = Piecewise-linear es el menos general.