From 8d55f0644cbdde549223995116dda8fb9b354cb3 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 11 Feb 2013 20:08:59 -0800
Subject: Abstract

---
 abstract.tex | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'abstract.tex')

diff --git a/abstract.tex b/abstract.tex
index 5bdcc95..bb02350 100644
--- a/abstract.tex
+++ b/abstract.tex
@@ -15,10 +15,10 @@ As a proxy for various practical constraints, \E{} may select only a subset of s
 %, to obtain the best estimate possible for $\beta$.
 
 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.  Further,  the subjects 
-are \emph{strategic} and may lie about their costs. In particular, we formulate the {\em  Experimental Design Problem} (\SEDP) as finding 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. 
+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, truthful, budget feasible mechanism for \SEDP{}.
-By applying previous work on budget feasible mechanisms with submodular objective, one could 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. 
+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

