This week we're going to tell you about one of the great success stories of mechanism design, the Vickrey-Clarke-Groves mechanism. And in this video, I'm going to give you a high level taste of what this mechanism does and why it's important. So what is the Vickrey-Clarke-Groves mechanism for? Essentially, it solves a problem that we encounter in mechanism design pretty often where I, as the designer, am interested in implementing an efficient outcome. What that means is I've got a set of self-interested agents, each of whom has private information about how much they value each of the different things that could happen in the world. And what I'm desiring to do is always to pick the thing that maximizes the sum of the ways that the agents actually feel about these different things, which, of course, is something that I, as the designer, don't know. So what I need is for the agents to tell me how much they value different things, and I want then to pick the thing that maximizes the sum of their values. This would all be fine except that, of course, the agents could lie to me about how much they value different things. So what I want to do in a transferable utility setting here is to impose a set of payments that make it the right thing for the agents to tell me the truth so that I can then solve the pretty simple problem of maximizing the sum of how they feel about the different things. The trick is to set up these payments in the right way so that the agents really will want to tell me the truth. The great success of the VCG mechanism is that telling the truth for the agent is a dominant strategy. So it's a really strong kind of implementation. The agents really will want to tell me the truth, and they don't even have to think about what the other agents will do. It's simply the right thing for every agent To tell me the truth about their own valuation. And then if I run the VCG mechanism, the payments will be such that the agents will feel like they've done the right thing by just telling me the truth. I'm going to show you a number of different examples that gives you a sense of what that means in practice and why it's exciting. Let's start with the simplest example where I'm going to allocate a single thing among a set of agents. So imagine a government that wants to privatize a public utility like a power plant. Now when a government wants to privatize something, it's not usually because it just wants to collect a bunch of money. But instead it's that the government thinks that this public utility could be more efficiently operated by somebody in the private sector than by the government. If this is the case, the government typically wants to figure out which among a side of potential buyers values the utility the most because that's the buyer that would then most efficiently operate the utility afterwards. So you could think the government could go to each of these potential buyers and ask them, how much do you value the power plant? And it could then just give the power plant to the utility that values it the most. The problem of course is that if it just did this, the buyers would lie. They would all claim very, very high values in the hopes of being the highest. And the government would probably not end up giving the power plant to the right company. So instead, the government has to sell the power plant even if it doesn't care about collecting the money. The question then is what rules should it use for imposing payments on the different potential buyers? And if we were to use the VCG mechanism here, this would give us a way of imposing payments on the different buyers so that we would ensure that each of the buyers would simply tell the government the truth about how much the power plant is worth to them. This is a simple example because here the outcome space is just giving the power plant to each of the potential buyers. And we're just allocating a single good, essentially the power plant here. The VCG also works in other settings that look pretty different from this. Let me give you an example of that. Let's imagine here the simplest possible outcome space. There are just two things that could happen. I have a set of businesses on two sides of a river. And the two outcomes are that a bridge could be built or could not be built. And what I want to do here is to build a bridge If the sum of values that the agents have for the bridge exceeds the cost of its construction, and not build the bridge otherwise. And again, what I want to do here is collect information from all the businesses that has them tell me how much it's worth to them to have the bridge be constructed. And it may well be that they have a negative value for the bridge being constructed because maybe they're better off in the world where there's no bridge. So I want to look at all this aggregate information. And I want then to figure out payments where I might compensate some businesses that are hurt by the construction of the bridge. I may charge some businesses that are benefited by the cost of the bridge, and eventually collect enough money that I can actually pay the construction workers, who of course have a negative value to the bridge being constructed because they have to do work, and overall decide whether the bridge in fact should be built or not. So again, the VCG mechanism would just do the right thing here. It would come up with payments that work out in the right way, as we'll see when we do this example a bit more formally later. Here's a third example, which is again pretty different from the first two. It's a little bit more like the bridge example. I need to make kind of a social choice here rather than allocating one thing among different people. Here the problem is scheduling meetings. So imagine that you're in a problem which I really face in my life all the time where it's necessary to schedule meetings between people who have different values for different times in their calendar and who may not tell you the truth about whether they are available or not. So, for example, they may lie to you and tell you I'm busy first thing in the morning just because they don't actually want to come in first thing in the morning. And in principle, it's fine that they have a bad value for that time, but it may be that that turns out to be the only time that everybody else is available. So it may be better to reward that person strongly for coming in first thing in the morning rather than not being able to have the meeting at all. So here what I want to do, again now I have to do this in a setting where payments are possible, so I have to imagine either that I really am going to pay people bonuses for coming to their meetings. Or I have to imagine that I have some kind of artificial currency which is still scarce, which is used for meeting scheduling, and people care about. So maybe in my case where somebody has to come in at a really undesirable time for them, they accumulate a lot of credit that they can use for something else that they value. But again, the way the VCG mechanism would work here is it would give everyone a dominant strategy for telling me all of the values they have for the different times at which meetings might happen. And it will then come up with payments that make everybody happy about having told me this and allow me to implement the social welfare maximizing meeting schedule. So let's look at one more example which indeed we'll work through numerically in later videos in a stylized form. This is the problem of buying a path in a network. And the network I want to think about here is a railroad network from the American Midwest in 1881. So each of these red lines here corresponds to a rail link that existed in this area in 1881. And I don't know if this is actually true, but I want to claim that each of these red lines corresponds to a privately owned railroad that is owned by a different railroad operator. Certainly in the case that in the early days of railroads in the United States, there were lots of different privately owned railroads. So I want to imagine that each of these railroad links has its own private cost for what it would cost to ship something along the link. Over here is the Hocking Valley Coal Field, which was an area of coal production. And of course over here is the city of Chicago. And the problem that I'm interested in is the problem of shipping something, shipping a bunch of coal from the Hocking Valley Coal Field to Chicago. So I, as the coal company, need to buy a sequence of links in the network that would get me all the way from the coal field to Chicago. Now If I was to use the VCG mechanism, I could solve this problem by asking each of the coal companies what their utility is for being selected to ship coal. And for each of them, this would be a negative number because it actually costs them something to do the shipping. So each of them would tell me a negative number. They would have a dominant strategy to tell me the truth about what their real cost is. I can then look at these numbers and the social welfare maximizing outcome here is the shortest path in the network. It's the set of paths that together get me from the Hocking Valley Coal Field to Chicago and imposes the least negative cost on all of the agents. Now, why would they be willing to be chosen if they're in a situation that they negatively value? Well, to make this a dominant strategy, VCG in this case is going to end up paying all of the agents rather than imposing payments on them as it did, for example, in the privatization example. So in this example, it's going to figure out a way to pay the agents that makes them willing to have told me the truth and ends up buying the shortest path. So overall, what have we seen here? The VCG mechanism is an amazing way of solving all of these apparently very different problems and indeed lots more. And again to remind you, the property that it has is that it chooses the efficient or social welfare maximizing outcome in a transferable utility setting in a way that gives agents dominant strategies to tell the truth. We'll spend the rest of this week telling you in more formal detail how the VCG mechanism is defined, how it works, and what its strengths and weaknesses are.
