Corte de pastel justo simétrico

El corte justo simétrico del pastel es una variante del problema del corte justo del pastel en el que la equidad se evalúa no solo por las partes del pastel, sino también por la participación en el corte.

Esencia

Consideremos un ejemplo: que se dé un pastel y se lo reparta entre Alicia y Jorge, cuyos gustos difieren, para que cada uno sienta que su parte se corta y elige justamente, es decir, para que cada uno tenga el valor de la parte por lo menos la mitad del valor de todo el pastel. Se podría usar la solución clásica de " divide y elige ": Alice corta el pastel en dos partes que son equivalentes a ella, y George elige una parte que considera más valiosa. Sin embargo, hay una falla en esta solución: Alice siempre obtiene una acción con un valor de 1/2, pero George puede recibir una acción con un valor superior a 1/2. Por lo tanto, este corte se llama justo , pero asimétrico , es decir, Alicia no ve nada de malo en qué parte eligió Jorge, pero siente injusto que fue Jorge quien eligió la parte y ella cortó el pastel.

Considere otra solución: tanto Alice como George marcan su límite (en el caso más simple, segmentos paralelos o coincidentes), que, desde el punto de vista de cada uno de ellos, divide el pastel en mitades iguales. Luego, el pastel se corta exactamente en el medio entre estos límites: denotemos como a la parte volumétrica del lóbulo izquierdo del pastel, en el que Alice se dividió, y como g - la parte volumétrica del lóbulo izquierdo del pastel, en el que George dividió, - luego el pastel debe cortarse por la mitad en dos partes, la parte volumétrica que queda es igual a . Si a < g , Alicia se queda con la pieza de la izquierda (cuyo valor es mayor que la parte de Alicia) y Jorge se queda con la pieza de la derecha (cuyo valor también es mayor). Si a > g , Alicia, por el contrario, obtiene la pieza correcta y Jorge la izquierda. Por lo tanto, esta solución al problema se llama justa y simétrica . ${\ estilo de visualización (a + g)/2}$

Esta idea fue propuesta por primera vez por Monabe y Okamoto [1] , quienes la llamaron libre de metaenvidia .

Se han propuesto varias opciones para el corte justo simétrico de la torta:

El corte justo anónimo del pastel requiere que no solo los valores sean iguales, sino que las piezas en sí mismas sean iguales [2] . Esto implica validez simétrica, pero la condición es más estricta. Por ejemplo, tal corte no es proporcionado por el procedimiento simétrico de dividir y elegir anterior, porque en el caso de a = g , el primer agente siempre obtiene la pieza más a la izquierda y el segundo siempre obtiene la pieza más a la derecha.
El corte justo de pasteles de Aristóteles solo requiere que los agentes con medidas idénticas reciban trozos con el mismo valor de evaluación [3] . Esto implica validez simétrica, pero la condición es más débil. Por ejemplo, se satisface con una versión asimétrica del procedimiento de dividir y elegir: si las puntuaciones de los agentes son idénticas, ambos jugadores son exactamente 1/2.

Definiciones

Hay un pastel C , generalmente representado como un segmento unidimensional. Hay n personas, y cada parte interesada i tiene una función de evaluación Vi que asigna subconjuntos de C a números no negativos.

El procedimiento de división es una función F que asigna n funciones de evaluación a una partición del intervalo C . La pieza que la función F asigna al agente i se denotará como . $F(V_{1},\dots,V_{n};i)$

Procedimiento simétrico

El procedimiento de división F se llama simétrico si para cualquier permutación p de índices (1,…, n ) y cualquier i

V_{i}(F(V_{1},\dots ,V_{n};i))=V_{i}(F(V_{p(1)},\dots ,V_{p(n )};p^{-1}(i)))

En particular, para n = 2 el procedimiento es simétrico si

V_{1}(F(V_{1},V_{2};1))=V_{1}(F(V_{2},V_{1};2))

y .

V_{2}(F(V_{1},V_{2};2))=V_{2}(F(V_{2},V_{1};1))

Esto significa que el agente 1 obtiene el mismo valor ya sea que juegue primero o segundo, y lo mismo ocurre con el agente 2.

En otro ejemplo, cuando n = 3, el requisito de simetría implica (entre otras cosas):

V_{1}(F(V_{1},V_{2},V_{3};1))=V_{1}(F(V_{2},V_{3},V_{1} ;3))=V_{1}(F(V_{3},V_{1},V_{2};2))

Procedimiento Anónimo

El procedimiento de división F se llama anónimo si para cualquier permutación p de índices (1,…, n ) y para cualquier $i$

F(V_{1},\dots ,V_{n};i)=F(V_{p(1)},\dots ,V_{p(n)};p^{-1}(i ))

