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.

Published by Freddy_Reiber

Undergrad student at UCI. Running a blog on how to use Computer Science to win in modern board games.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: