From 7f6e240cf4c111449cc2fceae13a0925fc95192a Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 11 Feb 2013 20:11:11 -0800 Subject: Abstract --- abstract.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'abstract.tex') diff --git a/abstract.tex b/abstract.tex index bb02350..ae26832 100644 --- a/abstract.tex +++ b/abstract.tex @@ -16,7 +16,7 @@ As a proxy for various practical constraints, \E{} may select only a subset of s We initiate the study of budgeted mechanisms for experimental design. In this setting, \E{} has a budget $B$. Each subject $i$ declares an associated cost $c_i >0$ to be part of the experiment, and must be paid at least her cost. In particular, the {\em Experimental Design Problem} (\SEDP) is to find a set $S$ of subjects for the experiment that maximizes $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 parameter $\beta$ that is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. Further, the subjects are \emph{strategic} and may lie about their costs. Thus, we need to design a -mechanism for \SEDP with suitable properties. +mechanism for \SEDP{} with suitable properties. We present a deterministic, polynomial time, truthful, budget feasible mechanism for \SEDP{}. By applying previous work on budget feasible mechanisms with submodular objective, one could {\em only} have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. Our mechanism yields a constant factor ($\approx 12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation. We also show how to generalize our approach to a wide class of learning problems. -- cgit v1.2.3-70-g09d2