Cualquier procedimiento anónimo es simétrico, porque si las piezas son iguales, sus estimaciones son ciertamente iguales.

Sin embargo, lo contrario no es cierto: es posible que la permutación le dé al agente diferentes piezas con los mismos valores.

Procedimiento aristotélico

El procedimiento de división F se llama aristotélico , si para : $V_{i}=V_{k}$

V_{i}(F(V_{1},\puntos, V_{n};i))=V_{k}(F(V_{1},\puntos,V_{n};k))

El criterio lleva el nombre de Aristóteles , quien escribió en su libro sobre ética: "...cuando se otorgan partes desiguales con igual propiedad, o cuando las personas son desiguales con partes iguales, aumenta el número de disputas y quejas".

Todo procedimiento simétrico es aristotélico. Sea p una permutación intercambiando i y k . De la simetría se sigue que

V_{i}(F(V_{1},\puntos, V_{i},\puntos,V_{k},\puntos,V_{n};i))=V_{i}(F( V_{1},\puntos,V_{k},\puntos,V_{i},\puntos,V_{n};k))

Pero como V i = V k , estas dos sucesiones de medidas son idénticas, de ahí la definición de Aristotélico.

Además, cualquier procedimiento de corte de pastel envidioso es aristotélico: de la ausencia de envidia se sigue que

V_{i}(F(V_{1},\dots ,V_{n};i))\geqslant V_{i}(F(V_{1},\dots ,V_{n};k) )V_{k}(F(V_{1},\puntos,V_{n};k))\geqslant V_{k}(F(V_{1},\puntos,V_{n};i))

Sin embargo, dado que , de dos desigualdades opuestas se sigue que ambos valores son iguales. $V_{i}=V_{k}$

Sin embargo, un procedimiento que satisfaga la condición más débil de cortar proporcionalmente el pastel no es necesariamente aristotélico. Cheese [3] dio un ejemplo con 4 agentes, en el que el procedimiento de Even-Paz para el corte proporcional de la torta puede dar valores diferentes para agentes con medidas de evaluación idénticas.

A continuación se resumen las relaciones entre los criterios:

Aristóteles simétrico anónimo $\a$ $\a$
Sin envidia Aristóteles $\a$
Sin Envidia Proporcional $\a$

Procedimientos

Cualquier procedimiento puede hacerse " a priori simétrico" por aleatorización. Por ejemplo, en un procedimiento asimétrico de dividir y elegir, el divisor se puede elegir lanzando una moneda. Sin embargo, dicho procedimiento no sería simétrico de hecho. Por lo tanto, la investigación sobre el corte de torta justo simétrico se centra en algoritmos deterministas .

Monabe y Okamoto [1] propusieron procedimientos deterministas simétricos sin envidia (“meta sin envidia”) para dos y tres agentes.

Nicolo y Yu [2] propusieron un protocolo de división anónimo y Pareto eficiente sin envidia para dos agentes. El protocolo implementa un equilibrio perfecto en subjuegos bajo el supuesto de que cada agente tiene información completa sobre las estimaciones de otros agentes.

El procedimiento de corte y selección simétricos para dos agentes se estudió empíricamente en experimentos de laboratorio [4] . Los procedimientos alternativos para el corte justo simétrico del pastel para dos participantes son la marca más a la derecha [5] y el resto más a la izquierda [6] .

Cheese [3] sugirió varios procedimientos:

El esquema general para transformar cualquier procedimiento de división envidiosa en un procedimiento determinista simétrico: realizamos el procedimiento original n ! veces, una vez por cada permutación de agentes, y elegir el resultado según el criterio topológico (es decir, por el mínimo de cortes). Este procedimiento se vuelve prácticamente inaplicable para n grande .
Un procedimiento proporcional aristotélico para n agentes que requiere consultas y un número polinomial de operaciones aritméticas. $O(n^{3})$
Un procedimiento proporcional simétrico para n agentes que requiere consultas, pero puede requerir un número exponencial de operaciones aritméticas. $O(n^{3})$

El procedimiento proporcional de Aristóteles

El procedimiento aristotélico de Cheese [3] para el corte proporcional de la torta amplía el procedimiento del " divisor único ". Por conveniencia, normalizamos las funciones de evaluación para que el valor de la torta completa para todos los agentes sea igual a n . El objetivo es asignar a cada agente una participación de al menos 1.

