Add proof of Myerson's lemma. Introduce the counterexample in the body.

1 files changed, 5 insertions, 0 deletions

diff --git a/problem.tex b/problem.tex
index 033c7e1..0b10107 100644
--- a/problem.tex
+++ b/problem.tex
@@ -207,6 +207,11 @@ Ideally, we would like the allocation $S$ to be of maximal value; however, truth
 \end{itemize}
 %\emph{W.l.o.g.}, we assume in the sequel that costs are at most $B$, \emph{i.e.}, $c_i\in[0,B]$, for all $i\in \mathcal{N}$. This is because, by individual rationality,  any $i$ for which $c_i>B$ clearly cannot be allocated; as such, any mechanism that satisfies the above properties ignores such subjects.
 
+Note that the algorithm given in \eqref{eq:max-algorithm} cannot be used in the
+strategic case. Indeed, it is known that using the MAX operator breaks
+truthfulness in general. A counterexample for the specific value function $V$
+defined in \eqref{obj} is provided in Appendix~\ref{sec:non-monotonicity}.
+
 \begin{comment}
 As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are  \emph{single parameter} auctions: each agent has only one
 private value (namely, $c_i$). As such, Myerson's Theorem \cite{myerson} gives