\subsection{D-Optimality Criterion}
Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes \eqref{dcrit} within a good approximation ratio. As \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation we consider  the (equivalent) maximization of $V(S) = f(\det\T{X_S}X_S )$, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. However, the following lower bound implies that such an optimization goal cannot be attained under the costraints of  truthfulness, budget feasibility, and individional rationallity.

\begin{lemma}
For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individionally rational mechanism for budget feasible experiment design with value fuction $V(S) = \det{\T{X_S}X_S}$.
\end{lemma}
\begin{proof}
\input{proof_of_lower_bound1}
\end{proof}

This negative result motivates us to study the following modified objective:
\begin{align}V(S) = \log\det(I_d+\T{X_S}X_S), \label{modified}\end{align} where $I_d\in \reals^{d\times d}$ is the identity matrix.
One possible interpretation of \eqref{modified} is that, prior to the auction, the experimenter has free access to $d$ experiments whose features form an ortho-normal basis in $\reals^d$. However, \eqref{modified} can also be motivated in the context of \emph{Bayesian experimental design} \cite{chaloner1995bayesian}. In short, the objective \eqref{modified} arises naturally when the experimenter retrieves the model $\beta$ through \emph{ridge regression}, rather than the linear regression \eqref{leastsquares} over the observed data; we explore this connection in Section~\ref{sec:bed}. From a practical standpoint, \eqref{modified} is a good approximation of \eqref{dcrit} when the number of experiments is large. Crucially, \eqref{modified} is submodular and satifies $V(\emptyset) = 0$, allowing us to use the extensive machinery for the optimization of submodular functions, as well as recent results in the context of budget feasible auctions. 

\subsection{Truthful, Constant Approximation Mechanism}

In this section we present a mechanism for \EDP. Previous works on maximizing
submodular functions \cite{nemhauser, sviridenko-submodular} and designing
auction mechanisms for submodular utility functions \cite{singer-mechanisms,
chen, singer-influence} rely on a greedy heuristic. In this heuristic, elements
are added to the solution set according to the following greedy selection rule:
assume that you have already selected a set $S$, then the next element to be
included in the solution set is:
\begin{displaymath}
    i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}
\end{displaymath}
This is the generalization of the \emph{value-per-cost} ratio used in greedy
heuristic for knapsack  problems. However, note that for general submodular
functions, the value of an element depends on the set to which it is added.

Unfortunately, even for the non-strategic case, the greedy heuristic gives an
unbounded approximation ratio. Let us introduce $i^*
= \argmax_{i\in\mathcal{N}} V(i)$, the element of maximum value (as a singleton
set). It has been noted by Khuller et al. \cite{khuller} that for the maximum
coverage problem, taking the maximum between the greedy solution and $V(i^*$)
gives a $\frac{2e}{e-1}$ approximation ratio. In the general case, we have the
following result from \cite{singer-influence} which follows from \cite{chen}:

\begin{lemma}[Singer \cite{singer-influence}]\label{lemma:greedy-bound}
Let $S_G$ be the set computed by the greedy heuristic and let us define $i^*$:
\begin{displaymath}
    i^* = \argmax_{i\in\mathcal{N}} V(i)
\end{displaymath}
then the following inequality holds:
\begin{displaymath}
OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big)
\end{displaymath}
\end{lemma}

Hence, taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that
this approach breaks incentive compatibility and therefore cannot be directly
applied to the strategic case. Indeed, assume that we are in a situation where
the mechanism has allocated to the greedy set ($V(S_G) \geq V(i^*)$). If an
agent $i$ from the greedy set reduces her cost, it could happen that $V(S_G)$
becomes smaller than $V(i^*)$. In this case the mechanism will allocate to
$i^*$ and $i$ will be out of the allocated set. This breaks the monotonicity of
the allocation rule.

To address this issue, \cite{chen, singer-influence} compare $V(i^*)$ to
a quantity which can be proven to be close from $V(S_G)$ while keeping
keeping monotonicity. In \cite{chen}, the authors suggest comparing $V(i^*)$ to
$OPT(V,\mathcal{N}\setminus\{i^*\}, B)$. While this yields an approximation
ratio of 8.34, in the general case, this quantity cannot be computed in
polynomial time. In \cite{chen, singer-influence}, for the specific problems of
maximum set coverage and knapsack, the authors compare $V(i^*)$ to
a  fractional relaxation of the optimization program \eqref{eq:non-strategic}.

