\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 from \cite{chen} which bounds $OPT$ in terms of
the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the
element of maximum value.

\begin{lemma}[\cite{chen}]\label{lemma:greedy-bound}
Let $S_G$ be the set computed in Algorithm \ref{mechanism} 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}

Using Proposition~\ref{prop:relaxation} and~\ref{lemma:greedy-bound} 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}

If the condition  does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and
applying Proposition~\ref{prop:relaxation}, we get
\begin{displaymath}
    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}.
\end{displaymath}
Applying Lemma~\ref{lemma:greedy-bound},
\begin{displaymath}
    V(i^*) \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{displaymath}
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 Lemma~\ref{lemma:greedy-bound} again, 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 $C$ that minimizes
\begin{displaymath}
    \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}
            \right)\right).
\end{displaymath}
This function has two minima, only one of those is such that $C(e-1) -6e
+2 \geq 0$. This minimum is
\begin{equation}\label{eq:constant}
    C =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}.
\end{equation}
For this minimum, $\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 Theorem \ref{thm:lowerbound}}

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$.\hspace*{\stretch{1}}\qed