<p>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., <a href="https://people.cs.pitt.edu/~kirk/CS1699Fall2014/VCG-LOS.pdf" rel="nofollow noreferrer">this write-up by Kirk Pruhs.</a></p>

CC BY-SA 3.0
2017-02-13T21:21:32.087Z
2017-02-13T21:21:32.087Z
Bayesian
<p>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$.</p>

<p>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)</p>

<auctions><mechanism-design><algorithms>
Does the VCG algorithm work for any bundle valuation function?
RBS
# Does the VCG algorithm work for any bundle valuation function?

(Asked by: username_0 on 2016-12-07)

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)

**Tags:** auctions, mechanism-design, algorithms

---

## 1 answers

### Answer by username_1 on 2017-02-13. Score: 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.](https://people.cs.pitt.edu/~kirk/CS1699Fall2014/VCG-LOS.pdf)


---

