path: root/main.tex

\label{sec:main}

In this section we present our mechanism for \EDP. Prior approaches to budget
feasible mechanisms build upon the full information case which we discuss
first.

\paragraph{Full information submodular maximization}

The best known approximation ratio $\frac{e}{e-1}$ for maximizing a submodular
set function under a cardinality constraint is attained by using a greedy
algorithm~\cite{nemhauser}. In this algorithm, elements are added to the
solution set according to the following greedy selection rule. Assume that
$S\subseteq \mathcal{N}$ is the solution set constructed thus far; then, the
next element $i$ to be included in $S$ is the one with the highest
\emph{marginal-value}: $V(S\cup\{i\}) - V(S)$. This process terminates when the
cardinality of $S$ reaches the cardinality limit.

For submodular maximization under a budget constraint \eqref{eq:non-strategic},
the greedy algorithm can be generalized: if $S\subset\mathcal{N}$ is the set
constructed thus far, the element $i$ to be included is the one which maximizes
the \emph{marginal-value-per-cost}:
\begin{align}
    i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy}
\end{align}
This is repeated until the sum of costs of elements in $S$ reaches the budget
constraint $B$. Unfortunately, the greedy algorithm alone has an unbounded
approximation ratio~\cite{khuller}.  However, let $i^*
= \argmax_{i\in\mathcal{N}} V(\{i\})$  be the element of maximum value, and
$S_G$ the set computed by the greedy algorithm, taking the maximum between
$V(S_G)$ and $V(i^*)$ yields a bounded approximation ratio. Formally, the
following lemma holds.
\begin{lemma}~\cite{chen}\label{lemma:greedy-bound}
Let $S_G$ be the set computed by the greedy algorithm 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}
This lemma immediately proves an approximation ratio of $\frac{5e}{e-1}$ for
the afore-mentioned approach. A more sophisticated
algorithm~\cite{sviridenko-submodular} can attain the optimal $\frac{e}{e-1}$
approximation ratio

\fussy
\paragraph{Strategic case}
We could design the allocation function of our mechanism by following the full
information approach: allocating to agent $i^*$ when $V(i^*)\geq V(S_G)$ and to
$S_G$ otherwise. However, Singer~\cite{singer-influence} notes that this
allocation function is not monotonous, and thus breaks incentive compatibility
by Myerson's theorem (Theorem~\ref{thm:myerson}).

Let us denote by $OPT_{-i^*}$ the optimal value achievable in the
full-information case after removing $i^*$ from the set $\mathcal{N}$:
\begin{equation}
    OPT_{-i^*} \defeq \max_{S\subseteq\mathcal{N}\setminus\{i^*\}} \Big\{V(S) \;\Big| \;
    \sum_{i\in S}c_i\leq B\Big\}
\end{equation}
Singer~\cite{singer-mechanisms} and Chen \emph{et al.}~\cite{chen} prove that
allocating to $i^*$ when $V(i^*)\geq C.OPT_{-i^*}$ (for some constant $C$) and
to $S_G$ otherwise yields a 8.34-approximation mechanism. However,
$OPT_{-i^*}$, the solution of the full-information case, cannot be computed in
poly-time when the underlying problem is NP-hard (unless P=NP), as is the case
for \EDP{}.

Instead, Singer~\cite{singer-mechanisms} and Chen \emph{et al.}~\cite{chen}
suggest to replace $OPT_{-i^*}$ by a quantity $L^*$ satisfying the following
properties:
\begin{itemize}
    \item $L^*$ must not depend on agent $i^*$'s reported
    cost and must be monotonous: it can only increase when agents decrease
    their costs. This is to ensure the monotonicity of the allocation function.
    \item $L^*$ must be close to $OPT_{-i^*}$ to maintain a bounded
    approximation ratio.
    \item $L^*$ must be computable in polynomial time.
\end{itemize}

