\section{Related work}


Budget feasible mechanism design was originally proposed by Singer \cite{singer-mechanisms}. Singer considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model, \emph{i.e.} assuming an  oracle providing the  value of the submodular objective on any given set. 
 Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). Chen \emph{et al.}~\cite{chen}  improve this result by providing a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful mechanisms for submodular maximization.

In contrast to the above results, no truthful, constant approximation mechanism that runs in polynomial time is presently known for submodular maximization.  However, assuming access to an oracle providing the optimum in the full-information setup, Chen \emph{et al.},~provide a truthful, $8.34$-appoximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, this mechanism is not poly-time, unless P=NP.  Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful mechanisms, improving upon an earlier bound of 2 by Singer \cite{singer-mechanisms}. 

Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer,  Chen \emph{et al.}~\cite{chen} , give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate  mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-mechanisms,singer-influence}.

Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing  fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists
a truthful, $O(\log^3 n)$-approximate mechanism 
\cite{dobz2011-mechanisms} as well as a a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization. 
\cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations)

\stratis{TODO: privacy discussion. Logdet objective. Should be one paragraph each.}

\begin{comment}
Two types of mechanisms: \emph{deterministic} and \emph{randomized}. For
randomized mechanisms, people seek \emph{universally truthful} mechanisms:
mechanisms which are a randomization of truthful mechanisms.

\paragraph{Symmetric submodular functions} $V(S) = g(|S|)$ where $g$ is
a concave function. Truthful deterministic mechanism with approximation ratio
of 2. This is optimal \cite{singer-mechanisms}.

\paragraph{Knapsack} deterministic: $1+\sqrt{2}\leq \alpha \leq 2 + \sqrt{2}$,
randomized: $2\leq \alpha\leq 3$ \cite{chen}

\paragraph{Matching} deterministic: $2 \leq \alpha\leq 7.32$ \cite{singer-mechanisms}

\paragraph{Coverage} deterministic: $ ?\leq\alpha\leq 31$ \cite{singer-influence}

\paragraph{Submodular function} deterministic: $1+\sqrt{2}\leq\alpha\leq ?$,
randomized: $2\leq\alpha\leq 7.91$ \cite{chen}

For wider class of functions, \cite{singer-mechanisms} proves that even for XOS
functions, the lower bound is $\sqrt{n}$ (no constant approximation) even in the
non-strategic case). To be able to say something interesting, people extend the
computational model to the \emph{demand} query model: you have access to an
oracle which given a vector of price $[p_i]_{i\in\mathcal{N}}$ returns
$S\in\argmax_{S\subseteq\mathcal{N}} V(S) - \sum_{i\in S} p_i$

\paragraph{XOS functions} fractionally additive functions: functions which can
be written as the max of a finite set of additive functions. deterministic: 768

\paragraph{Complement-free (sub-additive) objective} derministic: $O(\log^3 n)$
\cite{dobz2011-mechanisms}. randomized: $O(\frac{\log n}{\log \log n})$
\cite{bei2012budget}. More generally \cite{bei2012budget} gives a randomized
mechanism which is $O(\mathcal{I})$ where $\mathcal{I}$ is the integrality gap
of a set cover like problem which is defined from the value function. In
particular, for XOS function, this integrality gap is $O(1)$.

\paragraph{Bayesian mechanism design} when we have a distribution over the
costs of the agents. In this case the approximation guarantee is defined in
expectations. \cite{bei2012budget} $768/512$ approximation ratio for any
subadditive function.

\paragraph{Online mechanisms} \cite{learning} in the i.i.d posted price model
for symmetric submodular functions randomized $O(1)$-competitive algorithm. For
general submodular function in the secretary posted price model randomized
$O(\log n)$-competitive algorithm. In the bidding model $O(1)$-competitive
algorithm.

\stratis{What is known about the maximization of logdet in the non-strategic case? Is it NP hard? Approximation ratios?}
\thibaut{Knapsack reduces to our problem in dimension 1, hence maximizing log
det is NP-hard. The approximation ratio is at least (1-1/e) by applying the
general approximation algorithm from Sviridenko \cite{sviridenko-submodular}.}
\end{comment}