Procedimiento de socavado
El procedimiento de socavado es un procedimiento para la asignación justa de artículos entre dos personas. Es probable que encuentre una asignación de artículo completa y 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 socavado puede verse como una generalización del protocolo divide y elige de un recurso divisible a un recurso con indivisibilidades. El protocolo divide y elige requiere que una persona corte el recurso en dos partes iguales. Pero, si el recurso contiene indivisibilidades, puede ser imposible hacer un corte exactamente igual. En consecuencia, el procedimiento de socavado 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) tales que:
Para probar la corrección del procedimiento, basta 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. Entonces, 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 obtengamos una partición (X',Y') que es un corte casi igual para Alice. Alice todavía prefiere débilmente X' a Y'. Por el supuesto de monotonicidad, George aún prefiere 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 pueden tener que evaluar todos los paquetes posibles, por lo que el tiempo de ejecución puede ser exponencial en la cantidad de elementos.
Esto no es sorprendente, ya que el procedimiento de socavación se puede utilizar para resolver el problema de partición : suponga que ambos agentes tienen valoraciones idénticas y aditivas y ejecute el procedimiento de socavación; si encuentra una asignación libre de envidia, entonces esta asignación representa una partición igual. Dado que el problema de la partición es NP-completo, probablemente no pueda resolverse mediante un algoritmo de tiempo polinomial.
El procedimiento de socavado 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. Luego, la definición de un corte casi igualitario (para el agente ) debe cambiarse de la siguiente manera:
