path: root/main.tex

\label{sec:main}

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

\subsection*{Submodular maximization in the full-information case}

In the full-information case, submodular maximization under a budget constraint
\eqref{eq:non-strategic} relies on a greedy heuristic in which elements are
added to the solution set according to the following greedy selection rule.
Assume that $S\subseteq\mathcal{N}$ is the set constructed thus far, the next
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$. Denote by $S_G$ the set constructed by this heuristic and by
$i^* = \argmax_{i\in\mathcal{N}} V(\{i\})$, then 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 implies that the following algorithm:
\begin{equation}\label{eq:algorithm}
\textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
\;\textbf{else return}\; S_G
\end{equation}
has an approximation ratio of $\frac{5e}{e-1}$.

\subsection*{Submodular maximization in the strategic case}

In the strategic case, Algorithm~\ref{eq:algorithm} breaks incentive
compatibility. Indeed, \citeN{singer-influence} notes that this allocation
function is not monotone, which implies by Myerson's theorem
(Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful.

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}\label{eq:opt-reduced}
    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}
\citeN{singer-mechanisms} and \citeN{chen} prove that using the following
allocation:
\begin{displaymath}\label{eq:algorithm}
\textbf{if}\; V(\{i^*\}) \geq C. OPT_{-i^*}\; \textbf{return}\; \{i^*\}
\;\textbf{else return}\; S_G
\end{displaymath}
yields a 8.34-approximation mechanism for an appropriate $C$ (see also
Algorithm~\ref{mechanism}). However, $OPT_{-i^*}$, the maximum value attainable
in 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 \SEDP{}.

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

Such a quantity can be found by considering relaxations of the
optimization problem \eqref{eq:opt-reduced}. A function $L:[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 $L(\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\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
    \leq B\right\}\label{relax}
\end{align}

One of the main technical contribution of \citeN{chen} and
\citeN{singer-influence} is to come up with appropriate relaxations for
\textsc{Knapsack} and \textsc{Coverage} respectively.

\subsection*{Our approach}

\sloppy
We introduce a relaxation $L$ specifically tailored to the value function of
\SEDP:
\begin{equation}\label{eq:our-relaxation}
\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{equation}
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 our relaxation $L$, is close to $OPT$. 

\begin{algorithm}[t]
    \caption{Mechanism for \SEDP{}}\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 $OPT'_{-i^*} \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{$OPT'_{-i^*} < 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}

\fussy
In summary, 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.  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 payments when $S_G$ is the allocated set can
be found in~\cite{singer-mechanisms}.
\end{itemize}

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

\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}

We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual
rationality follow from monotonicity and threshold payments.  Monotonicity and
budget feasibility follow the same steps as the analysis of \citeN{chen};
 for the sake of completeness, we restate their proof in the Appendix.

The complexity of the mechanism is given by the following lemma.
\begin{lemma}[Complexity]\label{lemma:complexity}
    For any $\varepsilon > 0$, the complexity of the mechanism  is
    $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
\end{lemma}
\begin{proof}
    The value function $V$ in \eqref{modified} can be computed in time
    $O(\text{poly}(n, d))$ and the mechanism only involves a linear
    number of queries to the function $V$. 
    The function $\log\det$ is concave and self-concordant (see
    \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be found
    to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$  of iterations of Newton's method. Each iteration  can be
    done in time $O(\text{poly}(n, d))$. Thus, line 3 of
    Algorithm~\ref{mechanism} can be computed in time
    $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. Hence the allocation
    function's complexity is as stated. 
    %Payments can be easily computed in time  $O(\text{poly}(n, d))$ as in prior work.
\junk{
    Using Singer's characterization of the threshold payments
    \cite{singer-mechanisms}, one can verify that they can be computed in time
    $O(\text{poly}(n, d))$.
    }
\end{proof}

Finally, we prove the approximation ratio of the mechanism. We use the
following lemma  which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints
 is not too far from $OPT$.  
\begin{lemma}[Approximation]\label{lemma:relaxation}
     $   OPT' \leq 2 OPT
        + 2\max_{i\in\mathcal{N}}V(i)$
\end{lemma}
The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.

Using Lemma~\ref{lemma:relaxation} we can complete the proof of
Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if
$OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from
$\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set
$S^*$ allocated by the mechanism is such that:
\begin{equation} \label{approxbound}
OPT
\leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!
+ \! \varepsilon 
\end{equation}
To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to
$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume
that on line 3 of algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that
$\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been
computed (Lemma~\ref{lemma:complexity} states that this  is computed in time
within our complexity guarantee).  If the condition on line 3 of the algorithm
holds, then:
\begin{displaymath}
    V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq
    \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C} 
\end{displaymath}
as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$,
hence:
\begin{equation}\label{eq:bound1}
    OPT\leq (1+C)V(i^*) + \varepsilon
