diff options
| -rw-r--r-- | abstract.tex | 21 | ||||
| -rw-r--r-- | intro.tex | 2 | ||||
| -rw-r--r-- | paper.tex | 12 |
3 files changed, 30 insertions, 5 deletions
diff --git a/abstract.tex b/abstract.tex index 2da5561..a3766da 100644 --- a/abstract.tex +++ b/abstract.tex @@ -1,8 +1,21 @@ -We initiate the study of mechanisms for \emph{experimental design}. In this setting, -an experimenter with a budget $B$ has access to a population of $n$ potential experiment subjects $i\in 1,\ldots,n$, each associated with a vector of features $x_i\in\reals^d$ as well as a cost $c_i>0$. -Conducting an experiment with subject $i$ reveals an unknown value $y_i\in \reals$ to the experimenter. Assuming a linear relationship between $x_i$'s and $y_i$'s, \emph{i.e.}, $y_i \approx \T{\beta} x_i$, conducting the experiments and obtaining the measurements $y_i$ allows the experimenter to estimate $\beta$. The experimenter's goal is to select which experiments to conduct, subject to her budget constraint, to obtain the best estimate possible. +%We initiate the study of mechanisms for \emph{experimental design}. -We study this problem when subjects are \emph{strategic} and may lie about their costs. In particular, we formulate the {\em Experimental Design Problem} (\EDP) as finding a set $S$ of subjects that maximize $V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i})$ under the constraint $\sum_{i\in S}c_i\leq B$; our objective function corresponds to the information gain in $\beta$ when it is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. We present the first known deterministic, polynomial time truthful mechanism for \EDP{}, yielding a constant factor ($\approx 19.68$) approximation, and show that no truthful algorithms are possible within a factor 2 approximation. Moreover, we show that a wider class of learning problems admits a polynomial time universally truthful (\emph{i.e.}, randomized) mechanism, also within a constant factor approximation. +In the classical {\em experimental design} setting, +an experimenter \E\ with a budget $B$ has access to a population of $n$ potential experiment subjects $i\in 1,\ldots,n$, each associated with a vector of features $x_i\in\reals^d$ as well as a cost $c_i>0$. +Conducting an experiment with subject $i$ reveals an unknown value $y_i\in \reals$ to \E. \E\ typically assume some +hypothetical relationship between $x_i$'s and $y_i$'s, \emph{e.g.}, $y_i \approx \T{\beta} x_i$, and estimates +$\beta$ from experiments. +%conducting the experiments and obtaining the measurements $y_i$ allows +%\E\ can estimate $\beta$. +\E\ 's goal is to select which experiments to conduct, subject to her budget constraint. +%, to obtain the best estimate possible for $\beta$. + +We initiate the study of mechanisms for experimental design. In this setting, +subjects are \emph{strategic} and may lie about their costs. In particular, we formulate the {\em Experimental Design Problem} (\EDP) as finding a set $S$ of subjects that maximize $V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i})$ under the constraint $\sum_{i\in S}c_i\leq B$; our objective function corresponds to the information gain in $\beta$ when it is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. We present the first known +deterministic, polynomial time, truthful, budget feasible mechanism for \EDP{}. +Our mechanism yields a constant factor ($\approx 19.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor 2 approximation. +Our approach here generally applies to a wider class of learning problems and +obtains polynomial time universally truthful (\emph{i.e.}, randomized) budget feasible mechanism, also within a constant factor approximation. @@ -16,7 +16,7 @@ However, there is a cost $c_i$ associated with experimenting on subject $i$ which varies from subject to subject. This may be viewed as the cost subject $i$ incurs when tested and for which she needs to be reimbursed; or, it might be viewed as the incentive for $i$ -to participate in the experiment; or, it might be the inherent value of the data. When subjects are strategic, they may have an incentive to misreport their cost. This economic aspect has always been inherent in experimental design: experimenters often work within strict budgets and design creative incentives. However, we are not aware of principled study of this setting from a strategic point of view. +to participate in the experiment; or, it might be the inherent value of the data. This economic aspect has always been inherent in experimental design: experimenters often work within strict budgets and design creative incentives. However, we are not aware of principled study of this setting from a strategic point of view. When subjects are strategic, they may have an incentive to misreport their cost and the choice of experiments and payments need to be more sophisticated. Our contributions are as follows. @@ -11,6 +11,18 @@ \let\@copyrightspace\relax \makeatother +\numberofauthors{3} +\author{ +\alignauthor Thibaut Horel \titlenote{\texttt{thibaut.horel@ens.fr}}\\ + \affaddr{Technicolor}\\ + %\email{thibaut.horel@ens.fr} +\alignauthor Stratis Ioannidis \titlenote{\texttt{stratis.ioannidis@technicolor.com}}\\ + \affaddr{Technicolor}\\ + %\email{stratis.ioannidis@technicolor.com} +\alignauthor S. Muthukrishnan \titlenote{\texttt{muthu@cs.rutgers.edu}}\\ + \affaddr{Rutgers University}\\ + %\email{muthu@cs.rutgers.edu} +} \begin{document} \maketitle |