Proof explaination: Every VCG mechanism is an incentive compatible mechanism The following is taken from these lecture notes.
Definition: A Groves mechanism is a mechanism $(f, p_1, \cdots, p_n)$ in a quasilinear environment in which:

*

*$f(b) \in argmax_{s \in S} \sum_i b_i(s)$, and

*for every $i, p_i(b)=h_i(b_{-i}) - \sum_{j \neq i} b_j(f(b))$, where $h_i: V_{-i} \to \mathbb{R}$ is an arbitrary function that does not depend on $b_i$ (let alone $v_i$).

Theorem: Every Grove Mechanism is an incentive compatible mechanism.
Proof. Observe that for all $b_i, b_{-i}$,
$$
u_i(b_i, b_{-i})=v_i(f(b_i, b_{-i})) -p_i(b_i, b_{-i})=v_i(f(b_i, b_{-i})) - h_i(b_{-i}) + \sum_{j \neq i} b_j(f(b_i, b_{-i})).
$$
On input $(v_i, b_{-i})$, the function $f$ returns a solution $s^*$, which maximizes $v_i(s^*) + \sum_{j \neq i} b_j(s^*)$. That is, for any $s \in S$, we have $v_i(s^*) + \sum_{j \neq i} b_j(s^*) \geq v_i(s) + \sum_{j \neq i} b_j(s)$. In particular, this holds for $s=f(b_i, b_{-i})$ for all possible $b_i$.
Consequently,
$$
v_i(f(v_i, b_{-i})) + \sum_{j \neq i} b_j(f(v_i, b_{-i})) \geq v_i(f(b_i, b_{-i})) + \sum_{j \neq i} b_j(f(b_i, b_{-i}))
$$
and therefore
$$
u_i(v_i, b_{-i}) \geq u_i(b_i, b_{-i})
$$
$$\tag*{$\square$}$$
The first step is clear to me. If agent $i$ reports $v_i$, then the mechanism returns the agent $s^*$ as the winner which maximizes $\sum_i b_i(s^*)$ and since in the first case $v_i=b_i$, meaning the reported valuation $b_i$ of agent $i$ coincides with his actual valuation $v_i$, this is equal to maximizing $v_i(s^*) + \sum_{j \neq i} b_j(s^*)$, which is greater or equal to $v_i(s) + \sum_{j \neq i} b_j(s)$ for any other $s$. But this seems only to hold if $v_i$ is actually reported by agent $i$.
If $b_i(s) > v_i(s)$, then it could be possible that $\sum_i b_i(s) > v_i(s) + \sum_{j \neq i} b_i(s)$. Thus agent $i$ could report $b_i \neq v_i$ and the mechanism would choose this solution.
Furthermore, the sum $v_i(s) + \sum_{j \neq i} b_j(s)$ is unknown to the mechanism. If $b_i \neq v_i$ is reported by agent $i$ and since the mechanism chooses $f(b) \in argmax_{s \in S} \sum_i b_i(s)$, the above inequalities could fail.
In other words: the social welfare $\sum_i b_i(s)$ could be maximized if $i$ tells a lie and therefore the utility of $i$ would be also maximized.
The last step

$$v_i(f(v_i, b_{-i})) + \sum_{j \neq i} b_j(f(v_i, b_{-i})) \geq v_i(f(b_i, b_{-i})) + \sum_{j \neq i} b_j(f(b_i, b_{-i}))$$

is therefore unclear to me.
Any hints or explainations are highly appreciated.
 A: I misunderstood the definition. A mechanism is incentive compatible if for all agents $i$ and all bids $b_{-i}$ (the bids of agents other than $i$) and all the bids $v_i'$ (all possible bids of agent $i$) the following holds
$$
v_i(f(v_i,b_{-i}))-p_i(v_i,b_{-i}) \geq v_i(f(v_i',b_{-i})) - p_i(v_i',b_{-i}))
$$
For the Grooves mechanism the price function is defined as $p_i(b)=h_i(b_{-i}) - \sum_{j \neq i} b_j(f(b))$ for all agents $i$.
Now, take the real evaluation $v_i$ and a lie $v_i'$ of agent $i$. Then it is indeed possible that
$$
\sum_{i} b_i(f(v_i', b_{-i})) > \sum_{i} b_i(f(v_i, b_{-i}))
$$
Hence, the social welfare would be maximized if $i$ tells a lie. BUT, the point is that agent $i$ wants to maximize $v_i(f(b)) - p_i(b)=v_i(f(b)) + \sum_{i \neq j} b_j(f(b)) - h_i(b_{i}))$ and this is independent of the bid of agent $i$. Thus, assume that $i$ reports the truth $v_i$, then the mechanism maximizes $\sum_i b_i(f(v_i, b_{-i}))$ which evaluates to $v_i(b) + \sum_{i \neq j} b_i(f(v_i, b_{-i}))$ and this is exactly the utility of player $i$.
Assume that $i$ reports a lie $v_i'$, then of course the mechanism would maximize $\sum_i b_i(f(v_i, b_{-i})) = v_i'(b) + \sum_{i \neq j} b_i(f(v_i, b_{-i}))$ but since $v_i \neq v_i'$ the utility of $i$ is not maximized in this scenario.
To put it a little bit differently: If the mechanism declares $v_i'$ as the winning bid, $b=b_{-i}\cup v_i'$ is optimal for the lie of agent $i$, but possibly suboptimal for its real utility. Thus, agent $i$ has no reason to lie (or even better: agent $i$ has an interest of maximizing the interest of the other agents).
