From 7f6b960702e38cf2e34d5594ba2b37a45f8a9520 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Thu, 12 Dec 2013 17:48:03 -0500
Subject: Reimport things from the appendix to the main part for the
 camera-ready version

---
 problem.tex | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index 0e9c75f..46e72c5 100755
--- a/problem.tex
+++ b/problem.tex
@@ -91,7 +91,7 @@ d}.$ Intuitively, this corresponds to the simplest prior, in which no direction
 of $\reals^d$ is a priori favored; equivalently, it also corresponds to the
 case where ridge regression estimation \eqref{ridge} performed by $\E$ has
 a penalty term $\norm{\beta}_2^2$. A generalization of our results to arbitrary 
-covariance matrices $R$ can be found in Appendix~\ref{sec:ext}.
+covariance matrices $R$ can be found in \cite{arxiv}.
 
  %Note that \eqref{dcrit} is a submodular set function, \emph{i.e.}, 
 %$V(S)+V(T)\geq V(S\cup T)+V(S\cap T)$ for all $S,T\subseteq \mathcal{N}$; it is also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subset T$.
@@ -118,7 +118,7 @@ the optimal value achievable in the full-information case.
 reduces to EDP with $d=1$ by mapping the weight of each item, say,
 $w_i$, to an experiment with $x_i^2=w_i$.% Moreover, \eqref{modified} is submodular, monotone and satisfies $V(\emptyset) = 0$.
 
-The value function \eqref{modified} has the following properties, which are proved in Appendix~\ref{app:properties}. First, it is non-negative, \emph{i.e.}, $V(S)\geq 0$
+The value function \eqref{modified} has the following properties, which are proved in \cite{arxiv}. First, it is non-negative, \emph{i.e.}, $V(S)\geq 0$
 for all $S\subseteq\mathcal{N}$. Second, it is
 also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subseteq T$, with
 $V(\emptyset)=0$. Finally, it is submodular, \emph{i.e.}, 
@@ -150,7 +150,7 @@ yields an approximation ratio  of $\frac{5 e }{e-1}~$\cite{singer-mechanisms}; t
 
  \subsection{Budget-Feasible Experimental Design: Strategic Case}
 We study the following \emph{strategic} setting, in which the costs $c_i$ are {\em not} common knowledge and their reporting can be manipulated by the experiment subjects. The latter are strategic and wish to maximize their utility, which is the difference of the payment they receive and their true cost. Note that, though subjects may misreport $c_i$, they cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement).
-Experimental design  thus reduces to a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}; we review the formal definition  in Appendix~\ref{app:budgetfeasible}. In short, given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{reverse auction mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function} $S:\reals_+^n \to 2^\mathcal{N}$,  determining the set 
+Experimental design  thus reduces to a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}; we review the formal definition  in \cite{arxiv}. In short, given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{reverse auction mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function} $S:\reals_+^n \to 2^\mathcal{N}$,  determining the set 
  of experiments to be purchased, and (b) a \emph{payment function}
 $p:\reals_+^n\to \reals_+^n$, determining the payments $[p_i(c)]_{i\in \mathcal{N}}$ received by experiment subjects.
   
@@ -159,7 +159,7 @@ We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring t
 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  are \emph{$(\alpha,\beta)$-approximate}, \emph{i.e.}, there exist $\alpha\geq 1$ and $\beta>0$ s.t.~$OPT \leq \alpha V(S(c))+\beta$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time.
 
 We note that  the constant approximation 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.
+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 \cite{arxiv}. This motivates our study of more complex mechanisms.
 
 \begin{comment}
 As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are  \emph{single parameter} auctions: each agent has only one
-- 
cgit v1.2.3-70-g09d2

