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:
subject to
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.
Recent Comments