diff options
| -rw-r--r-- | abstract.tex | 2 | ||||
| -rw-r--r-- | intro.tex | 3 |
2 files changed, 3 insertions, 2 deletions
diff --git a/abstract.tex b/abstract.tex index 614a36b..dc663d8 100644 --- a/abstract.tex +++ b/abstract.tex @@ -18,7 +18,7 @@ We initiate the study of budgeted mechanisms for experimental design. In this se 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. -We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant factor approximation to \EDP. In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and $\log\log\frac{B}{\epsilon\delta}$. +We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a 12.98 factor approximation to \EDP. %In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and $\log\log\frac{B}{\epsilon\delta}$. By applying previous work on budget feasible mechanisms with a submodular objective, one could {\em only} have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. We also establish that no truthful, budget-feasible mechanism is possible within a factor $2$ approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression. @@ -38,7 +38,8 @@ subject to a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budge \smallskip The objective function, which is the key, is formally obtained by optimizing the information gain in $\beta$ when the latter is learned through ridge regression, and is related to the so-called $D$-optimality criterion~\cite{pukelsheim2006optimal,atkinson2007optimum}. \item -We present a polynomial time mechanism scheme for \SEDP{} that is approximately truthful and yields a constant factor approximation to the optimal value of \eqref{obj}. In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and $\log\log\frac{B}{\epsilon\delta}$. In contrast to this, we show that no truthful, budget-feasible mechanisms are possible for \SEDP{} within a factor 2 approximation. +We present a polynomial time mechanism scheme for \SEDP{} that is approximately truthful and yields a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. %In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and $\log\log\frac{B}{\epsilon\delta}$. +In contrast to this, we show that no truthful, budget-feasible mechanisms are possible for \SEDP{} within a factor 2 approximation. \smallskip We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results on budget feasible mechanism design under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time, or a non-deterministic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded). |