Procedimiento de socavación

El procedimiento de socavación es un procedimiento para la asignación justa de elementos entre dos personas. Se puede demostrar que encuentra una asignación de elementos completamente libre de envidia siempre que exista dicha asignación. Fue presentado por Brams y Kilgour y Klamler ^[1] y simplificado y ampliado por Aziz. ^[2]

El procedimiento de socavación requiere únicamente las siguientes suposiciones débiles por parte de las personas:

• Cada persona tiene una relación de preferencia débil en subconjuntos de elementos.
• Cada relación de preferencia es estrictamente monótona : para cada conjunto y elemento , la persona prefiere estrictamente .${\estilo de visualización X}$${\displaystyle y\notin X}$${\displaystyle X\cup y}$${\estilo de visualización X}$

No se supone que los agentes tengan preferencias receptivas .

El procedimiento de corte inferior puede considerarse como una generalización del protocolo de dividir y elegir de un recurso divisible a un recurso con indivisibilidades. El protocolo de dividir y elegir requiere que una persona corte el recurso en dos partes iguales. Pero, si el recurso contiene indivisibilidades, puede resultar imposible hacer un corte exactamente igual. En consecuencia, el procedimiento de corte inferior funciona con cortes casi iguales . Un corte casi igual de una persona es una partición del conjunto de elementos en dos subconjuntos disjuntos (X, Y) de manera que:

• La persona prefiere débilmente X a Y;
• Si un solo elemento se mueve de X a Y, entonces la persona prefiere estrictamente Y a X (es decir, para todo x en X, la persona prefiere ) .${\displaystyle Y\cup x}$${\displaystyle X\setminus x}$

Cada persona informa de todos sus cortes casi iguales. Hay dos casos:

• Caso 1 : los informes son diferentes, por ejemplo, hay una partición (X, Y) que es un corte casi igual para Alice pero no para George. Luego, esta partición se presenta a George. George puede aceptarla o rechazarla:
  • George acepta la partición si prefiere Y a X. Entonces Alice recibe X y George recibe Y y la asignación resultante está libre de envidia.
  • George rechaza la partición si prefiere X a Y. Por suposición, (X, Y) no es un corte casi igual para George. Por lo tanto, existe un elemento x en X tal que George prefiere . George informa ; decimos que George socava a X. Dado que (X, Y) es un corte casi igual para Alice, Alice prefiere . Entonces George recibe y Alice recibe y la asignación resultante está libre de envidia.${\displaystyle X\setminus x}$${\displaystyle Y\cup x}$${\displaystyle X\setminus x}$${\displaystyle Y\cup x}$${\displaystyle X\setminus x}$${\displaystyle X\setminus x}$${\displaystyle Y\cup x}$
• Caso 2 : los informes son idénticos, es decir, Alice y George tienen exactamente el mismo conjunto de cortes casi iguales. Luego, el procedimiento les pregunta si uno de sus cortes casi iguales es un corte exactamente igual. Por el supuesto de monotonía estricta, (X, Y) es un corte exactamente igual, si y solo si tanto (X, Y) como (Y, X) son cortes casi iguales. Por lo tanto, en el caso 2, Alice y George tienen el mismo conjunto de cortes exactamente iguales. Hay dos subcasos:
  • Caso fácil: existe un corte exactamente igual (X, Y). Entonces una persona (no importa quién) recibe X y la otra recibe Y y la división está libre de envidia.
  • Caso difícil: no existe un corte exactamente igual. Entonces el procedimiento regresa e informa que "no existe una asignación sin envidia".

Para demostrar la corrección del procedimiento, es suficiente probar que en el caso Difícil, no existe una asignación libre de envidia. De hecho, supongamos que existe una asignación libre de envidia (X, Y). Como estamos en el caso Difícil, (X, Y) no es un corte exactamente igual. Por lo tanto, una persona (por ejemplo, George) prefiere estrictamente Y a X, mientras que la otra persona (Alice) prefiere débilmente X a Y. Si (X, Y) no es un corte casi igual para Alice, entonces movemos algunos elementos de X a Y, hasta que obtenemos una partición (X', Y') que es un corte casi igual para Alice. Alice sigue prefiriendo débilmente X' a Y'. Por el supuesto de monotonía, George sigue prefiriendo estrictamente Y' a X'. Esto significa que (X', Y') no es un corte casi igual para George. Pero en el caso Difícil, ambos agentes tienen el mismo conjunto de cortes casi iguales, una contradicción.

