Corte de pastel eficiente

El reparto eficiente de un pastel es un problema de economía e informática . Implica un recurso heterogéneo , como un pastel con diferentes coberturas o un terreno con diferentes superficies, que se supone divisible : es posible cortar trozos arbitrariamente pequeños sin que disminuya su valor. El recurso debe dividirse entre varios socios que tienen diferentes preferencias por distintas partes del pastel; por ejemplo, algunos prefieren la cobertura de chocolate, otros las cerezas, otros simplemente quieren el trozo más grande posible, etc. La asignación debe ser económicamente eficiente . Se han estudiado varias nociones de eficiencia:

• La noción más común es la eficiencia de Pareto . Significa que ninguna otra asignación es mejor para al menos un participante y al menos igual de buena para todos.
• Un concepto menos estricto es el de no desperdicio . Una asignación no es derrochadora si ningún agente recibe un trozo de pastel que no le reporte ningún beneficio y que tenga un valor superior a cero para otro agente.

Por lo general, la eficiencia se estudia en relación con la equidad , y el objetivo es encontrar una distribución que satisfaga ambos criterios: eficiencia y equidad.

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

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

${\displaystyle C}$tiene que dividirse en${\displaystyle n}$subconjuntos disjuntos, de modo que cada persona reciba un subconjunto disjunto. La pieza asignada a la persona${\displaystyle i}$se llama${\displaystyle X_{i}}$, de modo que${\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:

Una asignación${\displaystyle X}$Se denomina derrochador si se asigna a algún agente una pieza que vale 0 para ese agente pero vale más de 0 para otro agente. En símbolos:

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

De lo contrario, se denomina asignación no derrochadora (AN). En el ejemplo del pastel, una asignación que le da todo el pastel a Alicia es AN, pero una asignación que le da todo el pastel a Jorge es derrochadora, ya que la parte de limón se "desperdicia". Existen muchas otras asignaciones AN; por ejemplo, darle el chocolate a Jorge y el resto del pastel a Alicia también es AN.

Una asignación${\displaystyle Y}$Pareto domina una asignación${\displaystyle X}$, si al menos una persona siente que${\displaystyle Y}$es mejor que${\displaystyle X}$y nadie siente eso${\displaystyle Y}$es peor que${\displaystyle X}$. En símbolos:

${\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${\displaystyle X}$Se denomina óptima de Pareto (OP) si no está dominada por ninguna otra división, es decir, no puede mejorarse sin objeción. En el ejemplo del pastel, darle todo el pastel a Alice es OP, pero dárselo todo a Bob está dominado por la asignación en la que la parte de limón se le da a Alice. En general (cuando no hay requisitos de conectividad en las piezas), toda asignación derrochadora está dominada por Pareto, por lo tanto, toda asignación OP es NW. Sin embargo, lo contrario no es cierto. Por ejemplo, la asignación que le da el chocolate a George y el resto del pastel a Alice es NW, pero no es OP; está dominada por la asignación que le da a George la vainilla y la mitad del chocolate. Esto se debe a que, en la asignación original, las utilidades de (Alice, George) son (3, 6), mientras que en la asignación alternativa las utilidades son (5.5, 7).

Siempre existen asignaciones eficientes. Por ejemplo, cualquier reparto de un pastel que sea utilitaristamente ó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 pastel NW utilizando 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 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, el PO tampoco es alcanzable por un protocolo finito. ^{[ 2 ] : 560, Thm.5}

El problema se simplifica bajo el supuesto de positividad estricta (cada agente valora cada punto del pastel en un valor estrictamente mayor que 0): cada asignación es trivialmente NW, y cada asignación que le da todo el pastel a un solo agente es trivialmente PO (ya que cualquier otra asignación le da a este agente una utilidad estrictamente menor).

El problema también resulta sencillo 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 utilitaria óptima (dando cada parte al agente que más la valora), y dicha asignación también es PO y NW.

A menudo, se requiere encontrar una asignación que no solo sea eficiente sino también justa según diversas nociones de equidad. La existencia sigue vigente:

• Siempre existe una asignación proporcional que cumple con el principio de Pareto . 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 además cumple con el principio de Pareto (dado que la proporcionalidad se conserva mediante mejoras de Pareto).
• Además, siempre existe una asignación 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 con las mejoras de Pareto. Sin embargo, se demuestra explícitamente en el teorema de Weller .

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

• En el modelo de consulta, ningún algoritmo finito que asigne a cada agente una fracción positiva del pastel 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 intervalos, puede existir 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 PO y libre de envidia (por lo tanto proporcional) en tiempo polinomial para cualquier número de agentes.

A menudo, además de la eficiencia y la equidad, existen restricciones geométricas en las piezas. Por ejemplo, si el pastel es un intervalo, entonces cada agente puede requerir una pieza que sea un intervalo contiguo. Con este requisito adicional:

• Siempre existe una asignación de orden de preferencia que además es proporcional. Esto se debe a que el conjunto de todas las asignaciones contiguas proporcionales sigue siendo compacto, y la proporcionalidad se conserva gracias a las 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:

• Con valoraciones generales, cuando las densidades de valor son estrictamente positivas, dividir y elegir es PO y proporcional para dos agentes. Supongamos sin logaritmo natural que Alice corta, George elige la pieza de más a la izquierda y Alice obtiene la pieza de 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 (por el supuesto de positividad estricta) cualquier movimiento de la ubicación del 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 este tipo, al menos uno de ellos debe obtener menos de 1/2 del valor total, mientras que en la asignación original ambos obtienen al menos 1/2.
• Con valoraciones constantes por partes, el algoritmo de equilibrio de mercado no necesariamente produce piezas conectadas, por lo que no funciona. Sin embargo, se puede utilizar un algoritmo similar a ^{[ 5 ] : 317, Thm.5} para encontrar una asignación proporcional que maximice la suma de utilidades para cualquier número de agentes, resolviendo${\displaystyle O(m^{n})}$programas lineales (donde m es el número de piezas).

Actualmente se desconoce si, para 3 o más agentes con valoraciones estrictamente positivas, se puede encontrar una asignación 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).

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