path: root/main.tex

\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 into looking at 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, points
are added to the solution set according to the following greedy selection rule:
assume that you have already selected a set $S$ of point, then the next point
to be selected 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 a point depends on the set of points which have already
been selected.

Unfortunately, even for the non-strategic case, the greedy heuristic gives an
unbounded approximation ratio. It has been noted by Khuller et al.
\cite{khuller} that for the maximum coverage problem, taking the maximum
between the greedy solution and the point of maximum value gives
a $\frac{2e}{e-1}$ approximation ratio. In the general case, let us recall
lemma 3.1 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 $i^*$ the point of
maximum value:
\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 the greedy set and the point of maximum value
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.

Two approaches have been studied to deal with the strategic case and rely on
comparing the point of maximum value to a quantity which can be proven to be
not too far from the greedy solution and maintains incentive compatibility.
\begin{itemize}
\item In \cite{chen}, the authors suggest using 
$OPT(V,\mathcal{N}\setminus\{i^*\}, B)$ where $i^*$ is the point of maximum
value. While this yields an approximation ratio of 8.34, in the general case,
the optimal value cannot be computed in polynomial time.
\item For the set coverage problem, Singer \cite{singer-influence} uses
a relaxation of the value function which can be proven to have a constant
approximation ratio to the value function.
\end{itemize}

Here, we will use the following relaxation of the value function \eqref{vs}.
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 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}
\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.
    \item the stopping rule in the while loop is more sophisticated than just
        checking against the budget constraint ($c(S) \leq B$). This is to
        ensure budget feasibility (see lemma~\ref{lemma:budget-feasibility}).
\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}

\begin{proof}
\emph{Truthfulness.} The algorithm only describes the allocation rule.
However, it suffices to prove that the mechanism is monotone, then Myerson's
theorem (see theorem~\ref{thm:myerson}) ensures us that by paying each
allocated user his threshold payment yields a truthful mechanism. The proof of
the monotonicity has already been done in \cite{singer-influence} and is given
here in lemma~\ref{lemma:monotone} below for the sake of completeness.

\emph{Budget feasibility.} Thanks to the analysis of the threshold
payment in \cite{chen}, the budget feasibility follows easily. The
proof is given in lemma~\ref{lemma:budget-feasibility} below. 

\emph{Approximation ratio.} The proof of the approximation ratio follows the
same path as in \cite{chen} and is done in lemma~\ref{lemma:approx}. Our main
contribution is to prove that the relaxation $L_\mathcal{N}$ has a constant
approximation ratio to the optimal solution (lemma~\ref{lemma:relaxation}). This
follows from the \emph{pipage rounding} method described in \cite{pipage} where
$L_\mathcal{N}$ is first compared to the \emph{multilinear relaxation} of the
value function (lemma~\ref{lemma:relaxation-ratio}) for which it is possible to
round solutions (making fractional components integral) while maintaining
feasibility (lemma~\ref{lemma:rounding}).
\end{proof}

\begin{lemma}\label{lemma:monotone}
The mechanism is monotone.
\end{lemma}

\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.
\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}

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}.

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!}.
\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. 

\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)$.

    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}
    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}