Section titles capitalization and splitting section 4

2 files changed, 5 insertions, 431 deletions

diff --git a/main.tex b/main.tex
index f11c4ee..2986eb1 100644
--- a/main.tex
+++ b/main.tex
@@ -4,7 +4,7 @@ In this section we present our mechanism for \SEDP. Prior approaches to budget
 feasible mechanisms for sudmodular maximization build upon the full information
 case which we discuss first.
 
-\subsection*{Submodular maximization in the full-information case}
+\subsection{Submodular Maximization in the Full Information Case}
 
 In the full-information case, submodular maximization under a budget constraint
 \eqref{eq:non-strategic} relies on a greedy heuristic in which elements are
@@ -32,7 +32,7 @@ This lemma immediately implies that the following algorithm:
 \end{equation}
 has an approximation ratio of $\frac{5e}{e-1}$.
 
-\subsection*{Submodular maximization in the strategic case}
+\subsection{Submodular Maximization in the Strategic Case}
 
 In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive
 compatibility. Indeed, \citeN{singer-influence} notes that this allocation
@@ -83,7 +83,7 @@ One of the main technical contribution of \citeN{chen} and
 \citeN{singer-influence} is to come up with appropriate relaxations for
 \textsc{Knapsack} and \textsc{Coverage} respectively.
 
-\subsection*{Our approach}
+\subsection{Our Approach}
 
 \sloppy
 We introduce a relaxation $L$ specifically tailored to the value function of
@@ -156,431 +156,3 @@ In addition, we prove the following simple lower bound.
 There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. 
 \end{theorem}
 