Here, following the same path as in \cite{chen, singer-influence}, we choose to
introduce the following relaxation of the  value function.  Let us define the
function $L_\mathcal{N}$:
\begin{displaymath}
    \forall\lambda\in[0,1]^{|\mathcal{N}|}\,\quad L_{\mathcal{N}}(\lambda) \defeq
    \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i \T{x_i}\right)
\end{displaymath}
Our mechanism will thus consist in comparing $V(i^*)$ to $OPT(L_\mathcal{N},
B)$ to decide whether we should allocate to $i^*$ or the greedy set $S_G$. The
main challenge will be to prove that $OPT(L_\mathcal{N}, B)$ is close to
$V(S_G)$. To do so, our main technical contribution is to prove that
$L_\mathcal{N}$ has a bounded approximation ratio to the value function $V$
(lemma~\ref{lemma:relaxation}).

The mechanism for \EDP{} is presented in algorithm \ref{mechanism}.
\begin{algorithm}
    \caption{Mechanism for \EDP{}}\label{mechanism}
    \begin{algorithmic}[1]
    \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
    \State $x^* \gets \argmax_{x\in[0,1]^{|\mathcal{N}|}} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
                                    \mid c(x)\leq B\}$
        \Statex
        \If{$L(x^*) < CV(i^*)$}
            \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}

\emph{Remarks} \stratis{write prose.}
\begin{enumerate}
    \item the function $L_\mathcal{N}$ is concave (see
        lemma~\ref{lemma:concave}) thus the maximization step on line 2 of the
        mechanism can be computed in polynomial time, which proves that the
        mechanism overall has a polynomial complexity. \stratis{citation on complexity? are there approximation issues? Also, concavity is well known, cite as approriately.}
    \item the stopping rule in the while loop is more sophisticated  \stratis{informal} than just
        checking against the budget constraint ($c(S) \leq B$). This is to
        ensure budget feasibility (see lemma~\ref{lemma:budget-feasibility}). \stratis{what is $c(S)$?}
\end{enumerate}

We can now state the main result of this section:
\begin{theorem}\label{thm:main}
    The mechanism described in Algorithm~\ref{mechanism} is truthful,
    individually rational and budget feasible. Furthermore, choosing:
    \begin{displaymath}
        C = C^* =  \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)}
    \end{displaymath}
    we get an approximation ratio of:
    \begin{displaymath}
        1 + C^* = \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)}\simeq 18.68
    \end{displaymath}
\end{theorem}

\stratis{Add lowerbound here too. Remove ``pseudo proof'' below. Start new subsection called proof of Thm... }


\subsection{Proof of theorem~\ref{thm:main}}

\stratis{Explain what are the main steps in the proof}
\begin{lemma}\label{lemma:monotone}
The mechanism is monotone.
\end{lemma}


\stratis{We assume by contradiction->Suppose, for contradiction}
\begin{proof}
    We assume by contradiction that there exists a user $i$ that has been
    selected by the mechanism and that would not be selected had he reported
    a cost $c_i'\leq c_i$ (all the other costs staying the same).

    If $i\neq i^*$ and $i$ has been selected, then we are in the case where
    $L(x^*) \geq C V(i^*)$ and $i$ was included in the result set by the greedy
    part of the mechanism. By reporting a cost $c_i'\leq c_i$, using the
    submodularity of $V$, we see that $i$ will satisfy the greedy selection
    rule:
    \begin{displaymath}
        i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\})
        - V(S)}{c_j}
    \end{displaymath}
    in an earlier iteration of the greedy heuristic. Let us denote by $S_i$
    (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$
    (resp. $c_i'$). We have $S_i'\subseteq S_i$. Moreover:
    \begin{align*}
        c_i' & \leq c_i \leq
        \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})}\\
        & \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})}
    \end{align*}
    Hence $i$ will still be included in the result set.

    If $i = i^*$, $i$ is included iff $L(x^*) \leq C V(i^*)$. Reporting $c_i'$
    instead of $c_i$ does not change the value $V(i^*)$ nor $L(x^*)$ (which is
    computed over $\mathcal{N}\setminus\{i^*\}$). Thus $i$ is still included by
    reporting a different cost. \stratis{$L$ lost its subscript}
