I have a set of objects $A=\{a_1,a_2,a_3,\cdots,a_m\}$ and one player, who proposes a vector of valuations $t=(t_1~t_2~t_3~\cdots~t_m)$ for the $m$ objects. $T$ is the set of all such valuation types. Given $T$ I design an allocation function $$f:T\rightarrow [0,1]^m$$ and a payment function $$p:T\rightarrow \mathbb{R}$$ The mechanism $(f,p)$ is said to be Incentive compatible if $$t(f(t))-p(t)\geq t(f(t'))-p(t')~~\forall t,t'\in T~~~~~~~~~~~~(1)$$ One can easily derive from the above eqaution that incentive compatibility implies the following: $$t(f(t))+t'(f(t'))\geq t(f(t'))+t'(f(t))~~~~~~~~~~~~~~~~~~(2)$$ that is, $(1)\Rightarrow (2)$.

Is the converse ($(2)\Rightarrow (1)$) true?

  • $\begingroup$ I have derived that $p(t)$ is a function of $f(t)$, that is if $f(t)=f(t')$ then $p(t)=p(t')$. I am trying to analytically write $p(t)$ as an implicit function of $f(t)$. Please help $\endgroup$ – Abishanka Saha Oct 18 '16 at 5:50

First of all, the general form of the problem you got there is extremely demanding. In multidimensional screening problems, analytically often all hell breaks loose in a sense that it is just not tractable. One way out might be this recent approach by Gabriel Carrol: Robustness and Separation in Multidimensional Screening (also provides an introduction that hints at the intractibility of the problem).

Coming back to your question: $(2)$ does not imply $(1)$, because $(2)$ only depends on $f$ and you can add a transfer rule that is not IC. As a counterexample, consider a single good, $m=1$. Take some strictly IC mechanism, $(f, p)$ and consider two types, $t$ and $t'$. So, $(1)$ is $$U(t):= f(t)t - p(t) > f(t')t - p(t')\\ U(t'):= f(t')t' - p(t')> f(t)t' - p(t)$$ and by construction $(2)$ holds as well. Let $t'>t$ and a lager allocation probability $f(t') > f(t)$ is accompanied by a larger expected transfer, $p(t') > p(t)$ - otherwise $t$ would love to fake being $t'$.

Now, construct $\widetilde{f}(s) = f(s)$ for all $s\in T$ and let $\widetilde p (t)= p(t')$ and $\widetilde p (t')= p(t)$. Since $(2)$ only depends on the allocation function $f$ and these functions are the same in both mechanisms, $(2)$ holds for $(\widetilde{f}, \widetilde{p})$. Obviously, $(1)$ is violated for the reason named above: $$\widetilde f (t') t - \widetilde p(t') > \widetilde f (t) t - \widetilde p(t).$$

To address your other problem (in your comment), use the integral formulation of expected utility. Rewriting $(1)$ yields, $$f( t)(t-t'))\geq U(t) - U(t') \geq f (t' )(t-t')$$ implying that $U$ is Lipschitz continuous, implying $U$ is differentiable a.e., and equals the integral over its derivative: $$U (t) = U(\underline t) + \int_{\underline t}^t f(s) ds$$ where $\underline t$ is the lowest possible type. Then, you rewrite, $$f (t) t - p(t) = U(\underline t) + \int_{\underline t}^t f(s) ds \\ f (t) t - U(\underline t) - \int_{\underline t}^t f(s) ds = p(t).$$ Suppose $\underline t=0$, then $$p(t) = p(0) + f(t)t - \int_{0}^t f(s) ds.$$ This implies the revenue equivalence theorem: If two auctions have the same allocation rule, payment functions (and thus revenue) can only differ by a constant. The same trick works for multi-unit auctions with multi-unit demand, see, e.g., Krishna, Ch 14.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.