Class #7 Highlights

In this class, we studied dominant strategy implementation. These mechanisms are of interest since truth-telling is robust to irrationality. An outcome is an equilibrium in weakly dominant strategies if there exists a strategy s(theta) for a type theta such that, regardless of the strategies (types) of the other individuals, s(theta) is better than any alternative s'. The revelation principle of dominant strategies says that, given any indirect mechanism and any allocation that arises as a dominant strategy equilibrium, the same allocation is implementable via a direct mechanism under truth-telling. The proof is identical to that for BNE.

With that definition in hand, we studied ex post efficient allocations under the following class of preferences:

U_i = v_i(x_i, theta_i) - T_i

Under these preferences, each individual only cares about her portion of the vector x, her own type, and her own transfer. 

We said that an allocation x* is ex post efficient if, for every realization of theta,

Sum[v_i(x*_i, theta_i),{i,1,n}] >= Sum[v_i(x'_i, theta_i),{i,1,n}]

for all  x' ~= x*. 

An example of an ex post efficient allocation is to give the object to the highest valued bidder in a single under auction. 

A theorem by Groves showed that any ex post efficient allocation is DS implementable using the transfer rule

T_i = -Sum[v_j(x*_j, theta_j),{j~=i}] + h_i[theta-i]

Here, h[.] is an arbitrary function. The point is that such a transfer rule aligns private and social preferences of each individual. 

Of particular interest was the Vickrey-Clarke version of h. The idea of these mechanisms is that everyone should pay the amount of their externality on the others. Define x-i* to be an ex post efficient allocation when individual i is absent. Then the externality that i imposes on the others is simply

Sum[v_j(x-i*_j, theta_j) - v_j(x*_j, theta_j), {j~=i}]

In words, this is the difference between the surplus (excluding transfers) that the other individuals enjoy when  i doesn't exist less the surplus they enjoy when i does exist. 

An example makes this clear. Suppose there were 3 individuals numbered {1,2,3}. Suppose each individual values the object by their index, so individual 1 places value 1 for the object, individual 2 values it at 2, and so on. Then, when 3 is not present, the item goes to individual 2, who earns 2 utils. When 3 is present, ex post efficiency allocates the object to her and none of the others earn any utils. Therefore, 3's externality on the others is 2. Similarly, if 2 is absent, the item goes to 3 and the combination of 1 and 3 earn 3 utils. When 2 is present, the item still goes to 3 and individuals 1 and 3 still earn 3 utils in total. Thus, 2 exerts no externality from her presence. 

Notice that an individual only exerts an externality when she is pivotal, i.e. when the allocation is different when she is present than when she is absent. The Vickrey-Clarke (pivotal) mechanism has the property that only pivotal individuals are obliged to make payments. 

We showed that the same idea can be applied to public goods settings, such as the go/no-go decision to build a discrete public good like a bridge. Vickrey invented the auction version of the mechanism while Clarke invented the public goods version. Groves noticed the deeper connection. He showed:

Theorem: The pivot mechanism is the cheapest mechanism to DS implement the ex post efficient allocation. 

This is useful for two reasons. First, if money taken out of the system represents waste, then this tells us the least wasteful way to achieve ex post efficiency. Second, it tells us that we cannot have DS implementation of ex post efficient allocations and budget balance at the same time. We have to choose one or the other. 

Mechanisms where individuals pay their externality are commonly called Vickrey-Clarke-Groves or VCG mechanisms in honor of the three individuals making key discoveries about them. 

Rebates

Now, the alert student of information economics may wonder why we need to take the money out of the system. After all, there are many schemes whereby rebating money back in lump-sum fashion can get out of problems like these. But this will not work here. If we amend the mechanism and say that we will give back (say) equal shares of all the money collected to the individuals in a society, then it will wreck the mechanism since an individual who is pivotal will now pay less than her externality. This is the case since a portion of her payments, when she is pivotal, will be returned. Anticipating this, truth-telling will no longer be incentive compatible.

To see the problem, consider an auction setting with 2 bidders where the auctioneer will give back all the money collected equally to the two individuals. Suppose that individual 1 values the item at 1.9 while individual values it at 2. Suppose 2 tells the truth, then 1 will, optimally, want to report a value in excess of 2 since she will then receive the object, pay 2 for it, but get 1 back via the rebate. This yields a net surplus of 0.9 (1.9 - 2 + 1) versus a payoff of zero from truth-telling. Other rebating schemes run into similar problems.

Key things should be able to do after this class:

1.  Explain how the revelation principle works for weakly dominant strategies.
2. Know what an ex post efficient allocation is
3. Apply the VCG mechanism to implement an ex post efficient allocation. Compute the payments made by each player in the game.