Such a quantity $L^*$ can be found by considering relaxations of the
optimization problem. A function $R:[0, 1]^{n}\to\reals_+$ defined on the
hypercube  $[0, 1]^{n}$ is a \emph{fractional relaxation} of $V$ over the set
$\mathcal{N}$ if $R(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$
denotes the indicator vector of $S$. The optimization program
\eqref{eq:non-strategic} extends naturally to such relaxations:
\begin{align}
    OPT' = \argmax_{\lambda\in[0, 1]^{n}}
    \left\{R(\lambda) \mid \sum_{i=1}^{n} \lambda_i c_i
    \leq B\right\}\label{relax}
\end{align}

In \cite{singer-mechanisms} and \cite{chen}, using $L^* = OPT'_{-i^*}$, when
$R$ is the \emph{multilinear extension} of $V$ (see
Section~\ref{sec:relaxation}) yields an constant-approximation mechanism for
\textsc{Knapsack}.

In \cite{singer-influence}, the optimization program \eqref{relax}
cannot be solved efficiently when $R$ is the multilinear extension of $V$.
Consequently, Singer introduces a second relaxation which he relates to the
multilinear extension through the \emph{pipage rounding} framework of Ageev and
Sviridenko~\cite{pipage}.

\paragraph{Our approach}
Following Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence},
we in turn introduce a relaxation $L$ specifically tailored to the value
function of \EDP:
\begin{displaymath}
\forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq
\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
\end{displaymath}
and then use $L^* = OPT'_{-i^*}$ with $R=L$ in our mechanism. The function $L$
is well-known to be concave and even self-concordant (see \emph{e.g.},
\cite{boyd2004convex}). In this case, the analysis of Newton's method for
self-concordant functions in \cite{boyd2004convex}, shows that finding the
maximum of $L$ to any precision $\varepsilon$ can be done in
$O(\log\log\varepsilon^{-1})$ iterations. Being the solution to a maximization
problem, $L^*$ satisfies the required monotonicity property. The main challenge
will be to prove that $OPT'_{-i^*}$, for the relaxation $R=L$, is close to
$OPT$. As in~\cite{singer-influence} this will be done by using the
\emph{pipage rounding} framework of~\cite{pipage} and forms the technical bulk
of the paper.

The resulting mechanism for \EDP{} is composed of
\begin{itemize}
\item
 the allocation function
presented in Algorithm~\ref{mechanism}, and 
\item
the payment function which pays each
allocated agent $i$ her threshold payment as described in Myerson's Theorem. 
%The constant $C$ is an absolute
%constant that determined in Section~\ref{sec:proofofmainthm}
%(see \eqref{eq:c}). 
 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 payment when $S_G$ is the allocated
set can be found in~\cite{singer-mechanisms}.
\end{itemize}

\begin{algorithm}[!t]
    \caption{Mechanism for \EDP{}}\label{mechanism}
    \begin{algorithmic}[1]
    \State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
    \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
    \State $\xi \gets \argmax_{\lambda\in[0,1]^{n}} \{L(\lambda)
                                    \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$
        \Statex
        \If{$L(\xi) < C \cdot V(i^*)$} \label{c}
            \State \textbf{return} $\{i^*\}$ 
        \Else
            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
            \State $S_G \gets \emptyset$
            \While{$c_i\leq \frac{B}{2}\frac{V(S_G\cup\{i\})-V(S_G)}{V(S_G\cup\{i\})}$}
                \State $S_G \gets S_G\cup\{i\}$
                \State $i \gets \argmax_{j\in\mathcal{N}\setminus S_G}
                \frac{V(S_G\cup\{j\})-V(S_G)}{c_j}$
            \EndWhile
            \State \textbf{return} $S_G$
        \EndIf
    \end{algorithmic}
\end{algorithm}
We can now state our main result:
\begin{theorem}\label{thm:main}
    \sloppy
    The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individually rational 
    and budget feasible. Furthermore, for any $\varepsilon>0$, the mechanism
  runs in time  $O\left(\text{poly}(n, d,
    \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
    \begin{align*}
        OPT
        & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
        \varepsilon\\
        & \simeq 12.98V(S^*) + \varepsilon
    \end{align*}
\end{theorem}

\fussy

%\stratis{Add lowerbound here too.}
%Note that this implies we construct a poly-time mechanism with accuracy arbitrarily close to 19.68, by taking $\varepsilon = \ldots$\stratis{fix me}.
In addition, we prove the following simple lower bound.
\begin{theorem}\label{thm:lowerbound}
There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. 
\end{theorem}
%\stratis{move the proof as appropriate}
\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}

\begin{comment}
$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
we select each element $i$ in $\mathcal{N}$  independently with probability
$\lambda_i$: %or to reject it with probability $1-\lambda_i$:
\begin{displaymath}
    P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i
    \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i)
\end{displaymath}
Consider  the general \emph{multi-linear}
extension:
\begin{equation}\label{eq:multilinear}
    F(\lambda) 
    = \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[V(S)\right]
    = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
\end{equation}
\junk{

$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
we select each element $i$ in $\mathcal{N}$  independently with probability
$\lambda_i$: %or to reject it with probability $1-\lambda_i$:
\begin{displaymath}
    P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i
    \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i)
\end{displaymath}

For \EDP\  the multi-linear extension 
%of \eqref{modified} 
can be written:
\begin{displaymath}
    F(\lambda) = \mathbb{E}_{S\sim
    P_\mathcal{N}^\lambda}\Big[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big].
\end{displaymath}
%As in the case of \textsc{Coverage}, 
\eqref{relax} is not a convex optimization problem, and is not easy to solve directly. %As in ~\cite{singer-influence},
We consider an additional relaxation $L$ that 
follows naturally by swapping the expectation and the $\log\det$
in the above formula:
\begin{align}\label{eq:concave}
    L(\lambda) & \defeq \log\det\Big(\mathbb{E}_{S\sim
    P_\mathcal{N}^\lambda}\big[I_d + \sum_{i\in S} x_i\T{x_i}\big]\Big)\notag \\
    &= \log\det\left(I_d + \sum_{i\in\mathcal{N}}
    \lambda_i x_i\T{x_i}\right)
\end{align}
\end{comment}
\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
%\stratis{individual rationality???}
%The proof of the properties of the mechanism is broken down into lemmas.

We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual
rationality follows from monotonicity and threshold payments.  Monotonicity and
budget feasibility follow the same steps as the analysis of Chen \emph{et al.} \cite{chen};
 for the sake of completeness, we restate their proof in the Appendix.
 Our proof of the approximation ratio uses a bound on our concave relaxation
$L$ (Lemma~\ref{lemma:relaxation}). This is our main technical
contribution; the proof of this lemma can be found in Section~\ref{sec:relaxation}.
\begin{lemma}\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}\label{lemma:relaxation}
    %\begin{displaymath}
     $   OPT' \leq 2 OPT
        + 2\max_{i\in\mathcal{N}}V(i)$
    %\end{displaymath}
