Typos. There was an error in the proof of lemma 4. Fixing this error changes our

approximation ratio to 12.98 instead of 19.68...

1 files changed, 2 insertions, 2 deletions

diff --git a/intro.tex b/intro.tex
index e113dbc..68eb17f 100644
--- a/intro.tex
+++ b/intro.tex
@@ -24,7 +24,7 @@ Our contributions are as follows.
 \item
 We formulate the problem of experimental design subject to a given budget, in the presence of strategic agents who may lie about their costs. In particular, we focus on linear regression. This is naturally viewed  as a budget feasible mechanism design problem, in which the objective function %is sophisticated and 
 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 find set $S$ of subjects to maximize 
-\begin{align}V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i}) \label{obj}\end{align}
+\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. %, and other {\em strategic constraints} we don't list here.
 The objective function, which is the key,  is obtained by optimizing  the information gain in  $\beta$ when it is learned  through linear regression methods, and is related to the so-called $D$-optimality criterion. 
 \item
@@ -38,7 +38,7 @@ For specific combinatorial problems such as \textsc{Knapsack} or \textsc{Coverag
 deterministic, truthful, polynomial constant-approximation algorithms~\cite{singer-mechanisms,chen, singer-influence}, but they do not 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{}. Our mechanism is a constant factor ($\approx 19.68$) approximation for \EDP{}. In contrast to this, we show that no truthful, budget-feasible algorithms are possible for \EDP{}  within a factor 2 approximation. From a technical perspective, we present a convex relaxation of \eqref{obj}, and show that it is within a constant factor from the so-called multi-linear relaxation of  \eqref{obj}. This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}.   %{\bf FIX the last sentence}
+We present the first known, polynomial time truthful mechanism for \EDP{}. Our mechanism is a constant factor ($\approx 12.98$) approximation for \EDP{}. In contrast to this, we show that no truthful, budget-feasible algorithms are possible for \EDP{}  within a factor 2 approximation. From a technical perspective, we present a convex relaxation of \eqref{obj}, and show that it is within a constant factor from the so-called multi-linear relaxation of  \eqref{obj}. This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}.   %{\bf FIX the last sentence}
 
 \item
 Our approach to mechanisms for experimental design --- by