-\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.
-
-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}))$.
-\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
-    $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  which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints
- is not too far from $OPT$.  
-\begin{lemma}[Approximation]\label{lemma:relaxation}
-     $   OPT' \leq 2 OPT
-        + 2\max_{i\in\mathcal{N}}V(i)$
-\end{lemma}
-The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
-
-Using Lemma~\ref{lemma:relaxation} 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 $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).  If the condition on line 3 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} 
-\end{displaymath}
-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}
-Note that $OPT_{-i^*}'\leq OPT'$. If the condition  does not hold, from Lemmas
-\ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
-\begin{align*}
-    V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
-    \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
-    & \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{align*}
-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 again Lemma~\ref{lemma:greedy-bound}, 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 for $C=C^*$ such that:
-\begin{displaymath}
-    C^* = \argmin_C 
-    \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}
-            \right)\right)
-\end{displaymath}
-This equation has two solutions. Only one of those is such that $C(e-1) -6e
-+2 \geq 0$. This solution is:
-\begin{displaymath}
-    C^* =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)} \label{eq:c}
-\end{displaymath}
-For this solution, $\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 Lemma~\ref{lemma:relaxation}}\label{sec:relaxation}
-
-We need to prove that for our relaxation $L$ given by
-\eqref{eq:our-relaxation}, $OPT'$ is close to $OPT$ as stated in
-Lemma~\ref{lemma:relaxation}. Our analysis follows the \emph{pipage rounding}
-framework of \citeN{pipage}.
-
-This framework uses the \emph{multi-linear} extension $F$ of the submodular
-function $V$. Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the set $S$ if we select each element $i$ in $\mathcal{N}$ independently with probability $\lambda_i$:
-\begin{displaymath}
-    P_\mathcal{N}^\lambda(S) \defeq \prod_{i\in S} \lambda_i
-    \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i).
-\end{displaymath}
-Then, the \emph{multi-linear} extension $F$ is defined by:
-\begin{displaymath}
-    F(\lambda) 
-    \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big]
-    = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
-\end{displaymath}
-
-For \EDP{}  the multi-linear extension can be written:
-\begin{equation}\label{eq:multi-linear-logdet}
-    F(\lambda) = \mathbb{E}_{S\sim
-    P_\mathcal{N}^\lambda}\bigg[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big].
-\end{equation}
-Note that the relaxation $L$ that we introduced in \eqref{eq:our-relaxation},
-follows naturally from the \emph{multi-linear} relaxation by swapping the
-expectation and the $\log\det$ in \eqref{eq:multi-linear-logdet}:
-\begin{displaymath}
-    L(\lambda) = \log\det\left(\mathbb{E}_{S\sim
-    P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right).
-\end{displaymath}
-
-The proof proceeds as follows:
-\begin{itemize}
-\item First, we prove that $F$ admits the following rounding property: let
-$\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one
-fractional component of $\lambda$ for another until one of them becomes
-integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and
-for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point
-$\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n
-\lambda_i c_i \leq B$.  This rounding property is referred to in the literature
-as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or
-$\varepsilon$-convexity by \citeN{pipage}. This is stated and proven in
-Lemma~\ref{lemma:rounding} and allows us to bound $F$ in terms of $OPT$.
-\item Next, we prove the central result of bounding $L$  appropriately in terms
-of the multi-linear relaxation $F$ (Lemma \ref{lemma:relaxation-ratio}).
-\item Finally, we conclude the proof of Lemma~\ref{lemma:relaxation} by
-combining Lemma~\ref{lemma:rounding} and Lemma~\ref{lemma:relaxation-ratio}.
-\end{itemize}
-
-\begin{comment}
-Formally, if we define:
-\begin{displaymath}
-    \tilde{F}_\lambda(\varepsilon) \defeq F\big(\lambda + \varepsilon(e_i
-    - e_j)\big)
-\end{displaymath}
-where $e_i$ and $e_j$ are two vectors of the standard basis of
-$\reals^{n}$, then $\tilde{F}_\lambda$ is convex. Hence its maximum over the interval:
-\begin{displaymath}
- I_\lambda = \Big[\max(-\lambda_i,\lambda_j-1), \min(1-\lambda_i, \lambda_j)\Big]
-\end{displaymath}
-is attained at one of the boundaries of $I_\lambda$ for which one of the $i$-th
-or the $j$-th component of $\lambda$ becomes integral.
-\end{comment}
-
-\begin{lemma}[Rounding]\label{lemma:rounding}
-    For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible
-    $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is
-    fractional %, that is, lies in $(0,1)$ and:
-     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
-\end{lemma}
-\begin{proof}
-    We give a rounding procedure which, given a feasible $\lambda$ with at least
-    two fractional components, returns some feasible $\lambda'$ with one less fractional
-    component such that $F(\lambda) \leq F(\lambda')$.
-
-    Applying this procedure recursively yields the lemma's result.
-    Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two
-    fractional components of $\lambda$ and let us define the following
-    function:
-    \begin{displaymath}
-        F_\lambda(\varepsilon) = F(\lambda_\varepsilon)
-        \quad\textrm{where} \quad
-        \lambda_\varepsilon = \lambda + \varepsilon\left(e_i-\frac{c_i}{c_j}e_j\right)
-    \end{displaymath}
-    It is easy to see that if $\lambda$ is feasible, then:
-    \begin{equation}\label{eq:convex-interval}
-        \forall\varepsilon\in\Big[\max\Big(-\lambda_i,(\lambda_j-1)\frac{c_j}{c_i}\Big), \min\Big(1-\lambda_i, \lambda_j
-        \frac{c_j}{c_i}\Big)\Big],\;
-            \lambda_\varepsilon\;\;\textrm{is feasible}
-    \end{equation}
-    Furthermore, the function $F_\lambda$ is convex; indeed:
-    \begin{align*}
-        F_\lambda(\varepsilon)
-        & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
-        (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\
-        & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})
-         + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\
-         & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big]
-    \end{align*}
-    Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is:
-    \begin{displaymath}
-        \frac{c_i}{c_j}\mathbb{E}_{S'\sim
-        P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
-            V(S'\cup\{i\})+V(S'\cup\{i\})\\
-        -V(S'\cup\{i,j\})-V(S')\Big]
-    \end{displaymath}
-    which is positive by submodularity of $V$. Hence, the maximum of
-    $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is
-    attained at one of its limit, at which either the $i$-th or $j$-th component of
-    $\lambda_\varepsilon$ becomes integral.
-\end{proof}
-
-
-\begin{lemma}\label{lemma:relaxation-ratio}
- %   The following inequality holds:
-For all $\lambda\in[0,1]^{n},$
-    %\begin{displaymath}
-     $           \frac{1}{2}
-        \,L(\lambda)\leq
-        F(\lambda)\leq L(\lambda)$.
-    %\end{displaymath}
-\end{lemma}
-\begin{proof}
-    The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}(\lambda)}$ follows by the concavity of the $\log\det$ function.
-    To show the lower bound, 
-    we first prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
-    F(\lambda)/\partial_i L(\lambda)$, where
-    $\partial_i\, \cdot$ denotes the partial derivative with respect to the
-    $i$-th variable.  
-
-   Let us start by computing the derivatives of $F$ and
-    $L$ with respect to the $i$-th component.
-    Observe that:
-    \begin{displaymath}
-        \partial_i P_\mathcal{N}^\lambda(S) = \left\{
-            \begin{aligned}
-                & P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})\;\textrm{if}\; i\in S \\
-                & - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\;\textrm{if}\;
-                i\in \mathcal{N}\setminus S \\
-            \end{aligned}\right.
-    \end{displaymath}
-    Hence:
-    \begin{displaymath}
-        \partial_i F(\lambda) =
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S)
-        - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)
-    \end{displaymath}
-    Now, using that every $S$ such that $i\in S$ can be uniquely written as
-    $S'\cup\{i\}$, we can write:
-    \begin{displaymath}
-        \partial_i F(\lambda) =
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\big(V(S\cup\{i\})
-        - V(S)\big)
-    \end{displaymath}
-    The marginal contribution of $i$ to
-    $S$ can be written as 
-\begin{align*}
-V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(I_d 
-    + \T{X_S}X_S + x_i\T{x_i})
-    - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\\
-    &  = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d +
-\T{X_S}X_S)^{-1})
- = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)
-\end{align*}
-where $A(S) =I_d+ \T{X_S}X_S$. 
-%  $  V(S\cup\{i\}) - V(S) = \frac{1}{2}\log\left(1 +  \T{x_i} A(S)^{-1}x_i\right)$.
-Using this,
-    \begin{displaymath}
-        \partial_i F(\lambda) = \frac{1}{2}
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
-        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
-    \end{displaymath}
-     The computation of the derivative of $L$ uses standard matrix
-    calculus. Writing $\tilde{A}(\lambda) = I_d+\sum_{i\in
-    \mathcal{N}}\lambda_ix_i\T{x_i}$:
-    \begin{displaymath}
-        \det \tilde{A}(\lambda + h\cdot e_i) = \det\big(\tilde{A}(\lambda)
-        + hx_i\T{x_i}\big)
-         =\det \tilde{A}(\lambda)\big(1+
-        h\T{x_i}\tilde{A}(\lambda)^{-1}x_i\big)
-    \end{displaymath}
-    Hence:
-    \begin{displaymath}
-       \log\det\tilde{A}(\lambda + h\cdot e_i)= \log\det\tilde{A}(\lambda)
-        + h\T{x_i}\tilde{A}(\lambda)^{-1}x_i + o(h)
-    \end{displaymath}
-    Finally:
-    \begin{displaymath}
-        \partial_i L(\lambda)
-        =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i
-    \end{displaymath}
-
-For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if
-$A-B$ is positive definite (positive semi-definite).  This order allows us to
-define the notion of a \emph{decreasing} as well as  \emph{convex} matrix
-function, similarly to their real counterparts. With this definition, matrix
-inversion is decreasing and convex over symmetric positive definite matrices.
-In particular,
-\begin{gather*}
-        \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}
-\end{gather*}
- Observe that:
-    \begin{gather*}
-        \forall S\subseteq\mathcal{N}\setminus\{i\},\quad
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})\\
-        \forall S\subseteq\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) 
-        \geq P_\mathcal{N}^\lambda(S)
-    \end{gather*}
-    Hence:
-    \begin{align*}
-        \partial_i F(\lambda) 
-      %  & = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_\mathcal{N}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
-        & \geq \frac{1}{4}
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
-        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
-        &\hspace{-3.5em}+\frac{1}{4}
-        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})
-        \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
-        &\geq \frac{1}{4}
-        \sum_{S\subseteq\mathcal{N}}
-        P_\mathcal{N}^\lambda(S)
-        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
-    \end{align*}
-    Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq
-    \norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$.
-    Hence:
-    \begin{displaymath}
-        \partial_i F(\lambda) \geq
-        \frac{1}{4}
-        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)^{-1}\bigg)x_i
-    \end{displaymath}
-    Finally, using that the inverse is a matrix convex function over symmetric
-    positive definite matrices:
-    \begin{displaymath}
-        \partial_i F(\lambda) \geq
-        \frac{1}{4}
-        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i
-        = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i
-         = \frac{1}{2}
-     \partial_i L(\lambda)
-    \end{displaymath}
-
-Having bound the ratio between the partial derivatives, we now bound the ratio $F(\lambda)/L(\lambda)$ from below. Consider the following cases.
-    First, if the minimum of the ratio
-    $F(\lambda)/L(\lambda)$ is attained at a point interior to the hypercube, then it is
-    a critical point, \emph{i.e.}, $\partial_i \big(F(\lambda)/L(\lambda)\big)=0$ for all $i\in \mathcal{N}$; hence, at such a critical point:
-    \begin{equation}\label{eq:lhopital}
-        \frac{F(\lambda)}{L(\lambda)}
-        = \frac{\partial_i F(\lambda)}{\partial_i
-        L(\lambda)} \geq \frac{1}{2}
-    \end{equation}
-    Second, if the minimum is attained as 
-    $\lambda$ converges to zero in, \emph{e.g.}, the $l_2$ norm, by the Taylor approximation, one can write:
-    \begin{displaymath}
-        \frac{F(\lambda)}{L(\lambda)}
-        \sim_{\lambda\rightarrow 0}
-        \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F(0)}
-        {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L(0)}
-        \geq \frac{1}{2},
-    \end{displaymath}
-    \emph{i.e.}, the ratio $\frac{F(\lambda)}{L(\lambda)}$ is necessarily bounded from below by 1/2 for small enough $\lambda$. 
-       Finally, if the minimum is attained on a face of the hypercube $[0,1]^n$ (a face is
-    defined as a subset of the hypercube where one of the variable is fixed to
-    0 or 1), without loss of generality, we can assume that the minimum is
-    attained on the face where the $n$-th variable has been fixed
-    to 0 or 1. Then, either the minimum is attained at a point interior to the
-    face or on a boundary of the face. In the first sub-case, relation
-    \eqref{eq:lhopital} still characterizes the minimum for $i< n$.
-    In the second sub-case, by repeating the argument again by induction, we see
-    that all is left to do is to show that the bound holds for the vertices of
-    the cube (the faces of dimension 1).  The vertices are exactly the binary
-    points, for which we know that both relaxations are equal to the value
-    function $V$. Hence, the ratio is equal to 1 on the vertices.
-\end{proof}
-
-\begin{proof}[of Lemma~\ref{lemma:relaxation}]
-Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
-    = OPT'$. By applying Lemma~\ref{lemma:relaxation-ratio}
-    and Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
-    one fractional component such that:
-    \begin{equation}\label{eq:e1}
-        L(\lambda^*) \leq 2
-        F(\bar{\lambda})
-    \end{equation}
-    Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$
-    denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$.
-    By definition of the multi-linear extension $F$:
-    \begin{displaymath}
-        F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\})
-    \end{displaymath}
-    By submodularity of $V$, $V(S\cup\{i\})\leq V(S) + V(\{i\})$, hence:
-    \begin{displaymath}
-        F(\bar{\lambda}) \leq V(S) + V(i)
-    \end{displaymath}
-    Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
-    $V(S)\leq OPT$. Hence:
-    \begin{equation}\label{eq:e2}
-        F(\bar{\lambda}) \leq  OPT
-        + \max_{i\in\mathcal{N}} V(i)
-    \end{equation}
-    Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma. \hspace*{\stretch{1}}\qed
-\end{proof}
-
-\subsection{Proof of Theorem \ref{thm:lowerbound}}
-
-\begin{proof}
-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$.
-\end{proof}
-
diff --git a/paper.tex b/paper.tex
index fde8270..3b13ea1 100644
--- a/paper.tex
+++ b/paper.tex
@@ -35,6 +35,8 @@ S. Muthukrishnan \affil{Rutgers University, Microsoft Research}}
 \input{problem}
 \section{Mechanism for \SEDP{}}
 \input{main}
+\section{Proofs}
+\input{proofs}
 \section{Extension to Other Problems}\label{sec:ext}
 \input{general}
 %\section{Conclusion}