Reparto proporcional de la torta con diferentes derechos

En el problema de la distribución justa de los beneficios , los socios suelen tener diferentes derechos. Por ejemplo, el recurso puede pertenecer a dos accionistas, de modo que Alice posee 8/13 y George 5/13. Esto conduce al criterio de proporcionalidad ponderada (WPR): existen varios pesos que suman 1, y cada socio debería recibir al menos una fracción del recurso según su propia valoración. ${\displaystyle w_{i}}$ ${\displaystyle i}$ ${\displaystyle w_{i}}$

Por el contrario, en el modo más simple de corte de pastel proporcional , los pesos son iguales: para todos ${\displaystyle w_{i}=1/n}$ ${\displaystyle i}$

Se pueden utilizar varios algoritmos para encontrar una división WPR.

Clonación

Supongamos que todos los pesos son números racionales, con denominador común . Por lo tanto, los pesos son , con . Para cada jugador , crea clones con el mismo valor-medida. El número total de clones es . Encuentra una distribución proporcional de la torta entre ellos. Finalmente, dale a cada compañero las piezas de sus clones. ${\displaystyle D}$ ${\displaystyle p_{1}/D,\dots ,p_{n}/D}$ ${\displaystyle p_{1}+\cdots +p_{n}=D}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$ ${\displaystyle D}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$

Robertson y Webb ^{[1] : 36} muestran un procedimiento más simple para dos socios: Alicia corta el pastel en pedazos iguales a sus ojos; Jorge selecciona los pedazos más valiosos a sus ojos, y Alicia toma los pedazos restantes. ${\displaystyle D}$ ${\displaystyle p_{G}}$ ${\displaystyle p_{A}}$

Este procedimiento simple requiere cortes que pueden ser muy grandes. Por ejemplo, si Alice tiene derecho a 8/13 y George a 5/13, entonces se necesitan 13-1=12 cortes en la partición inicial. ${\displaystyle D-1}$

El número de consultas requeridas es ${\displaystyle D\lceil \log _{2}(D)\rceil .}$

Particiones Ramsey

Supongamos que hay que dividir un pastel entre Alicia y Jorge, y que a Alicia le corresponde 8/13 y a Jorge 5/13. El pastel se puede dividir de la siguiente manera.

• Alicia corta el pastel en 6 pedazos con ratios de valoración 5:3:2:1:1:1 .
• George marca las piezas que tienen para él al menos el valor mencionado por Alicia.

Ahora bien, hay dos casos "buenos" -casos en los que podemos utilizar estas piezas para lograr una división proporcional ponderada respecto de los diferentes derechos-:

Caso 1: Hay un subconjunto de las piezas marcadas cuya suma es 5. Por ejemplo, si George marca la pieza 3 y las tres piezas 1, este subconjunto se le da a George y el resto se le da a Alice. George ahora tiene al menos 5/13 y Alice tiene exactamente 8/13.

Caso 2: Hay un subconjunto de las piezas sin marcar cuya suma es 8. Por ejemplo, si George marca la pieza 3 y solo una pieza 1, este subconjunto se le da a Alice y el resto se le da a George. Alice ahora tiene exactamente 8 y George ha renunciado a una suma menor que 8, por lo que tiene al menos 5/13.

Es posible demostrar que los casos buenos son los únicos casos posibles. Es decir, cada subconjunto de 5:3:2:1:1:1, O tiene un subconjunto que suma 5, O su complemento tiene un subconjunto que suma 8. Por lo tanto, el algoritmo anterior siempre encuentra una asignación WPR con las proporciones dadas. El número de cortes utilizados es solo 5.

McAvaney, Robertson y Webb ^{[1] : 36–41  [2]} generalizan esta idea utilizando el concepto de particiones de Ramsey (llamado así por la teoría de Ramsey ).

Formalmente: si y son números enteros positivos, una partición de se llama partición de Ramsey para el par , si para cualquier sublista , hay una sublista de cuya suma es , o hay una sublista de cuya suma es . ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$ ${\displaystyle P}$ ${\displaystyle k_{1}+k_{2}}$ ${\displaystyle k_{1},k_{2}}$ ${\displaystyle L\subseteq P}$ ${\displaystyle L}$ ${\displaystyle k_{1}}$ ${\displaystyle P\setminus L}$ ${\displaystyle k_{2}}$

En el ejemplo anterior, la partición es 5:3:2:1:1:1, que es una partición Ramsey. Además, esta es la partición Ramsey más corta en este caso, por lo que nos permite utilizar una pequeña cantidad de cortes. ${\displaystyle k_{1}=8}$ ${\displaystyle k_{2}=5}$

Las particiones de Ramsey siempre existen. Además, siempre hay una partición de Ramsey más corta. Se puede encontrar utilizando una variante simple del algoritmo de Euclides . El algoritmo se basa en el siguiente lema: ^{[1] : 143–144}