\end{lemma}
The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.

\paragraph{Finishing Proof of Theorem~\ref{thm:main} }
Note that the lower bound $OPT' \geq  OPT
$ also holds trivially, as $L$ is a fractional relaxation of $V$ over $\mathcal{N}$.
Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm:main} by showing that, %\begin{lemma}\label{lemma:approx}
    %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C
    %(e-1) -10e  +2}\right)\right)
    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{align}
        OPT
         \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound}
    \end{align}
%\end{lemma}
    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,
    \begin{displaymath}
        OPT \leq OPT_{-i^*} + V(i^*)
    \end{displaymath}
    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{multline}\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{multline}
    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$.
    %which is needed in the above derivation. 
This solution is:
    \begin{align}
        C^* =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)} \label{eq:c}
    \end{align}
    For this solution,
 %   \begin{displaymath}
  $      \frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon. $
 %   \end{displaymath}
    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
%\end{proof}

\subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation}
%Recall that, since $L$ is a fractional relaxation of  $V$, 
%\begin{displaymath}
%    OPT \leq OPT(L, B).
%\end{displaymath}
%However, for the purpose of proving theorem~\ref{thm:main}, we need to bound
%$L$ from above (up to a multiplicative factor) by $V$. 

\junk{
To prove Lemma~\ref{lemma:relaxation}, we use the
\emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where
$L$ is first bounded from above by the multi-linear relaxation $F$, which is itself
subsequently bounded by $V$. While the latter part is general and can be applied
to the multi-linear extension of any submodular function, the former part is
specific to our choice for the function $L$.  %and is our main technical contribution (lemma~\ref{lemma:relaxation-ratio}).

The proof has two aspects. The easier part is that $F$ is bounded by $V$.
This is called  \emph{cross-convexity}  in the literature (see, \emph{e.g.},
\cite{dughmi}), or $\varepsilon$-convexity by Ageev and Sviridenko~\cite{pipage}. 
}

We prove that our multi-linear function $F$ has a property 
 which allows to trade one fractional component of the solution for another until
one of them becomes integral, without losing any value.
This property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.},
\cite{dughmi}), or $\varepsilon$-convexity by Ageev and
Sviridenko~\cite{pipage}.
\junk{

a variant of the $\varepsilon$-convexity of the multi-linear
extension \eqref{eq:multilinear} introduced by Ageev and Sviridenko
\cite{pipage} which allows to trade one fractional component of the solution for another until
one of them becomes integral, without loosing any value. This property is also
referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.},
\cite{dughmi}). 
}
Formally, %this property states that 
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.

The lemma below proves that we can similarly trade a fractional component for
another until one of them becomes integral \emph{while maintaining the
feasibility of the point at which $F$ is evaluated}. 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$.
\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 
    %\begin{displaymath}
     $   F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
    %\end{displaymath}
\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:
    \begin{displaymath}
        F(\lambda) \leq F(\lambda')
    \end{displaymath}
    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{multline}\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{multline}
    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{multline*}
        \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{multline*}
    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}

Next, we prove the central result of bounding $L$  appropriately in terms of $F$.

\junk{
To prove Lemma~\ref{lemma:relaxation}, we use the
\emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where
$L$ is first bounded from above by the multi-linear relaxation $F$, which is itself
subsequently bounded by $V$. While the latter part is general and can be applied
to the multi-linear extension of any submodular function, the former part is
specific to our choice for the function $L$.  %and is our main techn
}

\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{align*}
        \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{align*}
    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. In particular, 
  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:
    \begin{displaymath}
        \T{x_i}A(S)^{-1}x_i \leq \norm{x_i}_2^2 \leq 1 
    \end{displaymath}
    Moreover:
    \begin{displaymath}
        \forall x\leq 1,\; \log(1+x)\geq x
    \end{displaymath}
    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{align*}
        \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{align*}

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}

\paragraph{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}
    Using the submodularity of $V$:
    \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 2 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