<p>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: <a href="http://web.stanford.edu/~gdc/marginalrobust.pdf" rel="noreferrer">Robustness and Separation in Multidimensional Screening</a> (also provides an introduction that hints at the intractibility of the problem).</p>

<p>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) &gt; f(t')t - p(t')\\
U(t'):= f(t')t' - p(t')&gt; f(t)t' - p(t)$$
and by construction $(2)$ holds as well.
Let $t'&gt;t$ and a lager allocation probability $f(t') &gt; f(t)$ is accompanied by a larger expected transfer, $p(t') &gt; p(t)$ - otherwise $t$ would love to fake being $t'$.</p>

<p>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') &gt; \widetilde f (t) t - \widetilde p(t).$$ </p>

<p>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., <a href="http://www.sciencedirect.com/science/book/9780123745071" rel="noreferrer">Krishna</a>, Ch 14.</p>

CC BY-SA 3.0
2017-02-13T12:52:01.323Z
2017-02-13T12:52:01.323Z
Bayesian
<p>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 <em>Incentive compatible</em> 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)$.</p>

<p>Is the converse ($(2)\Rightarrow (1)$) true?</p>

CC BY-SA 3.0
2016-10-18T05:50:26.237Z
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
QED
<mechanism-design>
Incentive compatibility
QED
# Incentive compatibility

(Asked by: username_0 on 2016-10-17)

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?

**Tags:** mechanism-design
> **Comments:**
> **username_0**: 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  

---

## 1 answers

### Answer by username_1 on 2017-02-13. Score: 4

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](http://web.stanford.edu/~gdc/marginalrobust.pdf) (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](http://www.sciencedirect.com/science/book/9780123745071), Ch 14.


---

