From 8562564268f83ca4ea0a4d6cd316a61f8b66f6b2 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
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