En el peor de los casos, los agentes podrían tener que evaluar todos los paquetes posibles, por lo que el tiempo de ejecución podría ser exponencial en el número de elementos.

Esto no es sorprendente, ya que el procedimiento de reducción se puede utilizar para resolver el problema de la partición : suponga que ambos agentes tienen valoraciones idénticas y aditivas y ejecute el procedimiento de reducción; si encuentra una asignación sin envidia, entonces esta asignación representa una partición igual. Dado que el problema de la partición es NP-completo, probablemente no se pueda resolver mediante un algoritmo de tiempo polinomial.

El procedimiento de reducción también puede funcionar cuando los agentes tienen derechos desiguales. ^[2] Supongamos que cada agente tiene derecho a una fracción de los artículos, siendo el otro agente. En ese caso, la definición de una reducción casi igual (para el agente ) debería modificarse de la siguiente manera: ${\estilo de visualización i}$$Estilo de visualización c_{i}$${\estilo de visualización -i}$${\estilo de visualización i}$

• ${\displaystyle u_{i}(X)\geq {c_{i} \sobre c_{-i}}u_{i}(Y)}$, y
• Para todo x en X, la${\displaystyle u_{i}(X\setminus x)<{c_{i} \sobre c_{-i}}u_{i}(Y\cup x)}$

En la publicación original, ^[1] el procedimiento de socavación está precedido por la siguiente fase de generación :

• Mientras hay temas sobre la mesa:
  • Cada persona reporta su mejor artículo.
    • Si los informes son diferentes, entonces cada persona recibe su mejor artículo.
    • Si los informes son idénticos, entonces el mejor artículo se coloca en una pila en disputa .

El procedimiento de socavación descrito anteriormente se ejecuta entonces solo en el pilote en disputa.

Esta fase puede hacer que el procedimiento de división sea más eficiente: la pila en disputa puede ser más pequeña que el conjunto original de elementos, por lo que puede ser más fácil calcular y reportar los cortes casi iguales.

Sin embargo, la fase de generación tiene varias desventajas: ^[2]

1. Esto podría hacer que el procedimiento pase por alto una posible asignación sin envidia. Por ejemplo, supongamos que hay cuatro elementos y sus valoraciones son las de la tabla adyacente. La asignación que da {w, z} a Alice y {x, y} a George está libre de envidia. De hecho, se puede encontrar mediante el procedimiento de corte simple, ya que la partición ({w, z}, {x, y}) es un corte casi igual para Alice pero no para George, y George aceptaría esta partición. Pero con la fase de generación, inicialmente Alice obtiene w y George obtiene x y los otros elementos {y, z} se colocan en la pila en disputa, y no hay una asignación sin envidia de la pila en disputa, por lo que el procedimiento falla.
2. Requiere que las personas seleccionen su "mejor artículo" sin saber qué otros artículos van a recibir. Esto se basa en el supuesto de que los artículos son bienes independientes . Alternativamente, se basa en un supuesto de capacidad de respuesta : si, en un paquete, un artículo es reemplazado por un artículo mejor, entonces el paquete resultante es mejor (está estrechamente relacionado con las preferencias débilmente aditivas ).
3. No funciona cuando los agentes tienen reclamaciones desiguales.
4. Se basa en la asignación secuencial, que es susceptible a la manipulación estratégica.

• Procedimiento de demanda decreciente y procedimiento de gráfico de envidia : dos procedimientos adicionales basados ​​en la clasificación ordinal de los paquetes.

• Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional. Cambridge University Press. págs. 306–307. ISBN. 9781107060432.(versión gratuita en línea)