Does the VCG algorithm work for any bundle valuation function?

Question

Assume we have $n$ buyers of $|M|=m$ items in a combinatorial auction. So as we know, we can use the Vickrey-Clarke-Groves (VCG) algorithm to allocate bundles of items to buyers as best as possible. However, each player $i$ has a value $v_{ij}$ for every single item $j$ and a value $v_i(S)$ for each bundle of items $S \subset M$.

My question is as follows: can we always use the VCG algorithm to find the best solution to this problem, even when the $v_i(S)$ function is non-additive, for example if $v_i(S) = \max\limits_{k \in S} v_{ik}$? (So in this case, player $i$ values a bundle of items as much as its most valued item, no matter how many items are in the bundle)

Answer 1

In theory, the answer is yes. In practice, the answer is no, because it is computationally intractable. My take-away from talking to computer scientists was that determining a winner and computing the transfers are NP-hard problems. See, e.g., this write-up by Kirk Pruhs.