\label{sec:main}

In this section we present our mechanism for \SEDP, uses the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal}. The construction follows a methodology employed by \citeN{Chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively, which we first describe below.


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

Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen}  and by \citeN{singer-influence} for the \textsc{Knapsack}   and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone relaxation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this relaxation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$.

Provided that the relaxation used within a constant approximation of $OPT$, the above allocation can be shown to have a constant approximation. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and can be solved exactly in weakly polynomial time. The challenge in our setting is dealing with a convex relaxationsolved by an $\epsilon$-accurate, $\delta$-decreasing algorithm. In our setting, this yields a $\delta$-truthful, constant approximation mechanism. 

To obtain this result, we use the following modified version of Myerson's theorem, whose proof can be found in Appendix~\note{FIXME!!!}
%
%Instead, \citeN{singer-mechanisms} and \citeN{chen}
%suggest to approximate $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 decreasing with respect to the 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}
%
%One of the main technical contributions of \citeN{chen} and
%\citeN{singer-influence} is to come up with appropriate such quantity by
%considering relaxations of \textsc{Knapsack} and \textsc{Coverage},
%respectively.
%
%\subsection{Our Approach}
%
%Using the results from Section~\ref{sec:approximation}, we come up with
%a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being
%$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
%defined below.
%
%\begin{definition}
%Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator
%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
%$\delta$-truthful iff:
%\begin{displaymath}
%\forall c\in\reals_+^n,\;
%\forall\mu\;\text{with}\; |\mu|\geq\delta,\;
%\forall i\in\{1,\ldots,n\},\;
%p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
%\end{displaymath}
%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
%\end{definition}
%
%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
%by more than $\delta$ about their reported costs. In practical applications,
%the bids being discretized, if $\delta$ is smaller than the discretization
%step, the mechanism will be truthful in effect.

%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
%variant of Myerson's theorem.

\begin{lemma}\label{thm:myerson-variant}
\sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is
$\delta$-truthful if:
(a) $S$ is $\delta$-decreasing, \emph{i.e.}, for any agent $i$ and $c_i' \leq
c_i-\delta$, for any
fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i,
c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b)
 agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$.
\end{lemma}
\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$ using Proposition~\ref{prop:monotonicity},
    compute a $\varepsilon$-accurate, $\delta$-decreasing
    approximation of $\max_{\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
Our 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, which is proved in Appendix~\ref{sec:proofofmainthm}:
\begin{theorem}\label{thm:main}
    \sloppy
    For any $\delta>0$ the allocation described in Algorithm~\ref{mechanism},
    along with threshold payments, is $\delta$-truthful, individually rational
    and budget feasible.  Furthermore, there exists an absolute constant $C$
    such that, for any $\varepsilon>0$, the mechanism runs in time
    $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
    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}
The value of the constant $C$ is given by \eqref{eq:constant} in
Appendix~\ref{sec:proofofmainthm}.
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}