So far we've heard a lot of good things about VCG. And for good reason. But VCG also has some important limitations that this video will introduce you to. The first is that VCG requires that the agents tell the mechanism everything about their private information. This is fine if we really believe our model that the agents had utility only for the choice that the mechanism makes and the payments that are imposed. But in some settings, agents might interact together repeatedly, and telling the mechanism and publicizing something about their private information might affect their ability to compete in future interactions. So if that's true, the agents might prefer a mechanism in which only as much information is disclosed as is required to actually compute the social welfare, maximizing choice, and the VCG payments. This is often possible, and VCG requires revealing more than that. So in such cases, a VCG wouldn't be a good choice of mechanism. Here's something a little bit more subtle about VCG. It turns out to be susceptible to collusion. So let's look at the road building game. Here we have three agents. We're going to choose to build the road rather than not building the road, because we get utility of 300 for building the road, and 250 for not building it. If we look at the agents of VCG payments, let's look for example at Agent 1. He would be paid 100, because in the situation where he exists, Agent 2 has happiness of 100. And he's going to have to pay 250, because in the world where he doesn't exist, the road won't be built, and there'll be Agent 3 will have 250 units of utility. So, in other words, he's going to be paid 100 and have to pay 250, which means that his payment is going to be 150. Well, we know that he has a dominant strategy to tell the truth. But what if both Agents 1 and 2 could coordinate to change their declared valuations? What if for example they were each to increase their valuation by $50? Well, in this situation it actually turns out that both Agents 1 and 2 are better off. Their payments both go down by $50. How does that happen? Well, it turns out that Agent 2's change of declaration reduces the payment for Agent 1. And Agent 1's change of declaration reduces the payment for Agent 2. So if they can collude together, they can both reduce their payments, and this doesn't violate our claim that they have individual dominant strategies, but it is a problem for VCG. So we have to be sure that we don't use VCG in situations where it's easy for agents to collude. So, the next problem with VCG that I'd like to tell you about, is, again has to do with the payments. And we say that VCG is not frugal because the payments can really seem out of line. So let's think again about this graph routing example that we've seen before where we want to find the shortest path and pay agents for routing traffic along their edges. So recall in this example that the shortest path is this one with a cost of five. And recall also that the second shortest path is this one with a cost of six. 2 plus 3 plus 1. Now let's think, in particular, about the effect on agent AB, of changes to AC's cost. And what I'm going to end up showing, you is that VCG can end up paying arbitrarily more than AB is willing to accept, because AB's payment doesn't end up depending on his own declaration, but instead ends up depending on the cost of the next shortest path. So, and this is also a possible problem in cases where we're not paying the agents, but rather where the agents are paying us. So let's see how it works. So if for example the cost of this edge was to increase to 8, then here our cost would be 12. Our second shortest path cost would be 12. And so that would change the payment to AB and it would go up by six. So we increased this value here of somebody else's value by six and although we didn't change anything about what AB was willing to accept, we ended up changing our payment to AB, also by six. And indeed, if the cost was any x greater than 2 for this edge AC, then we would end up making a payment to AB which depends on x and doesn't depend on AB's own value. So this means that the gap between agents' true costs on the payments they could receive under VCG is unbounded. Now, we might think that we're just comparing to the wrong thing. We might think that we really can't do anything about the fact that VCG is going to not be able to charge the people based on their own values. But we might hope that VCG's payments are close to the cost of the second shortest destroying path. And it turns out that that's not even true. So here's a different, a little bit more complicated graph, that will illustrate that point. So here I have two disjoint paths. This one here goes through k agents, and each agent has a cost of c over k. So k times c over k means the total cost is c. Here I have another edge with only one agent, and his cost is c times 1 plus epsilon. So as long as epsilon is a positive number, the top path is going to be shorter than the bottom. So, VCG picks the top path, and it pays each of the k agents this amount here. So it charges each of the k agents the costs of the other agents on the shortest path, and then it pays them the cost of the guy who doesn't get picked. And if we just rearrange this, do a little bit of algebra and compute VCG's total payment by multiplying this amount by k, you can confirm that this amount here is VCG's total payment here. Well, that's kind of bad news because compare this value here to this value. And you'll see that VCG's payment Is theta of k times the cost of the second shortest path. So what that means is, it differs only by a constant away from being k times bigger. And now we're comparing actually to the second shortest path. So it really seems like VCG can end up paying much more than is sensible. Here's a fourth problem with VCG. Let's think about the notion of revenue monotonicity. This is a concept that seems very intuitive and natural to us for a mechanism. That the revenue that a mechanism would obtain would always weakly increase as I add agents to the mechanism. So you might kind of intuitively think that if I'm running a mechanism, it's always good to attract more participants to the mechanism because that can only increase my revenue. But it turns out this isn't true under VCG. So let's go back to the road building example with different numbers. Here we see a case where the utility for building the road is 100, the aggregate utility. The aggregate utility for not building the road is 90. And so we would choose to build the road, and we would charge Agent 2, 90. Because that's the amount of utility that Agent 1 would have if Agent 2 wasn't around. So far so good. And now let's consider adding another agent. And in particular, let's add an agent who has the same utility as Agent 2. Well, this changes everything. Because now, if I drop either Agent 2 or Agent 3, then, I'm still going to end up in a situation where I make the same choice. That means, neither of these agents is pivotal and because they're not pivotal, they don't pay anything. So, now nobody has to pay anything. So what this means is that adding another agent to my mechanism didn't change the choice that was made by VCG. But caused it to go from a positive amount of revenue to zero revenue. Another way of seeing why this could be a problem, is that Agent 2 could pretend to be two agents if he was able to submit a bid to the mechanism under a false name. And if he could do that, he could eliminate his own payment. So, with the problem with collusion which seem that if two agents can kind of behave like one agent in VCG, we've got a problem. Here we see that if one agent can behave like two agents, we've also got a problem. Here's one last concern about VCG. Sometimes we might want to use the mechanism as in the road building example, just as a way of making a social choice. Not at in order to actually collect money from the agents. And if this is the case, I might actually not really want to keep the money within the mechanism, maybe even the mechanism is just a computer program, it's not even something that's able to hold on to the money. So I might like to rebate the money back to the agent somehow. And the problem is, that if I just give all the agents a rebate, kind of no matter how I do it, it ends up changing the agents' incentives. So the agents start behaving differently in order to change the amount of the rebate they get, and it ends up breaking VCG. So for example, even if I say, I'm going to take all of the profits that VCG makes and give them to charity. Well, if the agents care about the charity, then they're going to care about what happened and that's going to change their utility. Or if I'm going to just take the money and go down the street and buy myself something. If that benefits the local enemy and that benefits the agents, then that's going to give them new incentives. So kind of formally what I have to do is burn the money. I have to take the money and just kind of destroy it in a way that has no consequences for the agents so that I don't give them the wrong incentives. Now, I should give you a caveat. It actually is possible to return some of the revenues to the agents, but it's very tricky to do this and in general what's not possible is to return all of the money. So there are ways of returning some fraction of the money, which is discussed in the literature, but in general it's not possible to just hand back all the money to the agents. So overall we've seen that despite the great properties that VCG has, there are also some caveats with it. Now I should mention that some of these caveats are problems with mechanisms other than VCG as well. So although I've pointed out some problems here, I don't want to leave you with the impression that these are problems only with VCG. But in general these are things that one should think about before making a choice of mechanism.
