From 9b26f56120422dec9537505f3971ce67dd46c68f Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sat, 6 Jul 2013 15:54:48 +0200
Subject: Add proof of Myerson's lemma. Introduce the counterexample in the
 body.

---
 problem.tex | 5 +++++
 1 file changed, 5 insertions(+)

(limited to 'problem.tex')

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
-- 
cgit v1.2.3-70-g09d2

