moved algo to appendix

4 files changed, 20 insertions, 22 deletions

diff --git a/appendix.tex b/appendix.tex
index 0f6e6b4..f9564c3 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -513,7 +513,8 @@ Formally, there must exist some $\alpha\geq 1$
     should be computable in time polynomial in various parameters. 
     %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$?  Needed to say something in general, but not in our case where the value function can be computed in polynomial time}.
 \end{itemize}
-
+\section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson}
+\input{myerson}
 
 \section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 \begin{algorithm}[!t]
@@ -719,7 +720,7 @@ Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2}
 gives the approximation ratio in \eqref{approxbound}, and concludes the proof
 of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
 
-\section{Proof of Theorem \ref{thm:lowerbound}}
+\section{Proof of Theorem \ref{thm:lowerbound}}\label{proofoflowerbound}
 
 Suppose, for contradiction, that such a mechanism exists. Consider two
 experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$
diff --git a/main.tex b/main.tex
index 859c8f4..0dfa162 100644
--- a/main.tex
+++ b/main.tex
@@ -70,13 +70,11 @@ c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
 We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}:
 \begin{theorem}\label{thm:main}
     \sloppy
-    For any $\delta>0$ the allocation described in Algorithm~\ref{mechanism},
-    along with threshold payments, is $\delta$-truthful, individually rational
-    and budget feasible.  Furthermore, there exists an absolute constant $C$
-    such that, for any $\varepsilon>0$, the mechanism runs in time
+    For any $\delta>0$, and any $\epsilon>0$,  there exists a $\delta$-truthful, individually rational
+    and budget feasible mechanim for \EDP{} that runs in time
     $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$
     and returns
-    a set $S^*$ such that:
+    a set $S^*$ such that
 %    \begin{align*}
        $ OPT
          \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
@@ -84,9 +82,7 @@ We can now state our main result, which is proved in Appendix~\ref{sec:proofofma
          \simeq 12.98V(S^*) + \varepsilon.$
 %    \end{align*}
 \end{theorem}
-The value of the constant $C$ is given by \eqref{eq:constant} in
-Appendix~\ref{sec:proofofmainthm}.
-In addition, we prove the following simple lower bound.
+In addition, we prove the following simple lower bound, proved in Appendix~\ref{proofoflowerbound}.
 
 \begin{theorem}\label{thm:lowerbound}
 There is no $2$-approximate, truthful, budget feasible, individually rational
diff --git a/myerson.tex b/myerson.tex
index bcfedc4..8c80cf6 100644
--- a/myerson.tex
+++ b/myerson.tex
@@ -10,20 +10,22 @@ other users:
 We distinguish four cases depending on the value of $s_i(c_i, c_{-i})$ and
 $s_i'(c_i', c_{-i})$.
 
-Since the mechanism is normalized, if $s_i(c_i, c_{-i})= s_i(c_i', c_{-i})=0$,
+\begin{enumerate}
+\item $s_i(c_i, c_{-i})= s_i(c_i', c_{-i})=0$.
+Since the mechanism is normalized 
 we have $p_i(c_i, c_{-i}) = p_i(c_i', c_{-i})= 0$ and \eqref{eq:local-foobar}
 is true.
-
+\item $s_i(c_i', c_{-i}) = s_i(c_i, c_{-i}) = 1$.
 Note that $i$ is paid her threshold payment when allocated, and since this
 payment does not depend on $i$'s reported cost, \eqref{eq:local-foobar} is true
-(and is in fact an equality) when $s_i(c_i', c_{-i}) = s_i(c_i, c_{-i}) = 1$.
-
-If $s_i(c_i', c_{-i}) = 0$ and $s_i(c_i, c_{-i}) = 1$, we have $p_i(c_i',
+(and is in fact an equality).
+\item $s_i(c_i', c_{-i}) = 0$ and $s_i(c_i, c_{-i}) = 1$.
+ We then have $p_i(c_i',
 c_{-i}) = 0$ by normalization and \eqref{eq:local-foobar} follows from
 individual rationality.
-
-Finally, let us assume that $s_i(c_i', c_{-i}) = 1$ and $s_i(c_i, c_{-i}) = 0$.
+\item $s_i(c_i', c_{-i}) = 1$ and $s_i(c_i, c_{-i}) = 0$.
 By $\delta$-decreasingness of $s_i$, $c_i \geq c_i'+\delta$, and $s_i(c_i,
 c_{-i}) = 0$ implies that $i$'s threshold payment is less than $c_i$,
 \emph{i.e.} $p_i(c_i', c_{-i}) \leq c_i$. This last inequality is equivalent to
-\eqref{eq:local-foobar} in this final case.
+\eqref{eq:local-foobar} in this final case. \qed
+\end{enumerate}
diff --git a/paper.tex b/paper.tex
index 87b9697..eb9a4b5 100644
--- a/paper.tex
+++ b/paper.tex
@@ -41,11 +41,10 @@
 \bibliography{notes}
 \appendix
 \input{appendix}
-\section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson}
-\input{myerson}
-\section{Non-Truthfulness of the Maximum Operator}\label{sec:non-monotonicity}
-\input{counterexample}
 \section{Extensions}\label{sec:ext}
 \input{general}
+\section{Non-Truthfulness of the Maximum Operator}\label{sec:non-monotonicity}
+\input{counterexample}
+
 
 \end{document}