path: root/related.tex

\section{Related work}
\label{sec:related}

\junk{\subsection{Experimental Design} The classic experimental design problem, which we  review in Section~\ref{sec:edprelim}, deals with  which $k$ experiments to conduct among a set of $n$ possibilities. It is a well studied problem both in the non-Bayesian \cite{pukelsheim2006optimal,atkinson2007optimum,boyd2004convex} and Bayesian setting \cite{chaloner1995bayesian}. Beyond $D$-optimality, several other objectives are encountered in the literature  \cite{pukelsheim2006optimal}; many involve a function of the covariance of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by its tractability and its relationship to the information gain.  %are encountered in the literature, though they do not relate to entropy as $D$-optimality. We leave the task of approaching the maximization of such objectives from a strategic point of view as an open problem.
}
\noindent\emph{Budget Feasible Mechanisms for General Submodular Functions.}
Budget feasible mechanism design was originally proposed by  \citeN{singer-mechanisms}, who 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. 
He shows that there exists a randomized, 112-approximation mechanism that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen}  improve this result to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms.

The above approximation guarantees hold for the expected value of the
randomized mechanism: for a given
instance, the approximation ratio provided by the mechanism may be
unbounded. No deterministic, truthful, constant approximation mechanism that
runs in polynomial time is presently known for submodular maximization.
Assuming access to an oracle providing the optimum in the
full-information setup, Chen \emph{et al.}~propose a truthful, $8.34$-approximate mechanism; in cases for which the full-information problem is NP-hard, as \EDP, this mechanism is not poly-time, unless P=NP.  Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. 

\noindent\emph{Budget Feasible Mechanism Design on Specific Problems.}
Improved uper and lower bounds \emph{and} deterministic polynomial mechanisms are known for specific submodular objectives \cite{singer-mechanisms, chen, singer-influence}.
\junk{For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer 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, \citeN{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-influence}.}
The  deterministic mechanisms for \textsc{Knapsack} \cite{chen} and
\textsc{Coverage} \cite{singer-influence} follow the same general framework,
which we also employ. In these two cases, the framework approximates the
optimal solution to the underlying combinatorial problem by a linear program (LP) relaxation~\cite{pipage}. No
such  relaxation exists for \EDP, which is unlikely to be
approximable through an LP due to its logarithmic objective. We develop instead a convex relaxation to \EDP;
though, contrary to the above LP relaxations, this cannot be solved exactly, we show how to
incorporate it in the framework of
\cite{chen,singer-influence} to yield a $\delta$-truthful mechanism for \EDP.  

%Our results therefore add \SEDP{} to the set of problems for which a deterministic, polynomial time, constant approximation mechanism is known.

\noindent\emph{Beyond Submodular Objectives.}
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 universally truthful, $O(\frac{\log n}{\log \log n})$-appro\-xi\-mate 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)
Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}.

\noindent\emph{Monotone Approximations in Combinatorial Auctions.}
Relaxations of combinatorial problems are prevalent
in \emph{combinatorial auctions}, 
in which an auctioneer aims at maximizing the social welfare. As noted by \citeN{archer-approximate},
approximations to this maximization must preserve incentive compatibility. Most approximation
algorithms do not preserve this property, hence specific relaxations, and corresponding roundings to an integral solution, must be
constructed \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}. Because of the specificity of our relaxation, and because we seek a determinist mechanism and $\delta$-truthfulness, not truthfulness-in-expectation, none of the techniques present in these works apply to our setting.


\junk{\citeN{archer-approximate} propose a randomized rounding of the LP relaxation of the \textsc{SetPacking} problem, yielding a mechanism
which is \emph{truthful-in-expectation}. %and in high probability. 
\citeN{lavi-truthful} construct randomized
truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation
ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution from which they sample integral solutions. 
Beyond LP relaxations, 
\citeN{dughmi2011convex} propose
truthful-in-expectation mechanisms for combinatorial auctions in which
the bidders' utilities are matroid rank sum functions (applied earlier to the \textsc{CombinatorialPublicProjects} problem \cite{dughmi-truthful}).  Their framework relies
on solving a convex optimization problem which can only be solved approximately. As in \cite{lavi-truthful}, they also treat the fractional solution as a distribution over which they sample integral solutions. The authors ensure that a solver is applied to a
``well-conditioned'' problem,  which resembles the technical challenge we face in
Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation. In addition, our objective is not a matroid rank sum function. As such, both the methodology for dealing with problems that are not ``well-conditioned''  as well as the approximation guarantees of the convex relaxation  in \cite{dughmi2011convex} do not readily extend to \EDP.
\citeN{briest-approximation} construct monotone FPTAS for problems that can be approximated through rounding techniques, which in turn can be used to construct truthful, deterministic, constant-approximation  mechanisms for corresponding  combinatorial auctions.}

