# Incentive compatibility

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?

• 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 – Abishanka Saha Oct 18 '16 at 5:50

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.