From 8562564268f83ca4ea0a4d6cd316a61f8b66f6b2 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 7 Jul 2013 21:21:23 -0700 Subject: minor --- problem.tex | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) (limited to 'problem.tex') diff --git a/problem.tex b/problem.tex index 1001d7b..8d5b262 100644 --- a/problem.tex +++ b/problem.tex @@ -84,13 +84,9 @@ covariance matrices $R$ can be found in Appendix~\ref{sec:ext}. \subsection{Budget-Feasible Experimental Design: Full Information Case}\label{sec:fullinfo} -Beyond the cardinality constraint in classical experimental design discussed above, a - budgeted version can also be considered. -%depart from the above classic experimental design setting by assuming that -Each experiment is associated with a cost $c_i\in\reals_+$. Moreover, the experimenter $\E$ is limited by a budget $B\in \reals_+$. -The cost $c_i$ can capture, \emph{e.g.}, the amount the subject $i$ deems sufficient to -incentivize her participation in the experiment. -In the full-information case, the experiment costs are common knowledge; as such, the optimization problem that the experimenter wishes to solve is: +Instead of the cardinality constraint in classical experimental design discussed above, we consider a budget-constrained version. +Each experiment is associated with a cost $c_i\in\reals_+$. +The cost $c_i$ can capture, \emph{e.g.}, the amount the subject $i$ deems sufficient to incentivize her participation in the experiment. The experimenter $\E$ is limited by a budget $B\in \reals_+$. In the full-information case, experiment costs are common knowledge; as such, the experimenter wishes to solve: \medskip\\\hspace*{\stretch{1}}\textsc{ExperimentalDesignProblem} (\EDP)\hspace*{\stretch{1}} \begin{subequations} \begin{align} @@ -149,7 +145,7 @@ We seek mechanisms that are \emph{normalized} (unallocated experiments receive z We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring that reporting one's true cost is an \emph{almost-dominant} strategy: no subject increases their utility by reporting a cost that differs more than $\delta>0$ from their true cost. Under this definition, a mechanism is truthful if $\delta=0$. In addition, we would like the allocation $S(c)$ to be of maximal value; however, $\delta$-truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with that yield a \emph{constant approximation ratio}, \emph{i.e.}, there exists $\alpha\geq 1$ s.t.~$OPT \leq \alpha V(S(c))$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time. -We note that the $\max$ operator in the greedy algorithm \eqref{eq:max-algorithm} breaks +We note that the greedy algorithm \eqref{eq:max-algorithm} breaks truthfulness. Though this is not true for all submodular functions (see, \emph{e.g.}, \cite{singer-mechanisms}), it is true for the objective of \EDP{}: we show this in Appendix~\ref{sec:non-monotonicity}. This motivates our study of more complex mechanisms. \begin{comment} -- cgit v1.2.3-70-g09d2