3
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ Yes, VCG still works in exactly the same way that the payments correspond to the agent's externality. $\endgroup$
    – Bayesian
    Commented Dec 15, 2020 at 9:08
  • $\begingroup$ @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. $\endgroup$
    – Mengfan Ma
    Commented Dec 15, 2020 at 9:22
  • $\begingroup$ or is there a more generalized version of VCG mechanism beyond the one in Roughgarden's book? $\endgroup$
    – Mengfan Ma
    Commented Dec 15, 2020 at 9:30
  • $\begingroup$ 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. $\endgroup$
    – Bayesian
    Commented Dec 15, 2020 at 10:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bayesian
    Commented Dec 15, 2020 at 14:43

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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