diff options
| -rw-r--r-- | abstract.tex | 2 | ||||
| -rw-r--r-- | main.tex | 4 | ||||
| -rw-r--r-- | proofs.tex | 15 |
3 files changed, 10 insertions, 11 deletions
diff --git a/abstract.tex b/abstract.tex index eebeb97..a92ad45 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 associated cost $c_i >0$ to be part of the experiment, and must be paid at least their cost. Further, the subjects are \emph{strategic} and may lie about their costs . In particular, we formulate the {\em Strategic 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. -We present a deterministic, polynomial time, truthful, budget feasible mechanism for \EDP{}. +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 apply our approach to a wide class of learning problems. @@ -148,8 +148,8 @@ We can now state our main result: \begin{align*} OPT & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+ - \varepsilon\\ - & \simeq 12.98V(S^*) + \varepsilon + \varepsilon + \simeq 12.98V(S^*) + \varepsilon \end{align*} \end{theorem} The value of the constant $C$ is given by \eqref{eq:constant} in @@ -316,14 +316,13 @@ In particular, \begin{gather*} \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1} \end{gather*} -as $A(S)\leq A(S\cup\{i\})$. Observe that - \begin{gather*} - \forall S\subseteq\mathcal{N}\setminus\{i\},\quad - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq - P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\}),\\ - \forall S\subseteq\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) - \geq P_\mathcal{N}^\lambda(S). - \end{gather*} +as $A(S)\preceq A(S\cup\{i\})$. Observe that + % \begin{gather*} + % \forall +$P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})$ for all $S\subseteq\mathcal{N}\setminus\{i\}$, and + % ,\\ + $P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \geq P_\mathcal{N}^\lambda(S),$ for all $S\subseteq\mathcal{N}$. + %\end{gather*} Hence, \begin{align*} \partial_i F(\lambda) |