Typos

1 files changed, 16 insertions, 2 deletions

diff --git a/related.tex b/related.tex
index 318a0e7..01d114c 100644
--- a/related.tex
+++ b/related.tex
@@ -8,7 +8,13 @@
 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 by providing 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 \emph{in expectation}: 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.},~provide 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}. 
+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}. 
 
 
 \subsection{Budget Feasible Mechanism Design on Specific Problems}
@@ -29,7 +35,15 @@ A different set of papers \cite{ghosh-roth:privacy-auction,roth-liggett,pranav}
 % 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.
+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.
 
 
 \fussy