small stuff

1 files changed, 9 insertions, 8 deletions

diff --git a/intro.tex b/intro.tex
index d2ba54c..33ce910 100644
--- a/intro.tex
+++ b/intro.tex
@@ -21,23 +21,24 @@ to participate in the experiment; or, it might be the inherent value of the data
 Our contributions are as follows.
 \begin{itemize}
 \item
-We formulate the problem of experimental design subject to a given budget, in presence of strategic agents who specify their costs. In particular, we focus on linear regression. This is naturally viewed  as a budget feasible mechanism design problem with a sophisticated objective function that is related to the covariance of the $x_i$'s. In particular we formulate the  {\em Experimental Design Problem} (\edp\ ) as follows: the experimenter \E\ wishes to maximize 
+We formulate the problem of experimental design subject to a given budget, in presence of strategic agents who specify their costs. In particular, we focus on linear regression. This is naturally viewed  as a budget feasible mechanism design problem with a sophisticated objective function that is related to the covariance of the $x_i$'s. In particular we formulate the  {\em Experimental Design Problem} (\EDP) as follows: the experimenter \E\ wishes to maximize 
 \begin{align}V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i}) \label{obj}\end{align}
-subject to the budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget, and other {\em strategic constraints} we don't list here. The objective function, which is the key, is motivated from the so-called $D$-objective criterion; in particular, it captures the reduction in the entropy of $\beta$ when the latter is learned  through regression methods.
+subject to the budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget. %, and other {\em strategic constraints} we don't list here.
+ The objective function, which is the key, is motivated from the so-called $D$-objective criterion; in particular, it captures the reduction in the entropy of $\beta$ when the latter is learned  through regression methods.
 
 \item
 The above objective is submodular. 
 There are several recent results in budget feasible 
 mechanisms~\cite{singer-mechanisms,chen,singer-influence,bei2012budget,dobz2011-mechanisms}, and some apply to  the submodular optimization in 
-\edp.
+\EDP.
 There is a randomized, 7.91-approximate mechanism for maximizing a general submodular function that is universally truthful, \emph{i.e.}, it is sampled from a distribution among truthful mechanisms. 
 There are however no known deterministic truthful mechanisms for general submodular functions.
-For specific combinatorial problems such as knapsack or coverage, there exist 
-constant-approximation algorithms~\cite{singer-mechanisms,chen, singer-influence}, but they don't work for the linear-algebraic  objective function in \edp.
-{\bf S+T: could we verify that the above sentence is correct in its implication?}
+For specific combinatorial problems such as \textsc{Knapsack} or \textsc{Coverage}, there exist 
+deterministic, truthful constant-approximation algorithms~\cite{singer-mechanisms,chen, singer-influence}, but they don't work for the linear-algebraic  objective function in \EDP.
+%{\bf S+T: could we verify that the above sentence is correct in its implication?}
 
-We present the first known, polynomial time truthful mechanism for \edp and show that it is a constant factor ($\approx 19$) approximation. The technical crux is an approximation algorithm we develop for a  suitable multi-linear relaxation derived from \edp.
-In contrast, no such truthful algorithms are possible that will be factor 2 approximation. 
+We present the first known, polynomial time truthful mechanism for \EDP{} and show that it is a constant factor ($\approx 19$) approximation. The technical crux is an approximation algorithm we develop for a  suitable multi-linear relaxation derived from \EDP.
+In contrast, no such truthful algorithms are possible within a factor 2 approximation. 
 
 \item
 Our approach to mechanisms for experimental design is general. We apply it to study