Exercise in Mechanism Design

Question

I found an exercise with solution in the field of Mechanism Design. The problem is I don't understand the solution.

Exercise. Use the characterization of incentive compatible direct-revelation mechansisms to show that there is no such mechanism for the problem of the department deciding whether to buy a 3-d printer of cost $C$ (even in the case of just two employees with values $v_1$ and $v_2$) with property that:

1. If $v_1 + v_2 > C$ then the printer is purchased and if $v_1 + v_2 < C$ then it’s not.

2. If the printer is purchased, then the employees are in total charged at least $C$ (i.e., no subsidy by the department), and player $i$ is never charged more than $v_i$.

Solution. Consider $v_1 = v_2 = 3C/4$. The price charged to player $1$ cannot be a function of $v_1$,

Q: why not?

and it can’t be larger than $C/4 + 1$ else the mechanism wouldn’t act correctly for $v_1 = C/4 + 1$

Q: but we set $v_1=v_2=3C/4$

(either it would fail to purchase or it would charge more than $v_1$). Similarly the price charged to player $2$ can’t be larger than $C/4 + 1$. So this violates the no-subsidy requirement.

I would appreciate if you could shed the light on the solution.

Answer 1

At least I can answer you first question : why can't the price charged to player 1 be a function of $v_1$?

The answer is that the mechanism would violate incentive compatibility. In order to derive a contradiction, assume that such mechanism exists and that the price charged to agent $1$ is a function of her value.

Denote by $p_1$ the price charged to player 1. As $p_1$ is a function of $v_1$, there must exists $v_1' \neq v_1''$ such that $p_1(v_1')\neq p_1(v_1'')$.

Without loss of generality, assume $p_1(v_1')< p_1(v_1'')$.

Now assume that the real value of player $1$ is $v_1''$, and the real value of $2$ is $v_2$ such that both $v_1' + v_2 > C$ and $v_1''+v_2>C$.

By assumption, the printer must be bought and it will be bought whether $1$ report her true value $v_1''$ or the false value $v_1$.

But then player $1$ has an incentive to misreport her preferences, claiming her value is $v_1'$, because she would be charged less.

Answer 2

I'd like to elaborate a bit on what Martin said about the VCG mechanisms and clarify my misleading comment (the theorem I should have quoted is Green-Laffront).

This is a public project problem, with three agents. Agents $1$ and $2$ have linear utility

$$ u_i(k ; v_i) = k (v_i + t_i), \; i = 1, 2 $$

where $v_i$ is agent $i$'s valuation of the project, $t_i$ is the transfer, and $k \in \{0,1\}$ denotes project selection; $k = 1$ means project is built (printer being purchased in this case). Agents $0$ has valuation $-C$ if project is built. Agent $0$ has no private information.

According to your problem, the requirements for the mechanism $(k(v_1, v_2), t(v_1, v_2))$ are:

1. Incentive compatibility (in dominant strategies): Player's best response is to report true type regardless of the other player's reported type.

2. Individual rationality: For each player, in the interim stage (i.e. after drawing his type), the equilibrium payoff must weakly dominate reservation utility $0$.

3. Efficient project selection: Let $(\hat{v_1}, \hat{v}_2)$ be the reported type profile. If $\hat{v}_1 + \hat{v}_2 - C > 0$, $k(\hat{v_1}, \hat{v}_2) = 1$.

4. No Subsidy: If $k(\hat{v_1}, \hat{v}_2) = 1$, then $t_1(\hat{v_1}, \hat{v}_2) + t_2(\hat{v_1}, \hat{v}_2) \leq -C$.

These conditions together are simply too strong to hold simultaneously.

IC in dominant strategies means

$$ v_1 - t_1(v_1, v_2) \geq v_1 - t_1(v_1', v_2) $$

for all $v_1$ and $v_1'$, and $v_2$. So $t_1(v_1, v_2) = t_1(v_1', v_2)$ for all $v_1$ and $v_1'$, i.e. the transfer of player $1$ does not depend on $v_1$. Now consider the case $v_1 = \epsilon$ and $v_2 = C - \epsilon$ where $\epsilon$ is as small as you'd like. Efficient project selection means $k(\epsilon, C - \epsilon) = 1$, and by IR, $t_1(\epsilon, C - \epsilon) \geq - \epsilon$. Therefore

$$ t_1(v_1, C - \epsilon) \geq - \epsilon, \; \forall v_1. $$

Player 1 cannot be charged more than $\epsilon$ when $v_2 = C - \epsilon$. Same goes for player $2$. So

$$ t_1(C - \epsilon, C - \epsilon) + t_2(C - \epsilon, C - \epsilon) \geq - 2 \epsilon. $$

This violates the No Subsidy condition.

If we dial back the requirements a little and only assume efficient projection selection and IC (in dominant strategies), then a mechanism from the VCG class would solve the problem. One particular VCG mechanism is the Clarke/pivotal mechanism:

If project is built, player $1$ is charged $(v_{2} - C)$ if $v_2 < C < v_1 + v_2$ (i.e. he's pivotal, project doesn't get built without him, and $0$ otherwise.

The Clarke mechanism shows VCG-class does not satisfy No Subsidy in general (e.g. take the same type profile $(C- \epsilon, C- \epsilon)$ as the above argument). A related impossibility result is the following:

Theorem (Green-Laffront) In the environment where agents have quasilinear utilities, consider social choice functions whose domain is the set of all possible value functions on project selection. If such a SCF is implementable in dominant strategies, then it cannot be ex post efficient, i.e. satisfy both efficient project selection and budget balance.

If implementability in dominant strategies is relaxed to implementability in Bayesian Nash equilibrium (one then needs to specify the distribution of types for the problem), ex post efficiency can be achieved by the expected externality mechanism. But then IR still may not hold. An impossibility result in this setting is the Meyerson-Satterthwaite theorem.