Reimport things from the appendix to the main part for the camera-ready version

1 files changed, 3 insertions, 46 deletions

diff --git a/appendix.tex b/appendix.tex
index 6926e00..63a8dd8 100755
--- a/appendix.tex
+++ b/appendix.tex
@@ -264,14 +264,7 @@ Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed
 %For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate
 %approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$.
 %\end{lemma}
-We begin by a description of Algorithm~\ref{alg:monotone} which computes an approximation of $L^*_c$, which is arbitrarily accurate \emph{and} $\delta$-decreasing. We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let $$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq  \dom_c . $$ 
-Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concave relaxation \eqref{eq:primal}:
-\begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal}
-\begin{split}  \text{Maximize:} &\qquad L(\lambda)\\
-\text{subject to:} & \qquad\lambda \in \dom_{c,\alpha}
-\end{split}
-\end{align}
-
+We begin by a description of Algorithm~\ref{alg:monotone} which computes an approximation of $L^*_c$, which is arbitrarily accurate \emph{and} $\delta$-decreasing. 
 %Note, that the feasible set in Problem~\eqref{eq:primal} increases (for the
 %inclusion) when the cost decreases. 
 %non-increasing.
@@ -594,31 +587,6 @@ Formally, there must exist some $\alpha\geq 1$ and $\beta>0$
 
 \section{Description of our mechanism for \EDP{} and proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 
-We begin by a description of the methodology used to construct our mechanism.
-Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in
-\mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set
-constructed greedily, by selecting elements of maximum marginal value per cost.
-The general framework used by \citeN{chen}  and by \citeN{singer-influence} for
-the \textsc{Knapsack}   and \textsc{Coverage} value functions contructs an
-allocation as follows. First, a polynomial-time, monotone approximation of
-$OPT$ is computed over all elements excluding $i^*$. The outcome of this
-approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the
-mechanism constructs an allocation $S_G$ greedily; otherwise, the only item
-allocated is the singleton $\{i^*\}$.  Provided that the approximation used is
-within a constant from $OPT$, the above allocation can be shown to also yield
-a constant approximation to $OPT$. Furthermore, using Myerson's
-Theorem~\cite{myerson}, it can be shown that this allocation combined with
-\emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below)
-constitute a truthful mechanism. 
-
-The approximation algorithms used in \cite{chen,singer-influence} are LP
-relaxations, and thus their outputs are monotone and can be computed exactly in
-polynomial time. We show 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, by
-being incorporated in the same framework.
-
-To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in Appendix~\ref{sec:myerson}.
 %
 %Instead, \citeN{singer-mechanisms} and \citeN{chen}
 %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
@@ -665,17 +633,6 @@ To obtain this result, we use the following modified version of Myerson's theore
 %$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
 %variant of Myerson's theorem.
 
-\begin{lemma}\label{thm:myerson-variant}
- A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
-$\delta$-truthful if:
-(a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq
-c_i-\delta$, for any
-fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i,
-c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
- agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$.
-\end{lemma}
-Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the
-above framework, yielding Theorem~\ref{thm:main}.
 
 \begin{algorithm}[!t]
     \caption{Mechanism for \SEDP{}}\label{mechanism}
@@ -706,11 +663,11 @@ above framework, yielding Theorem~\ref{thm:main}.
 \end{algorithm}
 
 
-We now present the proof of Theorem~\ref{thm:main}. 
+We present here the proof of Theorem~\ref{thm:main}. 
 Our mechanism for \EDP{} is composed of
 (a) the allocation function presented in Algorithm~\ref{mechanism}, and 
 (b) the payment function which pays each allocated agent $i$ her threshold
-payment as described in Myerson's Theorem.  In the case where $\{i^*\}$ is the
+payment as described in Myerson's Theorem (see Lemma~\ref{thm:myerson-variant}).  In the case where $\{i^*\}$ is the
 allocated set, her threshold payment is $B$. %(she would be have been dropped on
 %line 1 of Algorithm~\ref{mechanism} had she reported a higher cost).
 A closed-form formula for threshold payments when $S_G$ is the allocated set can