Examples of VCG Mechanism and The Clarke Pivot Rule – Mini Post 3

Abstract: In this post we look at the Clarke Pivot Rule, and how it applies and then two examples of how this mechanism can be used.

As mentioned in the previous post we use a function which we call $h_i$ . Because this function depends only on the other valuations of the bidders, we can change it without changing the incentives of the other bidders, so lets look at some examples.

One idea would be to set $h_i(v_{-i}) = 0$ . Note that $v_{-i}$ is the valuation of all bidders except bidder $i$ . This is DSIC, but we have to pay all other players in the auction money just for participating, which is not good if we are running the auction. One way to determine this function is through the Clarke Pivot Rule. This defines $h_i(v_{-i}) = \max_{x \in X} \sum_{j \neq i} v_j(x)$ .

With this rule the total amount payed by a individual player is (social welfare of others if $i$ were absent) – (social welfare of others when $i$ is present). This can also be referred to as the externality of player $i$ and can be thought of as the social cost due to player $i$ participating.

This rule when combined with a DSIC mechanism also gives us two properties that are generally quite useful. The first, is that a player cannot lose utility by participating in the mechanism. This is called individual rationality. The second is that the mechanism does not need to pay anything to the bidders. This is called no positive transfers.

With these rule defined we can now look at two examples of this mechanism that we have not seen before. The first is the Reverse Auction. In this system we have one player who wants to procure an item from the bidders with the lowest cost. In this instance its clear that getting the item with the lowest cost is equivalent to maximining the social welfare. The natural payment is to have the player pay the lowest bidder the second lowest bid, and nothing to the others. This is the same as using the Clarke pivot rule as the second lowest bid is what would have happened without the lowest bidder.

Another use of this analysis is the Bilateral Trade. In this instance one person is selling an an item and values it some positive value $v_s$ . Another person, the buyer values it at some $v_b$ . In this case, we can either trade items or not trade items. We can easily see that we trade if $v_b > v_s$ and don’t trade if $v_s > v_b$ . With VCG payments, and deciding that no payment is made if we don’t trade we see that, in the case of a trade, the buyer pays $v_s$ , as that is what the seller would have in the other best case. The seller is then payed $v_b$ . Now, because $v_b > v_s$ this mechanism subsidizes the trade, which is something we may look at in a future post.