<p>In general, VCG is also applicable to reverse auction settings. VCG is not even restricted to auction settings and can be used quite generally, see <a href="https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_mechanism" rel="nofollow noreferrer">wikipedia</a> for an introduction. If you want a deeper treatment, I recommend <a href="http://www-personal.umich.edu/%7Etborgers/" rel="nofollow noreferrer">Tilman Börger</a>'s book (it used to be fully online, maybe there are still copies flying around). In reality, there are often problems associated with VCG, see, e.g., Ausubel and Milgrom writing about <a href="https://web.stanford.edu/%7Emilgrom/publishedarticles/Lovely%20but%20Lonely%20Vickrey%20Auction-072404a.pdf" rel="nofollow noreferrer">&quot;The Lovely but Lonely Vickrey Auction.&quot;</a></p>
<p>The general idea of VCG is that each agent's transfer is their own externality.  In your setting, you cannot simply do that because there is a budget restriction on transfers. Papers with such a knapsack constraint in economics are <a href="https://www.sciencedirect.com/science/article/pii/S0048733313001157?casa_token=xfpVppMTKOQAAAAA:EcK5ZnXeXOoX2Ngo-RX3DC19qggrmzA29ep4krIsC5u_NFx05wrs0HkvApik8_SK7i5kEyyBUXg" rel="nofollow noreferrer">Ensthaler &amp;Giebe</a> and <a href="https://www.sciencedirect.com/science/article/pii/S0022053117300637?casa_token=wDbfZkeaSyAAAAAA:oKPXjZ9SmBkqUdh9TruaeNEKRT39kBG_0cpDW4Ex5_JfrtSKYJ4m3HjnW4M22dcTOc5tua18Px4" rel="nofollow noreferrer">Jarman &amp;Meisner (JET 2017)</a>, who use clock auctions as in <a href="https://www.journals.uchicago.edu/doi/full/10.1086/704074?casa_token=kUKgBNPPUzUAAAAA:GSObg5MwcGgJoo4vIuV6_-L5ZawkyI5UegEVCHL_DvxZHmT5zWuxIkSO0Me-yFsNh7zOYndei_8M" rel="nofollow noreferrer">Milgrom &amp; Segal (JPE 2020)</a>.</p>

CC BY-SA 4.0
2020-12-15T10:46:15.540Z
2020-12-15T10:46:15.540Z
Bayesian
<p>The VCG mechanism I've learnt is from Roughgarden's <em><a href="http://timroughgarden.org/f13/f13.pdf" rel="nofollow noreferrer">Twenty Lectures on Algorithmic Game Theory</a></em>. 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 <a href="https://economics.stackexchange.com/questions/40701/whats-the-definition-of-social-welfare-in-a-procurement-auction/40707#40707">thread</a>, the social welfare in a reverse auction is defined as:</p>
<p><span class="math-container">$$\sum_{i=1}^n x_i (v_0 - c_i)$$</span></p>
<p>where we have one buyer who values the good to be procured at <span class="math-container">$v_0$</span> and <span class="math-container">$n$</span> sellers who can produce the good at private cost <span class="math-container">$c_i$</span>, and <span class="math-container">$x_i$</span> indicates the outcome(allocation).</p>
<p>I was wondering, in reverse auction, whether or not the VCG mechanism is implemented exactly the same way as in Roughgarden's <em>Twenty Lectures on Algorithmic Game Theory</em> (section 7.2) ?</p>

CC BY-SA 4.0
2020-12-15T09:08:29.493Z
Yes, VCG still works in exactly the same way that the payments correspond to the agent's externality.
Bayesian
CC BY-SA 4.0
2020-12-15T09:22:18.737Z
@Bayesian I'm reading a paper by Singer on Budget Feasible Mechanisms https://people.seas.harvard.edu/~yaron/papers/BudgetFeasibleMechanisms.pdf, 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
CC BY-SA 4.0
2020-12-15T09:30:30.313Z
or is there a more generalized version of VCG mechanism beyond the one in Roughgarden's book?
Mengfan Ma
CC BY-SA 4.0
2020-12-15T10:48:52.697Z
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
CC BY-SA 4.0
2020-12-15T12:13:35.630Z
In the part where the author explains why VCG is inapplicable, I understood that VCG would choose the n-1 small-cost agents to maximize the social welfare, the payment, if we apply Myerson's lemma,  is obviously B. But why it's B in the way of VCG?  Denote by e the small cost, v the valuation of the buyer, the externality of agent i is 0: (n-2)(v-e) - (n-2)(v-e), where the first term is others' maximum welfare among all the possible outcome, the second is others' welfare in chosen outcome. These two outcomes are identical, to the best of my knowledge. Where did I go wrong in above computing?
Mengfan Ma
CC BY-SA 4.0
2020-12-15T14:39:28.927Z
I don't understand this example. If small costs e are common knowledge, there is no need to pay information rent. Then, you can put all small cost items in the knapsack and pay e to all of them.
Bayesian
CC BY-SA 4.0
2020-12-15T14:43:40.433Z
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
CC BY-SA 4.0
2020-12-15T18:05:17.957Z
The cost of each agent is private information. It makes sense to get a payment of B for each agent using Myerson's characterization instead of VCG formula(s). But, if it is the case, we may not conclude that VCG mechanism is inapplicable in this example, since we're not using the VCG mechanism here. Actually we're using a mechanism based on  Myerson's characterization.
Mengfan Ma
<auctions><mechanism-design>
Is VCG mechanism applicable in reverse auction? If so, how?
Mengfan Ma
# Is VCG mechanism applicable in reverse auction? If so, how?

