From 574e1f7e48f238efada8bff73ba26fd6dd50aaac Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 11 Feb 2013 16:36:11 -0800
Subject: related

---
 intro.tex | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

(limited to 'intro.tex')

diff --git a/intro.tex b/intro.tex
index f69620f..39e6b52 100644
--- a/intro.tex
+++ b/intro.tex
@@ -34,15 +34,17 @@ We initiate the study of experimental design problem in presence of budgets and
 %is  related to the covariance of the $x_i$'s.
  In particular, we formulate the  {\em Strategic Experimental Design Problem} (\SEDP) as follows: the experimenter \E\ wishes to find set $S$ of subjects to maximize 
 \begin{align}V(S) = \log\det\Big(I_d+\sum_{i\in S}x_i\T{x_i}\Big) \label{obj}\end{align}
-subject to a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget, as well as the usual constraints of truthfulness and individual rationality. %, and other {\em strategic constraints} we don't list here.
+subject to a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget, as well as the usual constraints of truthfulness and individual rationality. 
+This is naturally viewed  as a \emph{budget feasible mechanism design} problem, as introduced by \citeN{singer-mechanisms}.
+%, and other {\em strategic constraints} we don't list here.
 
 \smallskip
 The objective function, which is the key, is formally obtained by optimizing  the information gain in  $\beta$ when the latter is learned  through linear regression, and is related to  the so-called $D$-optimality criterion~\cite{pukelsheim2006optimal,atkinson2007optimum}. 
 \item
-We present a polynomial time, truthful mechanism for \SEDP{}, yielding a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. In contrast to this, we show that no truthful, budget-feasible algorithms are possible for \SEDP{}  within a factor 2 approximation. 
+We present a polynomial time, truthful mechanism for \SEDP{}, yielding a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. In contrast to this, we show that no truthful, budget-feasible mechanisms are possible for \SEDP{}  within a factor 2 approximation. 
 
 \smallskip
-We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results for budget feasible mechanisms under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time,  or a non-deterministic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded).
+We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results on budget feasible mechanism design under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time,  or a non-deterministic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded).
 \end{itemize}
 
 
-- 
cgit v1.2.3-70-g09d2