%\EDP{} is not readily approximable through such rounding techniques; as such, we rely on a relaxation to approximate it.

\noindent\emph{$\delta$-Truthfulness and Differential Privacy.}
The notion of $\delta$-truthfulness has attracted considerable attention recently in the context of differential privacy (see, \emph{e.g.}, the survey by \citeN{pai2013privacy}).  \citeN{mcsherrytalwar} were the first to observe that any $\epsilon$-differentially private mechanism must also be $\delta$-truthful in expectation, for $\delta=2\epsilon$. This property was used to construct $\delta$-truthful (in expectation) mechanisms for a digital goods auction~\cite{mcsherrytalwar} and for $\alpha$-approximate equilibrium selection \cite{kearns2012}. \citeN{approximatemechanismdesign} propose a framework for converting a differentially private mechanism to a truthful-in-expectation mechanism by randomly selecting between a differentially private mechanism with good approximation guarantees, and a truthful mechanism. They apply their framework to the \textsc{FacilityLocation} problem. We depart from the above works in seeking a deterministic mechanism for \EDP, and using a stronger notion of $\delta$-truthfulness.


\begin{comment}
\paragraph{Data Markets}
 A series of recent papers  \cite{mcsherrytalwar,approximatemechanismdesign,xiao:privacy-truthfulness,chen:privacy-truthfulness} consider the related problem of retrieving data from an  \textit{unverified} database, where strategic users may misreport their data to ensure their privacy. %\citeN{mcsherrytalwar} argue that \emph{differentially private} mechanisms offer a form of \emph{approximate truthfulness}: if users have a utility that depends on their privacy, reporting their data untruthfully can only increase their utility by a small amount.  %\citeN{xiao:privacy-truthfulness}, improving upon earlier work by~\citeN{approximatemechanismdesign}, constructs mechanisms that simultaneously achieve exact truthfulness as well as differential privacy. 
We depart by assuming that experiment outcomes are tamper-proof and cannot be manipulated.  
A different set of papers \cite{ghosh-roth:privacy-auction,roth-liggett,pranav} consider a setting where data cannot be misreported, but the utility of users is a function of the differential privacy guarantee an analyst provides them. We do not focus on privacy; any privacy costs in our setup are internalized in the costs $c_i$.  %Eliciting private data through a \emph{survey} \cite{roth-liggett}, whereby individuals first decide whether to participate in the survey and then report their data,
% also falls under the unverified database setting \cite{xiao:privacy-truthfulness}. In the \emph{verified} database setting, \citeN{ghosh-roth:privacy-auction} and~\citeN{pranav} consider budgeted auctions where users have a utility again captured by differential privacy. Our work departs from the above setups in that utilities do not involve privacy, whose effects are assumed to be internalized in the costs reported by the users; crucially, we also assume that experiments are tamper-proof, and individuals can misreport their costs but not their values.

\sloppy
Our work is closest to the survey setup of~\citeN{roth-schoenebeck}, who also
consider how to sample individuals with different features who report a hidden
value at a certain cost. The authors assume a joint distribution between costs
$c_i$ and features $x_i$, and wish to obtain an unbiased estimate of the
expectation of the hidden value over the population, under the constraints of
truthfulness, budget feasibility and individual rationality. Our work departs
by learning a more general statistic (a linear model) rather than data means.
We note that, as in \cite{roth-schoenebeck}, costs $c_i$ and features $x_i$ can
be arbitrarily correlated in our work---the experimenter's objective \eqref{obj}  does not depend on their joint distribution.
\end{comment}

\fussy
%\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}