Un jugador es elegido arbitrariamente, lo que se llama dividir , corta el pastel en n partes, que evalúa exactamente en 1.
Se construye un grafo bipartito en el que cada vértice de X es un agente, cada vértice de Y es pan comido, y hay una arista entre el agente x y el pan panecillo y si y solo si x evalúa la parte y en al menos 1 . ${\ estilo de visualización G = (X + Y, E)}$
Buscamos el emparejamiento sin envidia de tamaño máximo (PBZ) en G (un emparejamiento en el que no hay ningún agente que no pertenezca al emparejamiento, sino que es adyacente, pertenece al pedazo de pastel coincidente). Tenga en cuenta que el divisor es adyacente a todas las n partes del pastel, por lo que (dónde está el conjunto de vecinos de X en Y ). Por tanto, existe un emparejamiento no vacío sin envidia [7] . Suponga sin pérdida de generalidad que PBZ empareja los agentes 1,..., k en piezas , dejando agentes y piezas de k +1 dr n sin emparejar . $|N_{G}(X)|=n\geqslant |X|$ ${\ estilo de visualización N_ {G} (X)}$ ${\ estilo de visualización X_ {1}, \ puntos, X_ {k})$
Para cualquier i de 1,…, k , para lo cual , le damos X i al agente i . Ahora, al divisor ya todos los agentes cuyas funciones de evaluación son idénticas a la función del divisor se les asignan fragmentos que tienen los mismos valores. $V_{i}(X_{i})=1$
Considere ahora los agentes i de 1,…, k para los cuales . Dividámoslos en subconjuntos con vectores iguales de evaluaciones de piezas . Para cada subconjunto , dividimos recursivamente sus piezas entre ellos (por ejemplo, si los agentes 1, 3, 4 están de acuerdo en los valores de todas las piezas 1,…, k , entonces dividimos las piezas recursivamente entre ellos). Ahora todos los agentes cuyas funciones de evaluación son idénticas se asignan a los mismos subconjuntos y comparten la subtorta cuyo valor entre ellos es mayor que su número, por lo que se cumple la precondición de recursividad. $V_{i}(X_{i})>1$ ${\ estilo de visualización X_ {1}, \ puntos, X_ {n}}$ ${\ estilo de visualización X_{1},X_{3},X_{4))$
Dividimos recursivamente los fragmentos no asignados entre los agentes no asignados. Tenga en cuenta que, debido a la falta de envidia en la coincidencia, cada agente no distribuido evalúa cada fragmento distribuido a menos de 1, por lo que los valores de los fragmentos restantes son al menos tan grandes como el número de agentes, por lo que la condición previa para la recursividad se conserva. ${\displaystyle X_{k+1},\puntos,X_{k))$

Notas

↑ 1 2 Manabe, Okamoto, 2010 , pág. 501–512.
↑ 1 2 Nicolò, Yu, 2008 , p. 268–289.
↑ 1 2 3 4 Cheze, 2018 .
↑ Kyropoulou, Ortega, Segal-Halevi, 2019 , p. 547–548.
↑ Segal-Halevi, Sziklai, 2018 , pág. 19-30.
↑ Ortega, 2019 .
↑ Segal-Halevi, Aigner-Horev, 2019 .

Literatura

Yoshifumi Manabe, Tatsuaki Okamoto. Protocolos de corte de torta sin meta-envidia // Actas de la 35.a Conferencia internacional sobre fundamentos matemáticos de la informática. - Berlín, Heidelberg: Springer-Verlag, 2010. - ISBN 9783642151545 .
Antonio Nicolo, Yan Yu. Divide y elige estratégicamente // Juegos y Comportamiento Económico. - 2008. - T. 64 , núm. 1 . — ISSN 0899-8256 . -doi : 10.1016/ j.geb.2008.01.006 .
Guillaume Chezé. ¡No llores por ser el primero! Existen algoritmos de división justa simétrica. - 2018. - arXiv : 1804.03833v1 .
Maria Kyropoulou, Josué Ortega, Erel Segal-Halevi. Fair Cake-Cutting in Practice // Actas de la Conferencia ACM de 2019 sobre economía y computación. — Nueva York, NY, EE. UU.: ACM, 2019. — ISBN 9781450367929 . -doi : 10.1145/ 3328526.3329592 . - arXiv : 1810.08243 .
Erel Segal-Halevi, Balazs R. Sziklai. Monotonicidad de recursos y monotonicidad de poblaciones en cortes de torta conectados // Ciencias Sociales Matemáticas. - 2018. - Vol. 95.- ISSN 0165-4896 . -doi : 10.1016/ j.mathsocsci.2018.07.001 . — arXiv : 1703.08928 .
Josué Ortega. Manipulaciones obvias en el corte de pasteles. - 2019. - arXiv : 1908.02988v1 .
Erel Segal-Halevi, Elad Aigner-Horev. Coincidencias sin envidia en grafos bipartitos y sus aplicaciones a la división justa. - 2019. - arXiv : 1901.09527v2 .