Si , y es una partición de , y , entonces es una partición de . Además, es una partición de Ramsey mínima para el par si-y-solo-si es una partición de Ramsey mínima para el par . ${\displaystyle p_{1}<a<b}$ ${\displaystyle P=(p_{1},\dots ,p_{n})}$ ${\displaystyle b}$ ${\displaystyle P'=(b,p_{1},\dots ,p_{n})}$ ${\displaystyle P'}$ ${\displaystyle a+b}$ ${\displaystyle P'}$ ${\displaystyle a,b}$ ${\displaystyle P}$ ${\displaystyle a,b-a}$

Este lema conduce al siguiente algoritmo recursivo.

${\displaystyle FindMinimalRamsey(a,b)}$:

1. Ordene las entradas de tal manera que . ${\displaystyle a<b}$
2. Empujar . ${\displaystyle a}$
3. Si , entonces presione y termine. ${\displaystyle a=b-a=1}$ ${\displaystyle 1,1}$
4. Si , entonces . ${\displaystyle b-a\neq 1}$ ${\displaystyle FindMinimalRamsey(a,b-a)}$

Una vez que se encuentra una partición Ramsey mínima, se puede utilizar para encontrar una división WPR respetando los derechos.

El algoritmo necesita al menos cortes, donde es la proporción áurea. En la mayoría de los casos, este número es mejor que hacer cortes. Pero si , entonces se necesitan cortes, ya que la única partición de Ramsey del par es una secuencia con unos. ${\displaystyle \log _{\phi }\min(a,b)}$ ${\displaystyle \phi =(1+{\sqrt {5}})/2}$ ${\displaystyle a+b-1}$ ${\displaystyle a=1}$ ${\displaystyle b=a+b-1}$ ${\displaystyle b,1}$ ${\displaystyle b+1}$

Cortar casi por la mitad

Supongamos de nuevo que Alicia tiene derecho a 8/13 y Jorge a 5/13. La torta se puede dividir de la siguiente manera.

• George corta el pastel en dos trozos en proporción 7:6.
• Alicia elige una de las piezas que vale para ella al menos el valor declarado. Consideremos dos casos:
  • Alicia elige el 7. Luego, Alicia tiene derecho a 1 pieza más y el trozo restante debe dividirse en una proporción de 5:1.
  • Alicia elige el 6. Luego, Alicia tiene derecho a 2 más y el trozo restante debe dividirse en una proporción de 5:2.
• En ambos casos, el trozo restante es más pequeño y la proporción es menor. Al final, la proporción se convierte en 1:1 y el pastel restante se puede dividir utilizando cortar y elegir .

La idea general es similar al protocolo Even-Paz : ^{[1] : 42–44} : ${\displaystyle CutNearHalves(a,b)}$

1. Ordene las entradas de tal manera que . Suponga que Alice tiene derecho a y George tiene derecho a . ${\displaystyle a<b}$ ${\displaystyle b/(a+b)}$ ${\displaystyle a/(a+b)}$
2. Pídale a George que corte el pastel en mitades casi iguales, es decir:
   • Si es par, entonces George corta el pastel en dos pedazos iguales a sus ojos; ${\displaystyle a+b}$
   • Si es impar, entonces George corta el pastel en dos pedazos cuya relación de valoración depende de sus ojos. ${\displaystyle a+b}$ ${\displaystyle (a+b-1)/2:(a+b+1)/2}$
3. Al menos una de las piezas vale para Alicia al menos el valor declarado por Jorge; dale esta pieza a Alicia.
4. Supongamos que la pieza tomada por Alice es la pieza con valor , donde . Llamar . ${\displaystyle c/(a+b)}$ ${\displaystyle c\in \{(a+b-1)/2,(a+b)/2,(a+b+1)/2)}$ ${\displaystyle CutNearHalves(b,a-c)}$

El algoritmo de corte cercano a la mitad necesita como máximo cortes, por lo que siempre es más eficiente que el algoritmo de particiones de Ramsey. ${\displaystyle \log _{2}\min(a,b)}$

El algoritmo de corte por la mitad no siempre es óptimo. Por ejemplo, supongamos que la proporción es 7:3.

• Para cortar casi por la mitad se pueden necesitar al menos cuatro cortes: primero, George corta en la proporción 5:5 y Alice obtiene 5. Luego, Alice corta en la proporción 3:2; supongamos que George elige el 2. Luego, George corta en la proporción 2:1; supongamos que Alice elige el 1. Finalmente, cortan y eligen el resto.
• Podemos hacerlo mejor si dejamos que George corte en una proporción de 6:4. Si Alice elige el 4, la proporción se convierte en 3:3 y podemos usar el método de cortar y elegir inmediatamente. Si Alice elige el 6, la proporción se convierte en 3:1. Alice corta en una proporción de 2:2, George elige el 2 y necesitamos un paso más de cortar y elegir. En total, se necesitan tres cortes como máximo.

La cuestión de cómo encontrar el mejor recorte inicial para cada proporción de derechos es una pregunta abierta.

El algoritmo se puede generalizar a n agentes; el número de consultas requeridas es ${\displaystyle n(n-1)\lceil \log _{2}(D)\rceil .}$

Cseh y Fleiner ^[3] presentaron un algoritmo para dividir una torta multidimensional entre cualquier número de agentes con cualquier derecho (incluidos los derechos irracionales), en un número finito de consultas. Su algoritmo requiere consultas en el modelo de consultas de Robertson-Webb ; por lo tanto, es más eficiente que la clonación de agentes y el corte casi a la mitad. Demuestran que esta complejidad de tiempo de ejecución es óptima. ${\displaystyle 2(n-1)\lceil \log _{2}(D)\rceil }$

Algoritmos para derechos irracionales

Cuando los derechos no son números racionales, no se pueden utilizar métodos basados ​​en clonación, ya que el denominador es infinito. Shishido y Zeng presentaron un algoritmo llamado mark-cut-choose , que también puede manejar derechos irracionales, pero con un número ilimitado de cortes. ^[4]

El algoritmo de Cseh y Fleiner también se puede adaptar para trabajar con derechos irracionales en un número finito de consultas. ^[5]

Número de cortes necesarios

Además del número de consultas necesarias, también es interesante minimizar el número de cortes necesarios, de modo que la división no quede demasiado fraccionada. Los algoritmos Shishido-Zeng producen una división justa con un máximo de cortes, y una división muy justa con un máximo de cortes. ^[4] ${\displaystyle 2\cdot 3^{n-2}}$ ${\displaystyle 4\cdot 3^{n-2}}$

En el peor de los casos, al menos podrían ser necesarios algunos cortes. Brams, Jones y Klamler ^[6] muestran un ejemplo para n = 2. Un pastel formado por cuatro regiones consecutivas debe dividirse entre Alice y George, cuyas valoraciones son las siguientes: ${\displaystyle 2(n-1)}$

Nótese que el valor total de la torta es 8 para ambos socios. Si , entonces Alice tiene derecho a un valor de al menos 6. Para darle a Alice su parte correspondiente en una porción conectada, debemos darle las tres porciones más a la izquierda o las tres porciones más a la derecha. En ambos casos George recibe una porción con un valor de solo 1, que es menor que su parte correspondiente de 2. Para lograr una división WPR en este caso, debemos darle a George su parte correspondiente en el centro de la torta, donde su valor es relativamente grande, pero entonces Alice recibirá dos porciones desconectadas. ^[7] ${\displaystyle w_{A}\geq 0.75}$

Segal-Halevi ^[8] muestra que, si la torta es circular (es decir, los dos puntos finales están identificados), entonces siempre es posible una división WPR conexa para dos personas; esto se desprende del teorema de Stromquist-Woodall . Al aplicar recursivamente este teorema para encontrar divisiones exactas , es posible obtener una división WPR utilizando como máximo cortes cuando n es una potencia de 2, y un número similar cuando n es general. ${\displaystyle 2n\cdot (\log _{2}n-1)+2}$

Crew, Narayanan y Spirkle ^[9] mejoraron este límite superior a 3 n -4 utilizando el siguiente protocolo:

• Pídale a cada agente i que marque una x tal que V _i (0, x )=1/2.
• Ordena a los agentes en orden creciente de su marca, rompiendo los empates arbitrariamente.
• Agregue los agentes en el orden anterior en un conjunto P. Deténgase justo antes de que el peso total de los agentes en P supere 1/2.
• El primer agente que no se agregó a P se llama t , y el conjunto de agentes después de t se llama Q . Ahora:
  • Todos los agentes en valor P (0, x ) tienen al menos 1/2, y su peso total es como máximo 1/2;
  • Todos los agentes en Q tienen un valor ( x,1 ) al menos de 1/2, y su peso total es como máximo de 1/2;
  • El agente t valora tanto (0,x) como ( x,1 ) exactamente 1/2.
• Si tanto P como Q no están vacíos, entonces el agente t se divide entre P y Q de modo que el peso total en cada conjunto sea exactamente 1/2. La torta se corta en x y el procedimiento continúa recursivamente. Esto conduce a la siguiente relación de recurrencia (donde k es el número de agentes en P , sin incluir el clon del agente t ): . Al agregar la condición inicial se obtiene el número reclamado . ${\displaystyle {\text{Cuts}}(n+1)\leq \max _{1\leq k\leq n-1}(1+{\text{Cuts}}(k+1)+{\text{Cuts}}(n-k+1))}$ ${\displaystyle {\text{Cuts}}(2)=2}$ ${\displaystyle {\text{Cuts}}(n)\leq 3n-4}$

• El caso más difícil es que P esté vacío (el caso de que Q esté vacío es análogo). Esto implica que el peso de t es al menos 1/2, y todos los agentes valoran (0, x ) como máximo 1/2. En este caso, encontramos algún y tal que el agente t valore (0, y ) exactamente w _t , e intentamos particionar los agentes en P y Q como antes. Si nuevamente uno de estos conjuntos está vacío, entonces sabemos que todos los agentes valoran (0, y ) al menos w _t . Por lo tanto, por el teorema del valor intermedio , debe haber un valor z en ( x , y ) para el cual uno de los agentes, que no es t , valore (0, z ) exactamente igual que t . Luego, podemos cortar el pastel en z y recurrir como en el primer caso.

El número exacto de cortes necesarios sigue siendo una pregunta abierta. El caso abierto más simple es cuando hay 3 agentes y los pesos son 1/7, 2/7, 4/7. No se sabe si el número de cortes necesarios es 4 (como en el límite inferior) o 5 (como en el límite superior).

Véase también

Zeng ^[10] presentó un algoritmo para un corte aproximado de pastel sin envidia con diferentes derechos.

Dall'Aglio y MacCheroni ^{[11] : El Teoría 3} demostró la existencia de un reparto proporcional de los beneficios con diferentes derechos incluso cuando las preferencias de los agentes se describen mediante relaciones de preferencia no aditivas, siempre que satisfagan ciertos axiomas.

Referencias

1. Robertson, Jack; Webb, William (1998). Algoritmos para cortar la torta: sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. Número de serie  97041258. OL  2730675W.
2. McAvaney, Kevin; Robertson, Jack; Webb, William (1992). "Particiones de Ramsey de números enteros y divisiones justas". Combinatorica . 12 (2): 193. doi :10.1007/bf01204722. S2CID  19376212.
3. Cseh, Ágnes; Fleiner, Tamás (1 de junio de 2020). "La complejidad de cortar la torta con porciones desiguales". ACM Transactions on Algorithms . 16 (3): 29:1–29:21. arXiv : 1709.03152 . doi :10.1145/3380742. ISSN  1549-6325. S2CID  218517351.
4. Shishido, Harunor; Zeng, Dao-Zhi (1999). "Algoritmos de marcación, selección y corte para divisiones justas y fuertemente justas". Decisión y negociación grupal . 8 (2): 125–137. doi :10.1023/a:1008620404353. ISSN  0926-2644. S2CID  118080310.
5. Cseh, Ágnes; Fleiner, Tamás (2018), "La complejidad de cortar la torta con porciones desiguales", Teoría de juegos algorítmica , Springer International Publishing, págs. 19-30, arXiv : 1709.03152 , doi :10.1007/978-3-319-99660-8_3, ISBN 9783319996592, Número de identificación del sujeto  19245769
6. Brams, SJ; Jones, MA; Klamler, C. (2007). "Corte de pastel proporcional". Revista internacional de teoría de juegos . 36 (3–4): 353. doi :10.1007/s00182-007-0108-z. S2CID  19624080.
7. Nótese que existe una división conectada en la que las razones entre los valores de los socios son 3:1: se le dan a Alice las dos porciones más a la izquierda y 8/11 de la tercera porción (valor 4+16/11=60/11) y se le dan a George las 3/11 restantes y la porción más a la derecha (valor 1+9/11=20/11). Sin embargo, esta partición no es WPR ya que ningún socio recibe su parte correspondiente.
8. Segal-Halevi, Erel (14 de marzo de 2018). "Corte de la torta con diferentes derechos: ¿cuántos cortes son necesarios?". Journal of Mathematical Analysis and Applications . 480 : 123382. arXiv : 1803.05470 . doi :10.1016/j.jmaa.2019.123382. S2CID  3901524.
9. Crew, Logan; Narayanan, Bhargav; Spirkl, Sophie (16 de septiembre de 2019). "División desproporcionada". arXiv : 1909.07141 [math.CO].
10. Zeng, Dao-Zhi (2000). "Procedimientos aproximados libres de envidia". Práctica de juegos: contribuciones de la teoría de juegos aplicada . Biblioteca de teoría y decisión. Vol. 23. Springer. págs. 259–271. doi :10.1007/978-1-4615-4627-6_17. ISBN 9781461546276.
11. Dall'Aglio, M.; MacCheroni, F. (2009). «Tierras en disputa» (PDF) . Juegos y comportamiento económico . 66 : 57–77. doi :10.1016/j.geb.2008.04.006.