Moving the proofs to the appendix, improving the flow

1 files changed, 0 insertions, 122 deletions

diff --git a/proofs.tex b/proofs.tex
index 4cefc25..e69de29 100644
--- a/proofs.tex
+++ b/proofs.tex
@@ -1,122 +0,0 @@
-\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
-
-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$ 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$. 
-
-    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.
-\junk{
-    Using Singer's characterization of the threshold payments
-    \cite{singer-mechanisms}, one can verify that they can be computed in time
-    $O(\text{poly}(n, d))$.
-    }
-\end{proof}
-
-Finally, we prove the approximation ratio of the mechanism.
-
-We use the following lemma from \cite{chen} which bounds $OPT$ in terms of
-the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the
-element of maximum value.
-
-\begin{lemma}[\cite{chen}]\label{lemma:greedy-bound}
-Let $S_G$ be the set computed in Algorithm \ref{mechanism} and let 
-$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$. We have:
-\begin{displaymath}
-OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
-\end{displaymath}
-\end{lemma}
-
-Using Proposition~\ref{prop:relaxation} and~\ref{lemma:greedy-bound} we can complete the proof of
-Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if
-$OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from
-$\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set
-$S^*$ allocated by the mechanism is such that:
-\begin{equation} \label{approxbound}
-OPT
-\leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!
-+ \! \varepsilon .
-\end{equation}
-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 4 of the algorithm holds, then
-\begin{displaymath}
-    V(i^*) \geq \frac{1}{C}L^*_{-i^*}-\frac{\varepsilon}{C} \geq
-    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}.
-\end{displaymath}
-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 $L^*_{-i^*}\leq L^*_c$ and
-applying Proposition~\ref{prop:relaxation}, we get
-\begin{displaymath}
-    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},
-\begin{displaymath}
-    V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
-    + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}.
-\end{displaymath}
-Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
-\begin{align*}
-    V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) 
-    + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}.
-\end{align*}
-Finally, using Lemma~\ref{lemma:greedy-bound} again, we get
-\begin{equation}\label{eq:bound2}
-    OPT(V, \mathcal{N}, B) \leq 
-    \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}\right) V(S_G)
-    + \frac{2e\varepsilon}{C(e-1)- 6e + 2}.
-\end{equation}
-To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1}
-and \eqref{eq:bound2} respectively, we wish to chose $C$ that minimizes
-\begin{displaymath}
-    \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}
-            \right)\right).
-\end{displaymath}
-This function has two minima, only one of those is such that $C(e-1) -6e
-+2 \geq 0$. This minimum is
-\begin{equation}\label{eq:constant}
-    C =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}.
-\end{equation}
-For this minimum, $\frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon.$
-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
-
-
-\subsection{Proof of Theorem \ref{thm:lowerbound}}
-
-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]$
-and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must
-be in the set selected by the mechanism, otherwise the ratio is unbounded,
-a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity
-it remains in the solution; by  threshold payment, it is paid at least
-$B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility
-and individual rationality: hence, the selected set attains a value $\log2$,
-while the optimal value is $2\log 2$.\hspace*{\stretch{1}}\qed