From 1cb6e4b28e77b8c1a87e54bbd7097d7f8af0e371 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@Stratiss-MacBook-Air.local>
Date: Sun, 22 Sep 2013 07:54:48 +0200
Subject: stratis edits

---
 problem.tex | 0
 1 file changed, 0 insertions(+), 0 deletions(-)
 mode change 100644 => 100755 problem.tex

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
old mode 100644
new mode 100755
-- 
cgit v1.2.3-70-g09d2


From fc56a8f69d6eaeaecacdd4fdfa40df7e3d16599d Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@Stratiss-MacBook-Air.local>
Date: Sun, 22 Sep 2013 22:41:24 +0200
Subject: space saving

---
 approximation.tex |  4 ++--
 problem.tex       | 22 +++++++++++-----------
 2 files changed, 13 insertions(+), 13 deletions(-)

(limited to 'problem.tex')

diff --git a/approximation.tex b/approximation.tex
index cc278e1..1b94615 100755
--- a/approximation.tex
+++ b/approximation.tex
@@ -47,7 +47,7 @@ expectation of $V$ under the  distribution $P_\mathcal{N}^\lambda$:
     F(\lambda) 
     \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big]
   %  = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
-= \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right],\quad \lambda\in[0,1]^n.
+= \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[ \log\det\big( I_d + \textstyle\sum_{i\in S} x_i\T{x_i}\big) \big],\quad \lambda\in[0,1]^n.
 \end{equation}
 Function $F$ is an extension of $V$ to the domain  $[0,1]^n$, as it equals $V$ on integer inputs: $F(\id_S) = V(S)$ for all
 $S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. %\citeN{pipage} have shown how to use this extension to obtain approximation guarantees for an interesting class of optimization problems through the \emph{pipage rounding} framework, which has been successfully applied in \citeN{chen, singer-influence}. 
@@ -56,7 +56,7 @@ multi-linear extension \eqref{eq:multi-linear} cannot be optimized in
 polynomial time for  the value function $V$  we study here, given by \eqref{modified}. Hence, we introduce an extension $L:[0,1]^n\to\reals$ s.t.~
 \begin{equation}\label{eq:our-relaxation}
         L(\lambda) \defeq
-\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
+\log\det\big(I_d + \textstyle\sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\big),
 %= \log\det\left(\mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right),
 \quad \lambda\in[0,1]^n.
 \end{equation}
diff --git a/problem.tex b/problem.tex
index 798e69a..0e9c75f 100755
--- a/problem.tex
+++ b/problem.tex
@@ -35,8 +35,8 @@ maximum a posteriori estimation leads to the following maximization
 \cite{hastie}: 
 \begin{align}
     \begin{split}
-        \hat{\beta} = \argmax_{\beta\in\reals^d} \prob(\beta\mid y_S)
-        &=\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - \T{\beta}x_i)^2
+        \hat{\beta} = \textstyle\argmax_{\beta\in\reals^d} \prob(\beta\mid y_S)
+        &=\textstyle\argmin_{\beta\in\reals^d} \big(\textstyle\sum_{i\in S} (y_i - \T{\beta}x_i)^2
         + \T{\beta}R\beta\big)\\
         & = (R+\T{X_S}X_S)^{-1}X_S^Ty_S \label{ridge}
     \end{split}
@@ -64,7 +64,7 @@ Under the linear model, and the Gaussian prior, the information gain takes the f
 \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}
-Maximizing $I(\beta;y_S)$ is therefore equivalent to maximizing $\log\det(R+ \T{X_S}X_S)$, which is  known in the experimental design literature as the Bayes
+Maximizing $I(\beta;y_S)$ is therefore equivalent to maximizing $\log\det(R+ \T{X_S}X_S)$, which is known in   literature as the Bayes
 $D$-optimality criterion
 \cite{pukelsheim2006optimal,atkinson2007optimum,chaloner1995bayesian}. 
 
@@ -104,18 +104,18 @@ The cost $c_i$ can capture, \emph{e.g.}, the amount the subject $i$ deems suffic
 \medskip\\\hspace*{\stretch{1}}\textsc{ExperimentalDesignProblem} (\EDP)\hspace*{\stretch{1}}
 \begin{subequations}
 \begin{align}
-\text{Maximize}\quad V(S) &= \log\det(I_d+\T{X_S}X_S) \label{modified} \\
-\text{subject to}\quad \sum_{i\in S} c_i&\leq B\label{lincon}
+\text{Maximize}\quad &V(S) = \log\det(I_d+\T{X_S}X_S) \label{modified} \\
+\text{subject to}\quad &\textstyle\sum_{i\in S} c_i\leq B\label{lincon}
 \end{align}\label{edp}
 \end{subequations}
 \emph{W.l.o.g.}, we assume that $c_i\in [0,B]$ for all $i\in \mathcal{N}$, as no $i$ with $c_i>B$ can be in an $S$ satisfying \eqref{lincon}. Denote by
 \begin{equation}\label{eq:non-strategic}
-    OPT = \max_{S\subseteq\mathcal{N}} \Big\{V(S) \;\Big| \;
-    \sum_{i\in S}c_i\leq B\Big\}
+    OPT = \textstyle\max_{S\subseteq\mathcal{N}} \big\{V(S) \;\Big| \;
+   \textstyle \sum_{i\in S}c_i\leq B\big\}
 \end{equation}
 the optimal value achievable in the full-information case. 
 \EDP{}, as defined above, is  NP-hard; to see this, note that \textsc{Knapsack}
-reduces to EDP with dimension $d=1$ by mapping the weight of each item, say,
+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$
@@ -149,13 +149,13 @@ 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. We 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).
-In this setting,  experimental design 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 
+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 
  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.
   
 We seek mechanisms that are \emph{normalized} (unallocated experiments receive zero payments), \emph{individually rational} (payments for allocated experiments exceed costs), have \emph{no positive transfers} (payments are non-negative), and are \emph{budget feasible} (the sum of payments does not exceed the budget $B$). 
-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$. 
+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
-- 
cgit v1.2.3-70-g09d2

