Corte de pastel eficiente

El reparto eficiente de la tarta es un problema de economía y de informática . Implica un recurso heterogéneo , como una tarta con diferentes coberturas o una tierra con diferentes revestimientos, que se supone que es divisible (es posible cortar trozos arbitrariamente pequeños sin destruir su valor). El recurso tiene que dividirse entre varios socios que tienen diferentes preferencias sobre distintas partes de la tarta, es decir, algunas personas prefieren las coberturas de chocolate, otras prefieren las cerezas, algunas simplemente quieren un trozo lo más grande posible, etc. La asignación debería ser económicamente eficiente . Se han estudiado varias nociones de eficiencia:

• El concepto más común es el de eficiencia en el sentido de Pareto , que significa que ninguna otra asignación es mejor para al menos un participante y al menos tan buena para todos.
• Un concepto más débil es el de no derroche . Una asignación no es derrochadora si ningún agente recibe un trozo de tarta que vale 0 para él o ella y que vale más que 0 para otro agente.

La mayoría de las veces, la eficiencia se estudia en relación con la equidad , y el objetivo es encontrar una división que satisfaga tanto los criterios de eficiencia como los de equidad.

Definiciones

Hay una torta . Generalmente se supone que es un segmento unidimensional finito, un polígono bidimensional o un subconjunto finito del plano euclidiano multidimensional . ${\displaystyle C}$ ${\displaystyle \mathbb {R} ^{d}}$

Hay socios. Cada socio tiene una función de valor subjetiva que asigna subconjuntos de números. ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle V_{i}}$ ${\displaystyle C}$

${\displaystyle C}$debe dividirse en subconjuntos disjuntos, de modo que cada persona reciba un subconjunto disjunto. La parte asignada a la persona se llama , de modo que . ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle X_{i}}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n}}$

En las siguientes líneas consideramos un pastel con cuatro partes: chocolate, vainilla, limón y azúcar, y dos agentes: Alice y George, con las siguientes valoraciones:

Se dice que una asignación es derrochadora si asigna a un agente una parte que vale 0 para ese agente pero que vale más que 0 para otro agente. En símbolos: ${\displaystyle X}$

${\displaystyle \exists {i,j}:\exists Z\subseteq X_{i}:V_{i}(Z)=0~~{\text{and}}~~V_{j}(Z)>0}$y . ${\displaystyle \exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}$

De lo contrario, se denomina no derrochador (NW). En el ejemplo de la torta, una asignación que le dé toda la torta a Alice es NW, pero una asignación que le dé toda la torta a George es derrochadora porque la parte de limón se "desperdicia". Hay muchas otras asignaciones NW, por ejemplo, darle el chocolate a George y el resto de la torta a Alice es NW.

Una asignación domina en el sentido de Pareto una asignación , si al menos una persona considera que es mejor que , y ninguna persona considera que es peor que . En símbolos: ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$

${\displaystyle \forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})}$y ${\displaystyle \exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}$

Una asignación se denomina óptima de Pareto (OP) si no está dominada por ninguna otra división, es decir, no se puede mejorar sin objeciones. En el ejemplo del pastel, dar el pastel entero a Alicia es OP, pero dar el pastel entero a Bob está dominado por Pareto por la asignación en la que la parte de limón se le da a Alicia. En general (cuando no hay requisitos de conectividad en las porciones), cada asignación derrochadora está dominada por Pareto, por lo tanto, cada asignación OP es NW. Sin embargo, lo opuesto no es cierto. Por ejemplo, la asignación que da el chocolate a Jorge y el pastel restante a Alicia es NW pero no es PO - está dominada por Pareto por la asignación que da a Jorge la vainilla y la mitad del chocolate. Esto se debe a que, en la asignación original, las utilidades de (Alicia, Jorge) son (3, 6), mientras que en la asignación alternativa las utilidades son (5,5, 7). ${\displaystyle X}$

Existencia y computación

Siempre existen asignaciones eficientes. Por ejemplo, cada reparto utilitarista óptimo es PO, por lo tanto también NW.

