app:properties

1 files changed, 5 insertions, 5 deletions

diff --git a/problem.tex b/problem.tex
index 851f691..89ffa9d 100644
--- a/problem.tex
+++ b/problem.tex
@@ -27,7 +27,7 @@ Then, \E\ estimates $\beta$ through \emph{maximum a posteriori estimation}: \emp
 \end{align}
 where the last equality is obtained by setting  $\nabla_{\beta}\prob(\beta\mid y_S)$ to zero and solving the resulting linear system; in \eqref{ridge}, $X_S\defeq[x_i]_{i\in S}\in \reals^{|S|\times d}$ is the matrix of experiment features and
 $y_S\defeq[y_i]_{i\in S}\in\reals^{|S|}$ are the observed measurements. 
-This optimization, commonly known as \emph{ridge regression}, includes an additional quadratic penalty term compared to the standard least squares estimation.
+This optimization, commonly known as \emph{ridge regression}, includes an additional quadratic penalty term $\beta^TR\beta$ compared to the standard least squares estimation.
 % under \eqref{model}, the maximum likelihood estimator of $\beta$ is the \emph{least squares} estimator: for $X_S=[x_i]_{i\in S}\in \reals^{|S|\times d}$ the matrix of experiment features and
 %$y_S=[y_i]_{i\in S}\in\reals^{|S|}$ the observed measurements, 
 %\begin{align} \hat{\beta} &=\max_{\beta\in\reals^d}\prob(y_S;\beta) =\argmin_{\beta\in\reals^d } \sum_{i\in S}(\T{\beta}x_i-y_i)^2 \nonumber\\
@@ -109,11 +109,11 @@ the optimal value achievable in the full-information case.
 reduces to EDP with dimension $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$.
 
- Note that \eqref{modified} 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
+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\subset T$, with
-$V(\emptyset)=0$. Finally, it is non-negative, \emph{i.e.}, $V(S)\geq 0$
-for all $S\subseteq\mathcal{N}$, since the matrix $\T{X_S}X_S$ is positive semi-definite for all $S\subseteq \mathcal{N}$.
+$V(\emptyset)=0$. Finally, it is a submodular, \emph{i.e.}, 
+$V(S)+V(T)\geq V(S\cup T)+V(S\cap T)$ for all $S,T\subseteq \mathcal{N}$. 
 %Finally, we define the strategic version  of \EDP{} (denoted by \SEDP) by adding the additional constraints of truthfulness, individual rationality, and normal payments, as described in the previous section.
 The above three properties imply that a greedy algorithm yields a constant approximation ratio to \EDP.
 In particular, consider the greedy algorithm in which, for