\end{proof}

\begin{lemma}\label{lemma:budget-feasibility}
The mechanism is budget feasible.
\end{lemma}

\begin{proof}
Let us denote by $S_G$ the set selected by the greedy heuristic in the
mechanism of Algorithm~\ref{mechanism}. Let $i\in S_G$, let us also denote by
$S_i$ the solution set that was selected by the greedy heuristic before $i$ was
added. Recall from \cite{chen} that the following holds for any submodular
function: if the point $i$ was selected by the greedy heuristic, then:
\begin{equation}\label{eq:budget}
    c_i \leq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B
\end{equation}

\stratis{Use ``recall'' only for  something the reader is likely to know. }

Assume now that our mechanism selects point $i^*$. In this case, his payment
his $B$ and the mechanism is budget-feasible.

Otherwise, the mechanism selects the set $S_G$. In this case, \eqref{eq:budget}
shows that the threshold payment of user $i$ is bounded by:
\begin{displaymath}
\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B
\end{displaymath}

Hence, the total payment is bounded by:
\begin{displaymath}
    \sum_{i\in S_M} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B \leq B
\end{displaymath}
\end{proof}

\begin{lemma}\label{lemma:approx}
    Let $S^*$ be the set allocated by the mechanism. Let us write:
    \begin{displaymath}
        C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C
        (e-1) -10e  +2}\right)\right)
    \end{displaymath}

    Then:
    \begin{displaymath}
        OPT(V, \mathcal{N}, B) \leq
        C_\text{max}\cdot V(S^*) 
    \end{displaymath}
\end{lemma}

\begin{proof}

    If the condition on line 3 of the algorithm holds, then:
    \begin{displaymath}
        V(i^*) \geq \frac{1}{C}L(x^*) \geq
        \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B)
    \end{displaymath}

    But:
    \begin{displaymath}
        OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i\}, B) + V(i^*)
    \end{displaymath}

    Hence:
    \begin{displaymath}
        V(i^*) \geq \frac{1}{C+1} OPT(V,\mathcal{N}, B)
    \end{displaymath}

    If the condition of the algorithm does not hold, by applying lemmas
    \ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
    \begin{align*}
        V(i^*) & \leq \frac{1}{C}L(x^*) \leq \frac{1}{C}
        \big(4 OPT(V,\mathcal{N}, B) + 2 V(i^*)\big)\\
        & \leq \frac{1}{C}\left(\frac{4e}{e-1}\big(3 V(S_G)
        + 2 V(i^*)\big)
        + V(i^*)\right)
    \end{align*}
    
    Thus:
    \begin{align*}
        V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G)
    \end{align*}

    Finally, using again lemma~\ref{lemma:greedy-bound}, we get:
    \begin{displaymath}
        OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{8e}{C
        (e-1) -10e  +2}\right) V(S_G)\qed
    \end{displaymath}
\end{proof}

The optimal value for $C$ is:
\begin{displaymath}
    C^* = \argmin_C C_{\textrm{max}}
\end{displaymath}

This equation has two solutions. Only one of those is such that:
\begin{displaymath}
    C(e-1) -10e  +2 \geq 0
\end{displaymath}
which is needed in the proof of the previous lemma. Computing this solution,
gives the result of the theorem.

\subsection{An approximation ratio for $L_\mathcal{N}$}\label{sec:relaxation}

Our main contribution is lemma~\ref{lemma:relaxation} which gives an
approximation ratio for $L_\mathcal{N}$ and is key in the proof of
theorem~\ref{thm:main}.


\stratis{Given that the relaxation is the major contribution, and it plays a crucial role in your design, you might want to bring a lot of this before the statement of the theorem. Explain how both chen and singer use two relaxations to sandwitch the optimum. How this is motivated by the work by sviridenko. And, finallly, that you bring in this function that has a natural interpretation as the log det of the expectation.}

We say that $R_\mathcal{N}:[0,1]^{|\mathcal{N}|}\rightarrow\reals$ is
a relaxation of the value function $V$ over $\mathcal{N}$ if it coincides with
$V$ at binary points. Formally, for any $S\subseteq\mathcal{N}$, let
$\mathbf{1}_S$ denote the indicator vector of $S$. $R_\mathcal{N}$ is
a relaxation of $V$ over $\mathcal{N}$ iff:
\begin{displaymath}
    \forall S\subseteq\mathcal{N},\; R_\mathcal{N}(\mathbf{1}_S) = V(S)