Sin embargo, encontrar tales asignaciones puede ser difícil. Puede ser imposible encontrar una asignación de torta NW usando un número finito de consultas "mark" y "eval", incluso si solo hay dos agentes con valoraciones uniformes por partes . ^{[1] : 9, Clm.3} Esto se debe a que, después de cualquier número finito de tales consultas, el algoritmo tiene información sobre solo un número finito de intervalos y, por lo tanto, no puede evitar el desperdicio dentro de los intervalos: para cualquier asignación de un intervalo a un agente, es posible que este agente valore una parte de este intervalo en 0 mientras que el otro agente valora la misma parte en 1. Por lo tanto, PO tampoco es alcanzable mediante un protocolo finito. ^{[2] : 560, Thm.5}

El problema se vuelve fácil bajo el supuesto de positividad estricta (cada agente valora cada punto de la torta en estrictamente más de 0): cada asignación es trivialmente NW, y cada asignación que da toda la torta a un solo agente es trivialmente PO (ya que cualquier otra asignación da a este agente una utilidad estrictamente menor).

El problema también es fácil para un algoritmo que utiliza revelación directa en lugar de consultas. En un algoritmo de revelación directa, cada agente revela su función de valoración completa al algoritmo; esto es posible, por ejemplo, con valoraciones constantes por partes . Con la revelación directa, es fácil encontrar una asignación utilitarista óptima (dando cada parte a un agente que la valore más), y dicha asignación también es PO y NW.

Combinando eficiencia y equidad

A menudo, es necesario encontrar una distribución que no sólo sea eficiente sino también justa según diversas nociones de equidad. La existencia sigue siendo válida:

• Siempre existe una asignación PO que también es proporcional . Por ejemplo, siempre existe una asignación que maximiza la suma de valores sujetos a proporcionalidad (ya que el conjunto de todas las asignaciones proporcionales es compacto) y es PO (ya que la proporcionalidad se conserva mediante mejoras de Pareto).
• Además, siempre existe una asignación de PO que también está libre de envidia . Esto no se deduce directamente del argumento anterior, ya que la ausencia de envidia no se conserva mediante mejoras de Pareto. Sin embargo, se demuestra explícitamente como el teorema de Weller .

Encontrar dichas asignaciones puede ser difícil incluso con valoraciones estrictamente positivas, dependiendo del modelo computacional:

• En el modelo de consulta, ningún algoritmo finito que le dé a cada agente una fracción positiva de la torta puede ser PO, incluso con solo dos agentes con valoraciones estrictamente positivas. Esto se debe a que un algoritmo finito siempre conoce los valores de un número finito de intervalos, por lo que no puede evitar ineficiencias dentro de los intervalos: para cualquier asignación de los intervalos, puede haber un intercambio rentable de subintervalos que el algoritmo no puede detectar.
• En el modelo de revelación directa (con valoraciones constantes por partes ), el algoritmo de equilibrio de mercado ^[3] produce una asignación libre de PO y envidia (por lo tanto, proporcional) en tiempo polinomial para cualquier número de agentes.

Combinando eficiencia con equidad y conectividad

A menudo, además de la eficiencia y la equidad, existen restricciones geométricas sobre las porciones. Por ejemplo, si la torta es un intervalo, entonces cada agente puede requerir una porción que sea un intervalo contiguo. Con este requisito adicional:

• Siempre existe una asignación de PO que también es proporcional. Esto se debe a que el conjunto de todas las asignaciones proporcionales contiguas sigue siendo compacto y la proporcionalidad se conserva mediante mejoras de Pareto.
• Una asignación de PO que también esté libre de envidia podría no existir cuando hay al menos tres agentes, incluso si tienen valoraciones constantes por partes. ^{[4] : Ejemplo 5.1}

Desde una perspectiva computacional:

