Cálculo de Asignaciones Sin Envidia con Subsidios Limitados

La división justa ha emergido como un tema muy candente en la investigación de EconCS, y la ausencia de envidia está entre los conceptos de equidad más convincentes. Una asignación de elementos indivisibles a agentes es sin envidia si ningún agente prefiere el conjunto de otro agente al suyo propio en términos de valor. Dado que la ausencia de envidia rara vez es un objetivo factible, hay un enfoque reciente en las relajaciones de su definición. Un enfoque en esta dirección es complementar las asignaciones con pagos (o subsidios) a los agentes. Un objetivo factible es entonces lograr la ausencia de envidia en términos del valor total que un agente obtiene de la asignación y los subsidios. Consideramos el problema de optimización natural de calcular asignaciones que sean susceptibles de ser libres de envidia utilizando la menor cantidad de subsidios. Dado que el problema es NP-duro, nos centramos en el diseño de algoritmos de aproximación. Por el lado positivo, presentamos un algoritmo que, para un número constante de agentes, aproxima la cantidad mínima de subsidios dentro de cualquier precisión requerida, a expensas de un aumento controlado en el tiempo de ejecución. Por el lado negativo, mostramos que, para un número superconstante de agentes, el problema de minimizar los subsidios para la ausencia de envidia no solo es difícil de calcular exactamente (como muestra un argumento de folklore) sino también, más importante, difícil de aproximar.