3

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) ?

Mengfan Ma
  • 263
  • 1
  • 6
  • Yes, VCG still works in exactly the same way that the payments correspond to the agent's externality. – Bayesian Dec 15 '20 at 09:08
  • @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 Dec 15 '20 at 09:22
  • or is there a more generalized version of VCG mechanism beyond the one in Roughgarden's book? – Mengfan Ma Dec 15 '20 at 09: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
  • 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 Dec 15 '20 at 12:13
  • 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 Dec 15 '20 at 14:39
  • 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. – Bayesian Dec 15 '20 at 14:43
  • 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 Dec 15 '20 at 18:05

1 Answers1

4

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 for an introduction. If you want a deeper treatment, I recommend Tilman Börger'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."

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 and Jarman &Meisner (JET 2017), who use clock auctions as in Milgrom & Segal (JPE 2020).

Bayesian
  • 5,290
  • 2
  • 17
  • 44