diff options
Diffstat (limited to 'intro.tex')
| -rw-r--r-- | intro.tex | 4 |
1 files changed, 2 insertions, 2 deletions
@@ -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 |