(Asked by: username_0 on 2020-12-15)

The VCG mechanism I've learnt is from Roughgarden's *[Twenty Lectures on Algorithmic Game Theory](http://timroughgarden.org/f13/f13.pdf)*. 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](https://economics.stackexchange.com/questions/40701/whats-the-definition-of-social-welfare-in-a-procurement-auction/40707#40707), 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) ?

**Tags:** auctions, mechanism-design
> **Comments:**
> **username_1**: Yes, VCG still works in exactly the same way that the payments correspond to the agent's externality.  
> **username_0**: @Bayesian I'm reading a paper by Singer on Budget Feasible Mechanisms https://people.seas.harvard.edu/~yaron/papers/BudgetFeasibleMechanisms.pdf, 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.  
> **username_0**: or is there a more generalized version of VCG mechanism beyond the one in Roughgarden's book?  
> **username_1**: 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.  
> **username_0**: In the part where the author explains why VCG is inapplicable, I understood that VCG would choose the n-1 small-cost agents to maximize the social welfare, the payment, if we apply Myerson's lemma,  is obviously B. But why it's B in the way of VCG?  Denote by e the small cost, v the valuation of the buyer, the externality of agent i is 0: (n-2)(v-e) - (n-2)(v-e), where the first term is others' maximum welfare among all the possible outcome, the second is others' welfare in chosen outcome. These two outcomes are identical, to the best of my knowledge. Where did I go wrong in above computing?  
> **username_1**: I don't understand this example. If small costs e are common knowledge, there is no need to pay information rent. Then, you can put all small cost items in the knapsack and pay e to all of them.  
> **username_1**: 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.  
> **username_0**: The cost of each agent is private information. It makes sense to get a payment of B for each agent using Myerson's characterization instead of VCG formula(s). But, if it is the case, we may not conclude that VCG mechanism is inapplicable in this example, since we're not using the VCG mechanism here. Actually we're using a mechanism based on  Myerson's characterization.  

---

## 1 answers

### Answer by username_1 on 2020-12-15. Score: 4 | Accepted answer

In general, VCG is also applicable to reverse auction settings. VCG is not even restricted to auction settings and can be used quite generally, see [wikipedia](https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_mechanism) for an introduction. If you want a deeper treatment, I recommend [Tilman Börger](http://www-personal.umich.edu/%7Etborgers/)'s book (it used to be fully online, maybe there are still copies flying around). In reality, there are often problems associated with VCG, see, e.g., Ausubel and Milgrom writing about ["The Lovely but Lonely Vickrey Auction."](https://web.stanford.edu/%7Emilgrom/publishedarticles/Lovely%20but%20Lonely%20Vickrey%20Auction-072404a.pdf)

The general idea of VCG is that each agent's transfer is their own externality. In your setting, you cannot simply do that because there is a budget restriction on transfers. Papers with such a knapsack constraint in economics are [Ensthaler &Giebe](https://www.sciencedirect.com/science/article/pii/S0048733313001157?casa_token=xfpVppMTKOQAAAAA:EcK5ZnXeXOoX2Ngo-RX3DC19qggrmzA29ep4krIsC5u_NFx05wrs0HkvApik8_SK7i5kEyyBUXg) and [Jarman &Meisner (JET 2017)](https://www.sciencedirect.com/science/article/pii/S0022053117300637?casa_token=wDbfZkeaSyAAAAAA:oKPXjZ9SmBkqUdh9TruaeNEKRT39kBG_0cpDW4Ex5_JfrtSKYJ4m3HjnW4M22dcTOc5tua18Px4), who use clock auctions as in [Milgrom & Segal (JPE 2020)](https://www.journals.uchicago.edu/doi/full/10.1086/704074?casa_token=kUKgBNPPUzUAAAAA:GSObg5MwcGgJoo4vIuV6_-L5ZawkyI5UegEVCHL_DvxZHmT5zWuxIkSO0Me-yFsNh7zOYndei_8M).


---