\end{displaymath}

We can extend the optimisation problem defined above to a relaxation by
extending the cost function:
\begin{displaymath}
    \forall \lambda\in[0,1]^{|\mathcal{N}|},\; c(\lambda)
    = \sum_{i\in\mathcal{N}}\lambda_ic_i
\end{displaymath}
The optimisation problem becomes:
\begin{displaymath}
    OPT(R_\mathcal{N}, B) =
    \max_{\lambda\in[0,1]^{|\mathcal{N}|}}\left\{R_\mathcal{N}(\lambda)\,|\, c(\lambda)\leq B\right\}
\end{displaymath}

The relaxations we will consider here rely on defining a probability
distribution over subsets of $\mathcal{N}$.

Let $\lambda\in[0,1]^{|\mathcal{N}|}$, let us define:
\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}
$P_\mathcal{N}^\lambda(S)$ is the probability of picking the set $S$ if we select
a subset of $\mathcal{N}$ at random by deciding independently for each point to
include it in the set with probability $\lambda_i$ (and to exclude it with
probability $1-\lambda_i$).

For readability, let us define $A(S) = I_d + \T{X_S}X_S$, so that the value
function is $V(S) = \log\det A(S)$.

We have already defined the function $L_\mathcal{N}$ which is a relaxation of
the value function. Note that it is possible to express it in terms of the
probabilities $P_\mathcal{N}$:
\begin{align*}
    L_{\mathcal{N}}(\lambda) 
    & = \log\det \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[A(S)\big]\\
    & = \log\det\left(\sum_{S\subseteq N}
        P_\mathcal{N}^\lambda(S)A(S)\right)\\
    & = \log\det\left(I_d + \sum_{i\in\mathcal{N}}
        \lambda_ix_i\T{x_i}\right)\\
    & \defeq \log\det \tilde{A}(\lambda)
\end{align*}

We will also use the \emph{multi-linear extension}:
\begin{align*}
    F_\mathcal{N}(\lambda) 
    & = \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[\log\det A(S)\big]\\
    & = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)\\
    & = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) \log\det A(S)\\
\end{align*}

\begin{lemma}\label{lemma:concave}
    The \emph{concave relaxation} $L_\mathcal{N}$ is concave\footnote{Hence
    this relaxation is well-named!
\stratis{avoid humor}}.
\end{lemma}

\begin{proof}
    This follows from the concavity of the $\log\det$ function over symmetric
    positive semi-definite matrices. More precisely, if $A$ and $B$ are two
    symmetric positive semi-definite matrices, then:
    \begin{multline*}
        \forall\alpha\in [0, 1],\; \log\det\big(\alpha A + (1-\alpha) B\big)\\
        \geq \alpha\log\det A + (1-\alpha)\log\det B
    \end{multline*}
\end{proof}

It has been observed already (see for example \cite{dughmi}) that the
multi-linear extension presents the cross-convexity property: it is convex along
any direction $e_i-e_j$ where $e_i$ and $e_j$ are two elements of the standard
basis. This property allows to trade between two fractional components of
a point without diminishing the value of the relaxation. The following lemma
follows is inspired by a similar lemma from \cite{dughmi} but also ensures that
the points remain feasible during the trade. 

\stratis{explain how the proof below relates to the $\epsilon$-convexity of sviridenko}
\begin{lemma}[Rounding]\label{lemma:rounding}
    For any feasible $\lambda\in[0,1]^{|\mathcal{N}|}$, there exists a feasible
    $\bar{\lambda}\in[0,1]^{|\mathcal{N}|}$ such that at most one of its component is
    fractional, that is, lies in $(0,1)$ 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 $\lambda'$ with one less fractional
    component, feasible such that:
    \begin{displaymath}
        F_\mathcal{N}(\lambda) \leq F_\mathcal{N}(\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}

\begin{lemma}\label{lemma:relaxation-ratio}
    The following inequality holds:
    \begin{displaymath}
        \forall\lambda\in[0,1]^{|\mathcal{N}|},\; 
        \frac{1}{2}
        \,L_\mathcal{N}(\lambda)\leq
        F_\mathcal{N}(\lambda)\leq L_{\mathcal{N}}(\lambda)
    \end{displaymath}
