# Is VCG mechanism applicable in reverse auction? If so, how?

The VCG mechanism I've learnt is from Roughgarden's Twenty Lectures on Algorithmic Game Theory. Given an auction, we first identify the allocation that maximize the social welfare and then compute the payment for each agent according to the formulas given. In the case of reverse auction, according to this thread, the social welfare in a reverse auction is defined as:

$$\sum_{i=1}^n x_i (v_0 - c_i)$$

where we have one buyer who values the good to be procured at $$v_0$$ and $$n$$ sellers who can produce the good at private cost $$c_i$$, and $$x_i$$ indicates the outcome(allocation).

I was wondering, in reverse auction, whether or not the VCG mechanism is implemented exactly the same way as in Roughgarden's Twenty Lectures on Algorithmic Game Theory (section 7.2) ?

• Yes, VCG still works in exactly the same way that the payments correspond to the agent's externality. – Bayesian Dec 15 '20 at 9:08
• @Bayesian I'm reading a paper by Singer on Budget Feasible Mechanisms people.seas.harvard.edu/~yaron/papers/…, the model of this paper is too long to be included here. He explains why VCG doesn't work in reverse auction with budget on total payment in the second paragraph in page 2. I couldn't figure out why the payment for each selected agent is B according to a VCG-like analyse. Could you please shed some light upon this? Many many thanks in advance. – Mengfan Ma Dec 15 '20 at 9:22
• or is there a more generalized version of VCG mechanism beyond the one in Roughgarden's book? – Mengfan Ma Dec 15 '20 at 9:30
• The B in that paper is a budget. You cannot pay more than your budget and therefore VCG does not work in case VCG requires transfers that exceed this budget. – Bayesian Dec 15 '20 at 10:48
• Maybe Singer refers to his Myersonian characterization in Theorem 2.1.(ii) winners are paid threshold payments: the payment defined there would be B in your case (because $c_i=B$ is the lowest cost agent not in the allocation. – Bayesian Dec 15 '20 at 14:43