From 9b26f56120422dec9537505f3971ce67dd46c68f Mon Sep 17 00:00:00 2001 From: Thibaut Horel 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