\end{equation}
Note that $OPT_{-i^*}'\leq OPT'$. If the condition  does not hold, from Lemmas
\ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
\begin{align*}
    V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
    \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
    & \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
    + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}
\end{align*}
Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
\begin{align*}
    V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) 
    + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}
\end{align*}
Finally, using again Lemma~\ref{lemma:greedy-bound}, we get:
\begin{equation}\label{eq:bound2}
    OPT(V, \mathcal{N}, B) \leq 
    \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}\right) V(S_G)
    + \frac{2e\varepsilon}{C(e-1)- 6e + 2}
\end{equation}
To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1}
and \eqref{eq:bound2} respectively, we wish to chose for $C=C^*$ such that:
\begin{displaymath}
    C^* = \argmin_C 
    \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}
            \right)\right)
\end{displaymath}
This equation has two solutions. Only one of those is such that $C(e-1) -6e
+2 \geq 0$. This solution is:
\begin{displaymath}
    C^* =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)} \label{eq:c}
\end{displaymath}
For this solution, $\frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon.$
Placing the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2}
gives the approximation ratio in \eqref{approxbound}, and concludes the proof
of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed

\subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation}

We need to prove that for our relaxation $L$ given by
\eqref{eq:our-relaxation}, $OPT'$ is close to $OPT$ as stated in
Lemma~\ref{lemma:relaxation}. Our analysis follows the \emph{pipage rounding}
framework of \citeN{pipage}.

This framework uses the \emph{multi-linear} extension $F$ of the submodular
function $V$. Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the set $S$ if we select each element $i$ in $\mathcal{N}$ independently with probability $\lambda_i$:
\begin{displaymath}
    P_\mathcal{N}^\lambda(S) \defeq \prod_{i\in S} \lambda_i
    \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i).
\end{displaymath}
Then, the \emph{multi-linear} extension $F$ is defined by:
\begin{displaymath}
    F(\lambda) 
    \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big]
    = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
\end{displaymath}

For \EDP{}  the multi-linear extension can be written:
\begin{equation}\label{eq:multi-linear-logdet}
    F(\lambda) = \mathbb{E}_{S\sim
    P_\mathcal{N}^\lambda}\bigg[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big].
