Change to ACM style and inlining of the proofsHEADmaster

1 files changed, 11 insertions, 11 deletions

diff --git a/problem.tex b/problem.tex
index 6033e86..c3c124e 100644
--- a/problem.tex
+++ b/problem.tex
@@ -59,7 +59,7 @@ which is the entropy reduction on $\beta$ after the revelation of $y_S$ (also kn
 Hence, selecting a set of experiments $S$ that
 maximizes $V(S)$ is equivalent to finding the set of experiments that minimizes
 the uncertainty on $\beta$, as captured by the entropy reduction of its estimator.
-Under the linear model, and the Gaussian prior, the information gain takes the following form (see, \emph{e.g.}, \cite{chaloner1995bayesian}):
+Under the linear model, and the Gaussian prior, the information gain takes the following form (see, \emph{e.g.}, \mbox{\cite{chaloner1995bayesian}}):
 \begin{align}
  I(\beta;y_S)&= \frac{1}{2}\log\det(R+ \T{X_S}X_S) - \frac{1}{2}\log\det R\label{dcrit} %\\
 \end{align}
@@ -90,7 +90,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 \cite{arxiv}.
+covariance matrices $R$ can be found in Appendix~\ref{sec:ext}.
 
  %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$.
@@ -117,7 +117,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 \cite{arxiv}. 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 Appendix~\ref{app:properties}. 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.}, 
@@ -142,14 +142,11 @@ the following algorithm:
 \textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
 \;\textbf{else return}\; S_G
 \end{equation}
-yields an approximation ratio  of $\frac{5 e }{e-1}~$\cite{singer-mechanisms}; this can be further improved to $\frac{e}{e-1}$ using more complicated greedy set constructions~\cite{krause-submodular,sviridenko-submodular}.
+yields an approximation ratio  of $\frac{2 e }{e-1}~$\cite{krause-submodular}; this can be further improved to $\frac{e}{e-1}$ using more complicated greedy set constructions~\cite{krause-submodular,sviridenko-submodular}.
 
-
-
-
- \subsection{Budget-Feasible Experimental Design: Strategic Case}
+\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 \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 
+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 
  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.
   
@@ -157,8 +154,11 @@ 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$ (\emph{e.g.}, a tenth of a cent) 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  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 \cite{arxiv}, motivating our study of more complex mechanisms.
+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 give an example in Appendix~\ref{sec:non-monotonicity}, motivating 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