related

1 files changed, 11 insertions, 12 deletions

diff --git a/related.tex b/related.tex
index f61db30..19b245b 100755
--- a/related.tex
+++ b/related.tex
@@ -1,33 +1,32 @@
 \section{Related work}
 \label{sec:related}
 
-\junk{\subsection{Experimental Design} The classic experimental design problem, which we also briefly review in Section~\ref{sec:edprelim}, deals with  which $k$ experiments to conduct among a set of $n$ possible experiments. 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 some function of the covariance matrix of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance of $\beta$) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by both its tractability as well as 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.
+\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}. 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). \citeN{chen}  improve this result to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization.
+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 for submodular maximization 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 for submodular maximization.
 
 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 in fact be
 unbounded. No deterministic, 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.},~propose a truthful, $8.34$-approximate 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 deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. 
+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 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, \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}. 
+Improved bounds \emph{and} 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 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 our mechanism for \EDP. We describe this framework in detail in
-Section~\ref{sec:main}. Both of these mechanisms rely on approximating the
-optimal solution to the underlying combinatorial problem by a well-known linear program (LP) relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No
-such  relaxation exists for \EDP, which unlikely to be
+which we also employ (see Appendix~\ref{sec:proofofmainthm}). In these two cases, the framework approximates the
+optimal solution to the underlying combinatorial problem by a well-known linear program (LP) relaxation~\cite{pipage}, which is solved exactly in polynomial time. 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
-establish that it can be incorporated in the framework of
+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.