\end{lemma}

\begin{proof}

    We will prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
    F_\mathcal{N}(\lambda)/\partial_i L_\mathcal{N}(\lambda)$.

    \stratis{what is $\partial_i?$}. 

    This will be enough to conclude, by observing that:
    \begin{displaymath}
        \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
        \sim_{\lambda\rightarrow 0}
        \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F_\mathcal{N}(0)}
        {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L_\mathcal{N}(0)}
    \end{displaymath}
    \stratis{what about other boundaries?}
   and that an interior critical point of the ratio
    $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$ is characterized by:
    \begin{displaymath}
        \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
        = \frac{\partial_i F_\mathcal{N}(\lambda)}{\partial_i
        L_\mathcal{N}(\lambda)}
    \end{displaymath}


    Let us start by computing the derivatives of $F_\mathcal{N}$ and
    $L_\mathcal{N}$ with respect to
    the $i$-th component.

    For $F$, it suffices to look at the derivative of
    $P_\mathcal{N}^\lambda(S)$:
    \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{multline*}
        \partial_i F_\mathcal{N} =
        \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{multline*}

    Now, using that every $S$ such that $i\in S$ can be uniquely written as
    $S'\cup\{i\}$, we can write:
    \begin{multline*}
        \partial_i F_\mathcal{N} =
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S\cup\{i\})\\
        - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)\\
    \end{multline*}

    Finally, by using the expression for the marginal contribution of $i$ to
    $S$:
    \begin{displaymath}
        \partial_i F_\mathcal{N}(\lambda) = 
        \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_\mathcal{N}$ uses standard matrix
    calculus and gives:
    \begin{displaymath}
        \partial_i L_\mathcal{N}(\lambda)
        = \T{x_i}\tilde{A}(\lambda)^{-1}x_i
    \end{displaymath}
    
    Using the following inequalities:
    \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)\\
        \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \geq A(S\cup\{i\})^{-1}\\
    \end{gather*}
    we get:
    \begin{align*}
        \partial_i F_\mathcal{N}(\lambda) 
        & \geq \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}{2}
        \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)\\
        &\hspace{-3.5em}+\frac{1}{2}
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
        P_\mathcal{N}^\lambda(S\cup\{i\})
        \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
        &\geq \frac{1}{2}
        \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)\geq I_d$ we get that:
    \begin{displaymath}
        \T{x_i}A(S)^{-1}x_i \leq 1 
    \end{displaymath}
    
    Moreover:
    \begin{displaymath}
        \forall x\leq 1,\; \log(1+x)\geq x
    \end{displaymath}

    Hence:
    \begin{displaymath}
        \partial_i F_\mathcal{N}(\lambda) \geq
        \frac{1}{2}
        \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_\mathcal{N}(\lambda) &\geq
        \frac{1}{2}
        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i\\
        & \geq \frac{1}{2}
        \partial_i L_\mathcal{N}(\lambda)\qed
    \end{align*}
\end{proof}

\begin{lemma}\label{lemma:relaxation}
    We have:
    \begin{displaymath}
        OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B)
        + 2\max_{i\in\mathcal{N}}V(i)
    \end{displaymath}
\end{lemma}

\begin{proof}
    Let us consider a feasible point $\lambda^*\in[0,1]^{|\mathcal{N}|}$ such that $L_\mathcal{N}(\lambda^*)
    = OPT(L_\mathcal{N}, B)$. 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_\mathcal{N}(\lambda^*) \leq 2
        F_\mathcal{N}(\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$.
    Using the fact that $F_\mathcal{N}$ is linear with respect to the $i$-th
    component and is a relaxation of the value function, we get:
    \begin{displaymath}
        F_\mathcal{N}(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\})
    \end{displaymath}

    Using the submodularity of $V$:
    \begin{displaymath}
        F_\mathcal{N}(\bar{\lambda}) \leq 2 V(S) + V(i)
    \end{displaymath}

    Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
    $V(S)\leq OPT(V,\mathcal{N}, B)$. Hence:
    \begin{equation}\label{eq:e2}
        F_\mathcal{N}(\bar{\lambda}) \leq 2 OPT(V,\mathcal{N}, B)
        + \max_{i\in\mathcal{N}} V(i)
    \end{equation}

    Putting \eqref{eq:e1} and \eqref{eq:e2} together gives the results.
\end{proof}