\label{sec:main}

The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} can be used to design a mechanism for \SEDP. The construction follows a methodology proposed in \cite{singer-mechanisms} and employed by \citeN{chen} and \citeN{singer-influence} to construct \junk{deterministic, truthful} mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. The following theorem summarizes the properties of our merchanism.


%In the strategic case, Algorithm~\eqref{eq:max-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.

\begin{theorem}\label{thm:main}\label{thm:lowerbound}
    For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$,  there exists a $\delta$-truthful, individually rational
    and budget feasible mechanim for \EDP{} that runs in time
    $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$
    and allocates
    a set $S^*$ such that
    \begin{displaymath}
        OPT
         \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
        \varepsilon
         \simeq 12.98V(S^*) + \varepsilon.
     \end{displaymath}
Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational
mechanism for EDP. 
\end{theorem}
The detailed description of our proposed mechanism (see Algorithm~\ref{mechanism}), as well as the proof of the theorem can be found in Appendix~\ref{sec:proofofmainthm}.