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.

---
 main.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 29056c7..7f40d90 100644
--- a/main.tex
+++ b/main.tex
@@ -9,7 +9,7 @@ Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N
 
 Provided that the relaxation used within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and thus their optimal values are monotone and can be computed exactly in weakly polynomial time. In contrast, we extend these results by showing that the convex relaxation \eqref{eq:primal}, which can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to construct a $\delta$-truthful, constant approximation mechanism. 
 
-To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\note{FIXME!!!}
+To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\ref{sec:myerson}.
 %
 %Instead, \citeN{singer-mechanisms} and \citeN{chen}
 %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
-- 
cgit v1.2.3-70-g09d2

