We give a counterxample of the truthfulness of the maximum mechanism whose
allocation rule is defined in \eqref{eq:max-algorithm} when the value function
$V$ is as defined in \eqref{obj}. We denote by $(e_1, e_2, e_3)$ the canonical
basis of $\reals^3$ and define the following feature vectors: $x_1=e_1$,
$x_2=\frac{1}{\sqrt{2}}\cos\frac{\pi}{5}e_2
+ \frac{1}{\sqrt{2}}\sin\frac{\pi}{5}e_3$, $x_3=\frac{1}{\sqrt{2}}e_2$ and $x_4
= \frac{1}{2}e_3$, with associated costs $c_1 = \frac{5}{2}$, $c_2=c_3 = 1$ and
$c_4=\frac{2}{3}$. We also assume that the budget of the auctioneer is
$B=\frac{5}{2}$.

Note that $V(x_i) = \log(1+\|x_i\|^2)$, so $x_1$ is the point of maximum value.
Let us now compute the output of the greedy heuristic. We have:
\begin{equation}\label{eq:local-bazinga}
    \frac{V(x_1)}{c_1} \simeq 0.277,\;
    \frac{V(x_2)}{c_2}= \frac{V(x_3)}{c_3} \simeq 0.405,\;
    \frac{V(x_4)}{c_4} \simeq 0.335
\end{equation}
so the greedy heuristic will start by selecting $x_2$ or $x_3$. Without loss of
generality, we can assume that it selected $x_2$. From the Sherman-Morrison
formula we get:
\begin{displaymath}
    V(\{x_i, x_j\}) - V(x_i) = \log\bigg(1+ \|x_j\|^2
    - \frac{\ip{x_i}{x_j}^2}{1+\|x_i\|^2}\bigg)
\end{displaymath}
In particular, when $x_i$ and $x_j$ are orthogonal $V(\{x_i, x_j\}) = V(x_j)$.
This allows us to compute:
\begin{displaymath}
    \frac{V(\{x_2,x_3\})-V(x_2)}{c_3}=\log\bigg(1+\frac{1}{2}
    - \frac{1}{6}\cos^2\frac{\pi}{5}\bigg)\simeq 0.329
\end{displaymath}
\begin{displaymath}
    \frac{V(\{x_2,x_4\})-V(x_2)}{c_4}=\frac{3}{2}\log\bigg(1+\frac{1}{4}
    - \frac{1}{12}\sin^2\frac{\pi}{5}\bigg)\simeq 0.299
\end{displaymath}
Note that at this point $x_1$ cannot be selected without exceding the budget.
Hence, the greedy heuristic will add $x_3$ to the greedy solution and returns
the set $\{x_2, x_3\}$ with value:
\begin{displaymath}
    V(\{x_2, x_3\}) = V(x_2) + V(\{x_2, x_3\}) - V(x_2)\simeq 0.734
\end{displaymath}
In contrast, $V(x_1) \simeq 0.693$ so the mechanism will allocate to $\{x_2,
x_3\}$.

Let us now assume that user $3$ reduces her cost. It follows from
\eqref{eq:local-bazinga} that the greedy heuristic will start by adding her to
the greedy solution. Furthermore:
\begin{displaymath}
    \frac{V(\{x_3,x_2\})-V(x_3)}{c_2}=\log\bigg(1+\frac{1}{2}
    - \frac{1}{6}\cos^2\frac{\pi}{5}\bigg)\simeq 0.329
\end{displaymath}
\begin{displaymath}
    \frac{V(\{x_3,x_4\})-V(x_3)}{c_4}
    =\frac{3}{2}\log\bigg(1+\frac{1}{4}\bigg)\simeq 0.334
\end{displaymath}
Hence, the greedy solution will be $\{x_3, x_4\}$ with value:
\begin{displaymath}
    V(\{x_3, x_4\}) = V(x_3) + V(\{x_3, x_4\}) - V(x_3)\simeq 0.628
\end{displaymath}
As a consequence the mechanism will allocate to user $1$ in this case. By
reducing her cost, user 3, who was previously allocated, is now rejected by the
mechanism. This contradicts the monotonicity of the allocation rule, hence its
truthfulness by Myerson's theorem \cite{myerson}.