Forgot to add proofs.tex

1 files changed, 428 insertions, 0 deletions

diff --git a/proofs.tex b/proofs.tex
new file mode 100644
index 0000000..ee57762
--- /dev/null
+++ b/proofs.tex
@@ -0,0 +1,428 @@
+\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{equation}\label{eq:constant}
+    C^* =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)} \label{eq:c}
+\end{equation}
+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}
+