We've seen in the past that the VCG mechanism gives rise to dominant strategies and efficient allocations. We know that in general it doesn't give rise to individual rationality or budget balance. In this video we'll see that under some pretty mild additional assumptions it is possible for us to get both of these things. Now remember that individual rationality means that it makes sense for agents to participate in a mechanism. If they had a choice between participating and not participating they would be happy to participate. And recall that budget balance means that it doesn't cost money to run the mechanism. The mechanism either completely breaks even all the time, which we've already seen in the previous video is impossible for VCG, or at least is weakly budget balanced and turns a profit or breaks even. What we'll see in this video is that we can have both these two properties. So let me start with individual rationality. To get individual rationality, I'm going to need two different assumptions to be true of the environment. The first is called choice-set monotonicity. And this assumption says that for all agents, the set of outcomes that are achievable without that agent present. Is a weak subset of the set of outcomes that are possible when that agent is present. So, in other words, when I remove an agent from the mechanism, as, of course I have to do inside the payment evaluation for VCG, the mechanism set of choices that are available to it weekly goes down. So no, in particular no new choices become possible when somebody gets removed. The second assumption that I'll make is called no negative externalities. And I'll say that we have no negative externalities. If for all agents and all choices that can be made without that agent the agent's own valuation for each of these choices is non-negative. So, in other words, when you get dropped from the mechanism, it isn't possible for the mechanism to choose something that actually causes you pain. It might choose something that you like less well than what it chooses when you are present but it can't choose something for which you have negative utility. Let's look at two examples of realistic scenarios that satisfy both of these properties to give you a sense of why these properties are reasonable to assume. So the first is the road-building referendum problem. So consider this problem where we want to have a vote between agents to decide whether or not to build a public good like a road. So, the set of choices has nothing to do with the number of agents. Because the two choices are that either the road gets built or the road doesn't get built. Remember that the payments come from the payment function those are not the choices. And so the choice set is monotonic. It's monotonic in the weak sense that it just doesn't change within a but remember that we allowed for a weak subset. Secondly, let's assume that no agent negatively values the project. So, some agents might like it better for the road not to be built than for the road to be built. But let's say that none of the agents experiences negative utility in any situation. That still seems like a reason what model of this problem and that would give us no negative externalities. Okay, well we saw an example previously where choice-set monotonicity arose in a pretty trivial way because the set of choices just didn't change. Let's look at a richer example where the set of choices does change. So here let's think about kind of a simplified stock market in which we have two different kinds of agents. Some of them have a single unit of a stock that they want to sell. So they have one share of Apple stock and they want to sell it. We have another group of agents who want to buy one share of Apple stock and we have some number of agents on both sides of the market. Now the choices that the mechanism can make here Are different ways of paring together buyers and sellers. So every buyer can interact with only one seller. Every seller can interact with only one buyer. And nobody has to interact. So the pairing where nobody gets paired is valid. The pairing where just two people get paired is valid. And pairing where as many people as possible get paired is valid. So we have these various different ways of establishing trades that might happen in this market. Now, think about what happens if I add a new agent to the market, none of the pairings that worked when that agent wasn't present go away when I add a new person. They're all still possible to do because I could always just set that new person aside. But, I can also have that new person participate in trades that weren't possible without that person there and thus, you can see here the choice-set monotonicity is satisfied in a more interesting way because new options become available when I add an agent but no old options get rolled out. And it's natural in this kind of a setting to assume that agents have zero utility both for other people trading with each other and for other people not trading at all. And that being the case, the agent has zero utility for everything that can happen when they are not present and so there are no negative externalities. So now we are ready to consider the main result that we want to establish for this part of the video Which is that these two assumptions that we've just made of choice set monotonicity and no negative externalities, are sufficient to make the VCG mechanism exposed individual rational. Now let's remember what exposed individual rational means. As I said at the beginning of the video, individual rationality means that agents always have weakly positive utility for participating in the mechanism and ex-post means that this is true regardless of what valuations any of the agents have so this is true for every realization evaluations that the agent himself and also all of the other agents might have. So this is the strongest kind of individual rationality, so this is the most desirable property about individual rationality that we would hope to prove about VCG. And that makes this an encouraging result. So here's how we prove it. We begin by saying that all of the agents truthfully declare their valuations in equilibrium because we want to think about what happens in equilibrium. And then we can write this expression for age and Isaac expected utility for participating in the mechanism. Well, he gets his value for the allocation that actually happens. So this is the choice that VCG actually makes given that everybody reports their values truthfully. And he gets his value for that choice and then he pays the VCG payment function that we all know and love. So because I've assumed that everybody reports truthfully, I don't have any V-hats anywhere. So I can collect terms and, particularly, I can roll this into one of the sums. So I here get a sum over all of the agents, minus a sum over all of the agents except for I. Now it comes the part where I use choice-set monotonicity. So remember that this expression x(v) is the outcome that VCG chose which means that it maximizes social welfare and by choice set monotonicity, this other outcome x(v-i) was also one of the available choices when we pick this instead. And so what that means is there must have been at least as much social welfare arising under this choice as under this choice. If not, the optimization would have just picked this one. And so writing that as an equation, the sum of agents values for this choice is at least as big as the sum of equation values for this choice. I'm just moving that equation up here, and now I can also use no negative externalities. Let me just write the definition of no negative externalities so the value that I has for the choice that gets made when he's not present is greater than or equal to zero. And what that means is if I change this expression here to j not equal to i then I've just taken out a non-negative number here which means that this whole thing got smaller and that means the inequality still holds. And so I have this expression here and that's exactly what I wanted to prove because remember the agent's utility is this expression and so I want to ensure that this number is bigger than this number If it is then this whole thing is positive and I have individual rationality and that's exactly what we just find here. That this infact is positive or non-negative and so we do obtain individual rationality. Okay, so much for individual rationality, now I want to talk about budget balance. So here's the property that we need, turns out that one property is enough, for showing that VCG is weekly budget balanced. And we call this no single-agent effect. So an environment exhibits no single-agent effect if it's the case that for all agents I. All evaluations of the agents other than I that are possible and all choices x that maximize the social welfare. There exist another choice x prime which is feasible without i which means it's possible for us to pick it even if i has been dropped and for which all of the agents other than I get more social welfare than under the original allegation. So, in other words if I drop an agent I and then I pick some other choice instead we owed i. Everybody other than I is at least is happy with the new choice as with the old choice. So the welfare of agents other than I is weakly increased when we drop I. That might sound a little confusing, it's actually a really natural property. Here is an example. Think about a single sided auction where for example I have one good for sale. The choices in these case are all of the different agents I could give the good to. And if I drop an agent, one of two things is possible. Either that agent wasn't winning the auction before in which the social welfare maximizing outcome remains the same after the agent has been dropped and nothing changes. And so then I get equality in this expression. Or that is the agent who was winning before and then I pick a different winner once that agent has been dropped. I'll get less social welfare overall which is why I was picking a different agent in the first place. But when I consider only agents other than i they're all going to be happier when i has been dropped than when i was present. Because one of them gets to win after I is dropped. And in the case where i was present one of them wasn't winning. So if you can see it's kind of actually a pretty natural property, this no single-agent effect. So it turns out that this is all we need to prove that VCG is weekly budget balance and indeed that's a pretty direct proof. So as before let's assume truth telling an equilibrium. And now what we want to think about is the sum of transfers that agents make to the center. So the sum of all of the payments. And I want to show that this sum of all of these payments is greater than or equal to zero. That's going to mean weak budget balance. So once again, this is the VCG payment function and now I'm just summing the payment function across all of the agents. Because I'm interested in the aggregate payment. From the no single agent effect condition, I know that for all of the agents other than I. The value they have for the choice they gets made when I is dropped. The social welfare maximizing choice for them, they gets made when i is dropped, is at least is beg as the sum overall of their utilities for the choice that gets made when i is not dropped. That's just directly what no single-agent effect means. And you can see that these are exactly the terms that I have in the VCG payment function. And so the result follows directly. This blue term is bigger than the green term which means that this expression up here is just positive for every i or non-negative for every I. And so that gives us what we want which is that this whole sum is greater than or equal to 0. Well, I have one last bid of good news to give you here's a theorem from Christian and Perry. Which says something else about the revenue and VCG which is even more encouraging the one that what we just saw. It says consider any Baysian games settings in which VCG is exposed individually rational, and the claim is that in such a case VCG collects at least as much revenue as any other efficient and ex interim individually rational mechanism. Now here are a couple of things to kind of walk through about what is being claimed here. First of all, you might wonder about this little preamble, didn't we already talked about what happens when VCG is ex post to individual rational, well, not really because what we looked at before, was two conditions that are sufficient for VCG to be individual rational. We didn't claim that there are other things that might be true about the setting that would also result in VCG being individual rational so what this theorem says is don't worry about how you got there, think about any setting in which VCG is ex post individually rational, it will include what we talked about before but it'll include other settings too. And what is says is VCG collects at least as much revenue as any other efficient mechanism. The thing to notice here is even if that mechanism only uses Bayes-Nash equilibrium. We're not assuming that this other mechanism is dominant strategy efficient. So this other mechanism gets to be drawn from a much bigger pool, the dominant strategy mechanisms and the Bayes-Nash equilibrium mechanisms. And another sense in which it's drawn for a bigger pool is that we're only going to require of this competitor mechanism that it's ex interim individual rational whereas, we're requiring a VCG that it's ex post individual rational. So, this is ex interim individual rationality is a weaker thing to require which means, there's a broader set of mechanisms that would satisfy it which means that we're making a stronger statement when we compare VCG to this broad set. So, a way of understanding this result is that VCG is as budget balanced as any efficient mechanism can be. So I'm not saying here necessarily that the revenue is greater than or equal to zero. Sometimes it will be and sometimes not. But in cases where the revenue is still negative. Well, this results as is if VCG was ex post individual rational. There's no other mechanism which is efficient and which get's more revenue. So, VCG is always getting it's close to budget balance as efficient mechanism can. As long as VCG remains individually rational.