\end{equation}
Note that the relaxation $L$ that we introduced in \eqref{eq:our-relaxation},
follows naturally from the \emph{multi-linear} relaxation by swapping the
expectation and the $\log\det$ in \eqref{eq:multi-linear-logdet}:
\begin{displaymath}
    L(\lambda) = \log\det\left(\mathbb{E}_{S\sim
    P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right).
\end{displaymath}

The proof proceeds as follows:
\begin{itemize}
\item First, we prove that $F$ admits the following rounding property: let
$\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one
fractional component of $\lambda$ for another until one of them becomes
integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and
for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point
$\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n
\lambda_i c_i \leq B$.  This rounding property is referred to in the literature
as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or
$\varepsilon$-convexity by \citeN{pipage}. This is stated and proven in
Lemma~\ref{lemma:rounding} and allows us to bound $F$ in terms of $OPT$.
\item Next, we prove the central result of bounding $L$  appropriately in terms
of the multi-linear relaxation $F$ (Lemma \ref{lemma:relaxation-ratio}).
\item Finally, we conclude the proof of Lemma~\ref{lemma:relaxation} by
combining Lemma~\ref{lemma:rounding} and Lemma~\ref{lemma:relaxation-ratio}.
\end{itemize}

\begin{comment}
Formally, if we define:
\begin{displaymath}
    \tilde{F}_\lambda(\varepsilon) \defeq F\big(\lambda + \varepsilon(e_i
    - e_j)\big)
\end{displaymath}
where $e_i$ and $e_j$ are two vectors of the standard basis of
$\reals^{n}$, then $\tilde{F}_\lambda$ is convex. Hence its maximum over the interval:
\begin{displaymath}
 I_\lambda = \Big[\max(-\lambda_i,\lambda_j-1), \min(1-\lambda_i, \lambda_j)\Big]
\end{displaymath}
is attained at one of the boundaries of $I_\lambda$ for which one of the $i$-th
or the $j$-th component of $\lambda$ becomes integral.
\end{comment}

\begin{lemma}[Rounding]\label{lemma:rounding}
    For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible
    $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is
    fractional %, that is, lies in $(0,1)$ and:
     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
\end{lemma}
\begin{proof}
    We give a rounding procedure which, given a feasible $\lambda$ with at least
    two fractional components, returns some feasible $\lambda'$ with one less fractional
    component such that $F(\lambda) \leq F(\lambda')$.

    Applying this procedure recursively yields the lemma's result.
    Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two
    fractional components of $\lambda$ and let us define the following
    function:
    \begin{displaymath}
        F_\lambda(\varepsilon) = F(\lambda_\varepsilon)
        \quad\textrm{where} \quad
        \lambda_\varepsilon = \lambda + \varepsilon\left(e_i-\frac{c_i}{c_j}e_j\right)
    \end{displaymath}
    It is easy to see that if $\lambda$ is feasible, then:
    \begin{equation}\label{eq:convex-interval}
        \forall\varepsilon\in\Big[\max\Big(-\lambda_i,(\lambda_j-1)\frac{c_j}{c_i}\Big), \min\Big(1-\lambda_i, \lambda_j
        \frac{c_j}{c_i}\Big)\Big],\;
            \lambda_\varepsilon\;\;\textrm{is feasible}
    \end{equation}
    Furthermore, the function $F_\lambda$ is convex; indeed:
    \begin{align*}
        F_\lambda(\varepsilon)
        & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
        (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\
        & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})
         + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\
         & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big]
    \end{align*}
    Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is:
    \begin{displaymath}
        \frac{c_i}{c_j}\mathbb{E}_{S'\sim
        P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[
            V(S'\cup\{i\})+V(S'\cup\{i\})\\
        -V(S'\cup\{i,j\})-V(S')\Big]
    \end{displaymath}
    which is positive by submodularity of $V$. Hence, the maximum of
    $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is
    attained at one of its limit, at which either the $i$-th or $j$-th component of
    $\lambda_\varepsilon$ becomes integral.
\end{proof}


\begin{lemma}\label{lemma:relaxation-ratio}
 %   The following inequality holds:
For all $\lambda\in[0,1]^{n},$
    %\begin{displaymath}
     $           \frac{1}{2}
        \,L(\lambda)\leq
        F(\lambda)\leq L(\lambda)$.
    %\end{displaymath}
\end{lemma}
\begin{proof}
    The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}(\lambda)}$ follows by the concavity of the $\log\det$ function.
    To show the lower bound, 
    we first prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
    F(\lambda)/\partial_i L(\lambda)$, where
    $\partial_i\, \cdot$ denotes the partial derivative with respect to the
    $i$-th variable.  

   Let us start by computing the derivatives of $F$ and
    $L$ with respect to the $i$-th component.
    Observe that:
    \begin{displaymath}
        \partial_i P_\mathcal{N}^\lambda(S) = \left\{
            \begin{aligned}
                & P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})\;\textrm{if}\; i\in S \\
                & - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\;\textrm{if}\;
                i\in \mathcal{N}\setminus S \\
            \end{aligned}\right.
    \end{displaymath}
    Hence:
    \begin{displaymath}
        \partial_i F(\lambda) =
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S)
        - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)
    \end{displaymath}
    Now, using that every $S$ such that $i\in S$ can be uniquely written as
    $S'\cup\{i\}$, we can write:
    \begin{displaymath}
        \partial_i F(\lambda) =
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\big(V(S\cup\{i\})
        - V(S)\big)
    \end{displaymath}
    The marginal contribution of $i$ to
    $S$ can be written as 
\begin{align*}
V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(I_d 
    + \T{X_S}X_S + x_i\T{x_i})
    - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\\
    &  = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d +
\T{X_S}X_S)^{-1})
 = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)
\end{align*}
where $A(S) =I_d+ \T{X_S}X_S$. 
%  $  V(S\cup\{i\}) - V(S) = \frac{1}{2}\log\left(1 +  \T{x_i} A(S)^{-1}x_i\right)$.
Using this,
    \begin{displaymath}
        \partial_i F(\lambda) = \frac{1}{2}
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
    \end{displaymath}
     The computation of the derivative of $L$ uses standard matrix
    calculus. Writing $\tilde{A}(\lambda) = I_d+\sum_{i\in
    \mathcal{N}}\lambda_ix_i\T{x_i}$:
    \begin{displaymath}
        \det \tilde{A}(\lambda + h\cdot e_i) = \det\big(\tilde{A}(\lambda)
        + hx_i\T{x_i}\big)
         =\det \tilde{A}(\lambda)\big(1+
        h\T{x_i}\tilde{A}(\lambda)^{-1}x_i\big)
    \end{displaymath}
    Hence:
    \begin{displaymath}
       \log\det\tilde{A}(\lambda + h\cdot e_i)= \log\det\tilde{A}(\lambda)
        + h\T{x_i}\tilde{A}(\lambda)^{-1}x_i + o(h)
    \end{displaymath}
    Finally:
    \begin{displaymath}
        \partial_i L(\lambda)
        =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i
    \end{displaymath}

For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if
$A-B$ is positive definite (positive semi-definite).  This order allows us to
define the notion of a \emph{decreasing} as well as  \emph{convex} matrix
function, similarly to their real counterparts. With this definition, matrix
inversion is decreasing and convex over symmetric positive definite matrices.
In particular,
\begin{gather*}
        \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}
