3
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.