¿Funciona el algoritmo VCG para cualquier función de valoración de paquetes?

Question

Supongamos que tenemos $n$ compradores de $|M|=m$ artículos en una subasta combinatoria. Como sabemos, podemos utilizar el algoritmo de Vickrey-Clarke-Groves (VCG) para asignar paquetes de artículos a los compradores de la mejor manera posible. Sin embargo, cada jugador $i$ tiene un valor $v_{ij}$ para cada elemento $j$ y un valor $v_i(S)$ para cada paquete de artículos $S \subset M$ .

Mi pregunta es la siguiente: ¿podemos utilizar siempre el algoritmo VCG para encontrar la mejor solución a este problema, incluso cuando el $v_i(S)$ es no aditiva, por ejemplo si $v_i(S) = \max\limits_{k \in S} v_{ik}$ ? (Así que en este caso, el jugador $i$ valora un paquete de artículos tanto como su artículo más valorado, sin importar cuántos artículos haya en el paquete)

Answer 1

En teoría, la respuesta es sí. En la práctica, la respuesta es no, porque es computacionalmente intratable. Mi conclusión al hablar con los informáticos es que la determinación de un ganador y el cálculo de las transferencias son problemas difíciles de resolver. Véase, por ejemplo este escrito de Kirk Pruhs.