Unifying pass over the whole paper

1 files changed, 20 insertions, 23 deletions

diff --git a/proofs.tex b/proofs.tex
index 6169bb5..4cefc25 100644
--- a/proofs.tex
+++ b/proofs.tex
@@ -1,26 +1,25 @@
 \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 
-We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual
-rationality follow from monotonicity and threshold payments.  Monotonicity and
-budget feasibility follow the same steps as the analysis of \citeN{chen};
- for the sake of completeness, we restate their proof in the Appendix.
+We now present the proof of Theorem~\ref{thm:main}. $\delta$-truthfulness and
+individual rationality follow from $\delta$-monotonicity and threshold
+payments. $\delta$-monotonicity and budget feasibility follow the same steps as the
+analysis of \citeN{chen}; for the sake of completeness, we restate their proof
+in the Appendix.
 
 The complexity of the mechanism is given by the following lemma.
 
 \begin{lemma}[Complexity]\label{lemma:complexity}
-    For any $\varepsilon > 0$, the complexity of the mechanism  is
-    $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
+    For any $\varepsilon > 0$ and any $\delta>0$, the complexity of the mechanism  is
+    $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
 \end{lemma}
 
 \begin{proof}
     The value function $V$ in \eqref{modified} can be computed in time
     $O(\text{poly}(n, d))$ and the mechanism only involves a linear
     number of queries to the function $V$. 
-    The function $\log\det$ is concave and self-concordant (see
-    \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be found
-    to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$  of iterations of Newton's method. Each iteration  can be
-    done in time $O(\text{poly}(n, d))$. Thus, line 3 of
-    Algorithm~\ref{mechanism} can be computed in time
+
+    By Proposition~\ref{prop:monotonicity}, line 3 of Algorithm~\ref{mechanism}
+    can be computed in time
     $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. Hence the allocation
     function's complexity is as stated. 
     %Payments can be easily computed in time  $O(\text{poly}(n, d))$ as in prior work.
@@ -55,28 +54,26 @@ OPT
 \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!
 + \! \varepsilon .
 \end{equation}
-To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to
-$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume
-that on line 3 of Algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that
-$\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been
-computed (Lemma~\ref{lemma:complexity} states that this  is computed in time
-within our complexity guarantee).
+To see this, let $L^*_{-i^*}$ be the true maximum value of $L$ subject to
+$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line
+3 of Algorithm~\ref{mechanism}, we have
+$L^*_{-i^*}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{-i^*}+\varepsilon$.
 
-If the condition on line 3 of the algorithm holds, then
+If the condition on line 4 of the algorithm holds, then
 \begin{displaymath}
-    V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq
-    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}
+    V(i^*) \geq \frac{1}{C}L^*_{-i^*}-\frac{\varepsilon}{C} \geq
+    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}.
 \end{displaymath}
-as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
+Indeed, $L^*_{-i^*}\geq OPT_{-i^*}$ as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
 hence,
 \begin{equation}\label{eq:bound1}
     OPT\leq (1+C)V(i^*) + \varepsilon.
 \end{equation}
 
-If the condition  does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and
+If the condition  does not hold, by observing that $L^*_{-i^*}\leq L^*_c$ and
 applying Proposition~\ref{prop:relaxation}, we get
 \begin{displaymath}
-    V(i^*)  \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
+    V(i^*)\leq \frac{1}{C}L^*_{-i^*} + \frac{\varepsilon}{C}
     \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}.
 \end{displaymath}
 Applying Lemma~\ref{lemma:greedy-bound},