• En el caso de las valoraciones generales, cuando las densidades de valor son estrictamente positivas, dividir y elegir es PO y proporcional para dos agentes. Supongamos que Alice corta, George elige la pieza más a la izquierda y Alice obtiene la pieza más a la derecha. Cualquier asignación alternativa en la que George obtiene la izquierda y Alice obtiene la derecha no puede ser una mejora de Pareto, ya que (según el supuesto de positividad estricta) cualquier movimiento del lugar de corte hacia la izquierda perjudica a George, y cualquier movimiento hacia la derecha perjudica a Alice. Cualquier asignación alternativa en la que George obtiene la derecha y Alice obtiene la izquierda no puede ser una mejora de Pareto, ya que en cualquier asignación de ese tipo, al menos uno de ellos debe obtener menos de la mitad del valor total, mientras que en la asignación original ambos obtienen al menos la mitad.
• Con valoraciones constantes por partes, el algoritmo de equilibrio de mercado no necesariamente produce partes conectadas, por lo que no funciona. Sin embargo, se puede utilizar un algoritmo similar a ^{[5] : 317, Teoría 5} para encontrar una asignación proporcional que maximice la suma de utilidades para cualquier número de agentes, mediante la resolución de programas lineales (donde m es el número de partes). ${\displaystyle O(m^{n})}$

Actualmente no se sabe si, para 3 o más agentes con valoraciones estrictamente positivas, se puede encontrar una asignación de PO proporcional conectada utilizando un número finito de consultas (en el modelo de consulta) o utilizando un algoritmo polinomial (en el modelo de revelación directa).

Valoraciones no aditivas

Si la torta es un intervalo unidimensional y cada persona debe recibir un intervalo conectado, se cumple el siguiente resultado general: si las funciones de valor son estrictamente monótonas (es decir, cada persona prefiere estrictamente un trozo sobre todos sus subconjuntos propios), entonces cada división EF también es PO (nótese que esto no es cierto si los agentes pueden recibir trozos desconectados). Por lo tanto, en este caso, los protocolos Simmons–Su crean una división PO+EF.

Si el pastel es un círculo unidimensional (es decir, un intervalo cuyos dos extremos están identificados topológicamente) y cada persona debe recibir un arco conexo, entonces el resultado anterior no se cumple: una división EF no es necesariamente PE. Además, hay pares de funciones de valor (no aditivas) para las que no existe una división PO+EF. Sin embargo, si hay 2 agentes y al menos uno de ellos tiene una función de valor aditiva, entonces existe una división PO+EF. ^[6]

Véase también

• Corte de pastel utilitario
• Corte de pastel de feria
• El precio de la justicia

Referencias

1. Ianovski, Egor (1 de marzo de 2012). "Mecanismos de corte de tortas". arXiv : 1203.0100 [cs.GT].
2. Kurokawa, David; Lai, John K.; Procaccia, Ariel D. (30 de junio de 2013). "Cómo cortar un pastel antes de que termine la fiesta". Vigésima séptima conferencia de la AAAI sobre inteligencia artificial . 27 : 555–561. doi : 10.1609/aaai.v27i1.8629 . S2CID  : 12638556.
3. Aziz, Haris; Ye, Chun (14-17 de diciembre de 2014). "Algoritmos de corte de pastel para valoraciones constantes por partes y uniformes por partes". En Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). Economía de Internet y la Web . Décima Conferencia Internacional, Economía de Internet y la Web, Pekín, China. Notas de clase en Ciencias de la Computación. Vol. 8877. Springer International Publishing. págs. 1-14. arXiv : 1307.2908 . doi :10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0.S2CID18365892  .​
4. 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.
5. Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tayiko, Ahmad S. (10 de febrero de 2017). "Mecanismos sin envidia y con un número mínimo de cortes". Trigésima Primera Conferencia AAAI sobre Inteligencia Artificial . 31 . doi : 10.1609/aaai.v31i1.10584 . S2CID  789550.
6. Thomson, W. (2006). "Niños llorando en fiestas de cumpleaños. ¿Por qué?". Economic Theory . 31 (3): 501–521. doi :10.1007/s00199-006-0109-3. S2CID  154089829.