\end{gather*}
 Observe that:
    \begin{gather*}
        \forall S\subseteq\mathcal{N}\setminus\{i\},\quad
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})\\
        \forall S\subseteq\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) 
        \geq P_\mathcal{N}^\lambda(S)
    \end{gather*}
    Hence:
    \begin{align*}
        \partial_i F(\lambda) 
      %  & = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_\mathcal{N}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
        & \geq \frac{1}{4}
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
        &\hspace{-3.5em}+\frac{1}{4}
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})
        \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
        &\geq \frac{1}{4}
        \sum_{S\subseteq\mathcal{N}}
        P_\mathcal{N}^\lambda(S)
        \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
    \end{align*}
    Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq
    \norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$.
    Hence:
    \begin{displaymath}
        \partial_i F(\lambda) \geq
        \frac{1}{4}
        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)^{-1}\bigg)x_i
    \end{displaymath}
    Finally, using that the inverse is a matrix convex function over symmetric
    positive definite matrices:
    \begin{displaymath}
        \partial_i F(\lambda) \geq
        \frac{1}{4}
        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i
        = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i
         = \frac{1}{2}
     \partial_i L(\lambda)
    \end{displaymath}

Having bound the ratio between the partial derivatives, we now bound the ratio $F(\lambda)/L(\lambda)$ from below. Consider the following cases.
    First, if the minimum of the ratio
    $F(\lambda)/L(\lambda)$ is attained at a point interior to the hypercube, then it is
    a critical point, \emph{i.e.}, $\partial_i \big(F(\lambda)/L(\lambda)\big)=0$ for all $i\in \mathcal{N}$; hence, at such a critical point:
    \begin{equation}\label{eq:lhopital}
        \frac{F(\lambda)}{L(\lambda)}
        = \frac{\partial_i F(\lambda)}{\partial_i
        L(\lambda)} \geq \frac{1}{2}
    \end{equation}
    Second, if the minimum is attained as 
    $\lambda$ converges to zero in, \emph{e.g.}, the $l_2$ norm, by the Taylor approximation, one can write:
    \begin{displaymath}
        \frac{F(\lambda)}{L(\lambda)}
        \sim_{\lambda\rightarrow 0}
        \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F(0)}
        {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L(0)}
        \geq \frac{1}{2},
    \end{displaymath}
    \emph{i.e.}, the ratio $\frac{F(\lambda)}{L(\lambda)}$ is necessarily bounded from below by 1/2 for small enough $\lambda$. 
       Finally, if the minimum is attained on a face of the hypercube $[0,1]^n$ (a face is
    defined as a subset of the hypercube where one of the variable is fixed to
    0 or 1), without loss of generality, we can assume that the minimum is
    attained on the face where the $n$-th variable has been fixed
    to 0 or 1. Then, either the minimum is attained at a point interior to the
    face or on a boundary of the face. In the first sub-case, relation
    \eqref{eq:lhopital} still characterizes the minimum for $i< n$.
    In the second sub-case, by repeating the argument again by induction, we see
    that all is left to do is to show that the bound holds for the vertices of
    the cube (the faces of dimension 1).  The vertices are exactly the binary
    points, for which we know that both relaxations are equal to the value
    function $V$. Hence, the ratio is equal to 1 on the vertices.
\end{proof}

\begin{proof}[of Lemma~\ref{lemma:relaxation}]
Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
    = OPT'$. By applying Lemma~\ref{lemma:relaxation-ratio}
    and Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
    one fractional component such that:
    \begin{equation}\label{eq:e1}
        L(\lambda^*) \leq 2
        F(\bar{\lambda})
    \end{equation}
    Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$
    denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$.
    By definition of the multi-linear extension $F$:
    \begin{displaymath}
        F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\})
    \end{displaymath}
    By submodularity of $V$, $V(S\cup\{i\})\leq V(S) + V(\{i\})$, hence:
    \begin{displaymath}
        F(\bar{\lambda}) \leq V(S) + V(i)
    \end{displaymath}
    Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
    $V(S)\leq OPT$. Hence:
    \begin{equation}\label{eq:e2}
        F(\bar{\lambda}) \leq  OPT
        + \max_{i\in\mathcal{N}} V(i)
    \end{equation}
    Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma. \hspace*{\stretch{1}}\qed
\end{proof}

\subsection{Proof of Theorem \ref{thm:lowerbound}}

\begin{proof}
Suppose, for contradiction, that such a mechanism exists. Consider two
experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$
and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must
be in the set selected by the mechanism, otherwise the ratio is unbounded,
a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity
it remains in the solution; by  threshold payment, it is paid at least
$B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility
and individual rationality: hence, the selected set attains a value $\log2$,
while the optimal value is $2\log 2$.
\end{proof}