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, {A}. Suppose, also the same type space, {\{1, \ldots, m\}} for both. Let {f(\cdot)} be the density function over types. To avoid clutter, assume the uniform distribution, i.e., {f(\cdot) = \frac{1}{m}}. Nothing in the subsequent analysis relies on this.

When agent 1 reports type {s} and agent 2 reports type {t}, denote by {z_r(s,t) } the probability that outcome {r \in A} is selected. The {z}‘s must be non-negative and satisfy {\sum_{r \in A}z_r(s,t) = 1.}

Associated with each agent {i} is a vector {\{a_{ir}\}_{r \in A}} that determines, along with her type, the utility she enjoys from a given allocation. In particular, given the allocation rule {z}, the utility that agent {1} of type {t} enjoys when the other agent reports type {s} is {\sum_{r \in A}ta_{1r}z_r(t,s).} A similar expression holds agent 2.

Let {q_i(s,t) = \sum_{r \in A}a_{ir}z_r(s,t).} Interpret the {q}‘s as the `quantity’ of goods that each agent receives. Dominant strategy implies that {q_1(s,t)} should be monotone increasing in {s} for each fixed {t} and {q_2(s,t)} should be monotone increasing in {t} for each fixed {s}. The interim `quantities will be: {mQ_i(s) = \sum_t\sum_{r \in A}a_{ir}z_r(s,t).} Bayesian incentive compatibility (BIC) implies that the {Q_i}‘s should be monotone. To determine if given BIC interim `quantities’ {Q_i}‘s can be implemented via dominant strategies, we need to know if the following system is feasible

\displaystyle \sum_{r \in A}a_{1r}[z_r(i,j) - z_r(i-1,j)] \geq 0\,\, \forall \,\, i = 2, \ldots, m \ \ \ \ \ (1)

\displaystyle \sum_{r \in A}a_{2r}[z_r(i,j) - z_r(i,j-1)] \geq 0\,\, \forall \,\, j = 2, \ldots, m \ \ \ \ \ (2)

\displaystyle \sum_t\sum_{r \in A}a_{1r}z_r(s,t) = mQ_1(s) \ \ \ \ \ (3)

\displaystyle \sum_s\sum_{r \in A}a_{2r}z_r(s,t) = mQ_2(t) \ \ \ \ \ (4)

\displaystyle \sum_{r \in A}z_r(s,t) = 1\,\, \forall s,t \ \ \ \ \ (5)

\displaystyle z_r(i,j) \geq 0\,\, \forall i,j,r \ \ \ \ \ (6)

System (1-6) is feasible iff the optimal objective function value of the following program is zero:

\displaystyle \min \sum_{i,j}w_{ij} + \sum_{i,j}h_{ij}

subject to
\displaystyle \sum_{r \in A}a_{1r}[z_r(i,j) - z_r(i-1,j)] + w_{ij} - u_{ij} = 0\,\, \forall \,\, i = 2, \ldots, m\,\, (\mu_{ij}) \ \ \ \ \ (7)

\displaystyle \sum_{r \in A}a_{2r}[z_r(i,j) - z_r(i,j-1)] + h_{ij} - v_{ij} = 0\,\, \forall \,\, j = 2, \ldots, m\,\, (\nu_{ij}) \ \ \ \ \ (8)

\displaystyle \sum_j\sum_{r \in A}a_{1r}z_r(i,j) = mQ_1(i)\,\, (\alpha_i) \ \ \ \ \ (9)

\displaystyle \sum_i\sum_{r \in A}a_{2r}z_r(i,j) = mQ_2(j)\,\, (\beta_j) \ \ \ \ \ (10)

\displaystyle \sum_{r \in A}z_r(i,j) = 1\,\, \forall i,j\,\, (\lambda(i,j)) \ \ \ \ \ (11)

\displaystyle w_{ij},\,\, h_{ij}\,\,z_r(i,j) \geq 0\,\, \forall i,j,r \ \ \ \ \ (12)

Let {(z^*, w^*, h^*, u^*, v^*)} be an optimal solution to this program.
Suppose, for a contradiction there is a pair {(p,q)} such that {w^*_{pq} > 0}. I will argue that there must exist an {s} such that {u^*_{ps} > 0}. Suppose not, then for each {j \neq q}, either {w^*_{pj} > 0} or {w^*_{pj} = 0} and {u^*_{pj} = 0} (at optimality, it cannot be that {w^*_{pq}} and {u^*_{pq}} are both non-zero). In this case

\displaystyle m[Q_1(p)-Q_1(p-1)] = \sum_j\sum_{r \in A}a_{1r}z^*_r(p,j) - \sum_j\sum_{r \in A}a_{1r}z^*_r(p-1,j)

= \sum_{j: w^*_{pj} > 0}a_{1r}[z^*_r(p,j) - z^*_r(p-1,j)] = -\sum_j w^*_{pj}. This last term is negative, a contradiction. Therefore, there is a s such that w^*_{ps} = 0 but u^*_{ps} > 0.

Let {Z_1(i,j) = \sum_{r \in A}a_{1r}z^*_r(i,j)}, {Z_2(i,j) = \sum_{r \in A}a_{2r}z^*_r(i,j)} and denote by {Z(i,j)} the point {(Z_1(i,j), Z_2(i,j))}. Observe that {Z(i,j)} is in the convex hull, {K} of {\{(a_{1r}, a_{2r}\}_{r \in A}} for all {i,j}. Thus choosing {\{z_r(i,j)\}_{r \in A}}‘s amounts to choosing a point {Z(i,j) \in K}. Equivalently, choosing a point {Z(i,j) \in K} gives rise to a set of {\{z_r(i,j)\}_{r \in A}}‘s. For convenience assume that {Z(i,j)} is in the strict interior of {K} for all {(i,j)} and that K is full dimensional. This avoids having to deal with secondary arguments that obscure the main idea.

Recall, {w^*_{pq} > 0} implies {Z_1(p,q) 0} implies that {Z_1(p,s) > Z_1(p,s)}. Take all points {\{Z(i,q)\}_{i \geq p}} and shift them horizontally to the right by {\delta}. Call these new points {\{Z'(i,q)\}_{i \geq p}}. Observe that {Z'(i,q) \in K} for all {i \geq p}. Next, take all points {\{Z(i,s)\}_{i \geq p}} and shift them horizontally to the left by {\delta} to form new points {\{Z'(i,s)\}_{i \geq p}}. These points are also in {K}. Leave all other points {\{Z(p,j)\}_{j \neq, q,s}} unchanged.

Because the vertical coordinates of all points were left unchanged, (8) and (10) are satisfied by this choice of points. Because {\{Z(i,q)\}_{i \geq p}} and {\{Z(i,s)\}_{i \geq p}} were shifted in opposite directions along the horizontal, (9) is still true. Finally, because all points in {\{Z(i,q)\}_{i \geq p}} and {\{Z(i,s)\}_{i \geq p}} were shifted by the same amount, (7) continues to hold.

The shift leftwards of {Z(p,s)} reduces {u_{ps}} while the rightward shift of {Z(p,q)} reduces {w_{pq}}. Thus, we get a new solution with higher objective function value, a contradiction.

If {Z(p,q)} and {Z(p,s)} are not the interior of {K} but on the boundary, then horizontal shifts alone may place them outside of {K}. In the case of {Z(p,q)} this can only happen if {Z_2(p,q) > Z_2(p-1,q)}. In this case, shift {Z(p,q)} across and to the right by {\delta} as well and then downwards by the same amount. This would have to be matched by a corresponding upward shift by some point {Z_2(h,q)}. Similarly with {Z(p,s)}.

Thanks to Alexey Kushnir and Ahmad Peivandi for comments.