\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 let
$i^*$ be the element of maximum value. 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:max-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~\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.

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 the following
allocation:
\begin{displaymath}
\textbf{if}\; V(\{i^*\}) \geq C \cdot 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 contributions of \citeN{chen} and
\citeN{singer-influence} is to come up with appropriate such 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_{-i^*}$. 

\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, there exists an absolute constant $C$ such that, 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*}
    The value of the constant $C$ is given by \eqref{eq:constant} in
    Section~\ref{sec:proofofmainthm}.
\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}