In this post I describe an alternative proof of a nifty result that appears in a forthcoming paper by Goeree, Kushnir, Moldovanu and Xi. They show (under private values) given any Bayesian incentive compatible mechanism, M, there is a dominant strategy mechanism that gives each agent the same expected surplus as M provides.
For economy of exposition only, suppose 2 agents and a finite set of possible outcomes, . Suppose, also the same type space, for both. Let be the density function over types. To avoid clutter, assume the uniform distribution, i.e., . Nothing in the subsequent analysis relies on this.
When agent 1 reports type and agent 2 reports type , denote by the probability that outcome is selected. The ‘s must be non-negative and satisfy
Associated with each agent is a vector that determines, along with her type, the utility she enjoys from a given allocation. In particular, given the allocation rule , the utility that agent of type enjoys when the other agent reports type is A similar expression holds agent 2.
Let Interpret the ‘s as the `quantity’ of goods that each agent receives. Dominant strategy implies that should be monotone increasing in for each fixed and should be monotone increasing in for each fixed . The interim `quantities will be: Bayesian incentive compatibility (BIC) implies that the ‘s should be monotone. To determine if given BIC interim `quantities’ ‘s can be implemented via dominant strategies, we need to know if the following system is feasible
System (1-6) is feasible iff the optimal objective function value of the following program is zero:
Let be an optimal solution to this program.
Suppose, for a contradiction there is a pair such that . I will argue that there must exist an such that . Suppose not, then for each , either or and (at optimality, it cannot be that and are both non-zero). In this case
. This last term is negative, a contradiction. Therefore, there is a such that but .
Let , and denote by the point . Observe that is in the convex hull, of for all . Thus choosing ‘s amounts to choosing a point . Equivalently, choosing a point gives rise to a set of ‘s. For convenience assume that is in the strict interior of for all and that is full dimensional. This avoids having to deal with secondary arguments that obscure the main idea.
Recall, implies implies that . Take all points and shift them horizontally to the right by . Call these new points . Observe that for all . Next, take all points and shift them horizontally to the left by to form new points . These points are also in . Leave all other points unchanged.
Because the vertical coordinates of all points were left unchanged, (8) and (10) are satisfied by this choice of points. Because and were shifted in opposite directions along the horizontal, (9) is still true. Finally, because all points in and were shifted by the same amount, (7) continues to hold.
The shift leftwards of reduces while the rightward shift of reduces . Thus, we get a new solution with higher objective function value, a contradiction.
If and are not the interior of but on the boundary, then horizontal shifts alone may place them outside of . In the case of this can only happen if . In this case, shift across and to the right by as well and then downwards by the same amount. This would have to be matched by a corresponding upward shift by some point . Similarly with .
Thanks to Alexey Kushnir and Ahmad Peivandi for comments.