From b1c62876ed5b5d81efcda1a342ac0d29f8a86568 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sat, 3 Nov 2012 01:17:54 +0100
Subject: Finish completing the discussion before the mechanism, some other
 corrections following Stratis's comments

---
 problem.tex | 26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index 0ba9db9..a8b89f4 100644
--- a/problem.tex
+++ b/problem.tex
@@ -14,15 +14,23 @@ $y_S=[y_i]_{i\in S}\in\reals^{|S|}$ the observed measurements,
 & = (\T{X_S}X_S)^{-1}X_S^Ty_S\label{leastsquares}\end{align} 
 %The estimator $\hat{\beta}$ is unbiased, \emph{i.e.}, $\expt{\hat{\beta}} = \beta$ (where the expectation is over the noise variables $\varepsilon_i$). Furthermore, $\hat{\beta}$ is a multidimensional normal random variable with mean $\beta$ and covariance matrix $(X_S\T{X_S})^{-1}$. 
 
-Note that the estimator $\hat{\beta}$ is a linear map of $y_S$; as $y_S$ is a multidimensional normal r.v., so is $\hat{\beta}$ (the randomness coming from the noise terms $\varepsilon_i$). In particular, $\hat{\beta}$ has mean $\beta$ (\emph{i.e.}, it is an \emph{unbianced estimator}) and covariance $(\T{X_S}X_S)^{-1}$.
+Note that the estimator $\hat{\beta}$ is a linear map of $y_S$; as $y_S$ is
+a multidimensional normal r.v., so is $\hat{\beta}$ (the randomness coming from
+the noise terms $\varepsilon_i$). In particular, $\hat{\beta}$ has mean $\beta$
+(\emph{i.e.}, it is an \emph{unbiased estimator}) and covariance
+$(\T{X_S}X_S)^{-1}$.
 
 Let $V:2^\mathcal{N}\to\reals$ be a value function, quantifying how informative a set of experiments $S$ is in estimating $\beta$. The standard optimal experimental design problem amounts to finding a set $S$ that maximizes $V(S)$ subject to the constraint $|S|\leq k$. 
 
-A variety of different value functions are used in experimental design\cite{pukelsheim2006optimal}; almost all make use of the the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. A value functioned preferred because of its relationship to entropy is the \emph{$D$-optimality criterion}: %which yields the following optimization problem
+A variety of different value functions are used in experimental design\cite{pukelsheim2006optimal}; almost all make use of the covariance $(\T{X_S}X_S)^{-1}$ of the estimator $\hat{\beta}$. A value functioned preferred because of its relationship to entropy is the \emph{$D$-optimality criterion}: %which yields the following optimization problem
 \begin{align}
  V(S) &= \frac{1}{2}\log\det \T{X_S}X_S \label{dcrit} %\\
 \end{align}
-As $\hat{\beta}$ is a multidimensional normal random variable, the $D$-optimality criterion is equal (up to a costant) to the negative of the entropy of $\hat{\beta}$. 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 of its estimator.
+As $\hat{\beta}$ is a multidimensional normal random variable, the
+$D$-optimality criterion is equal (up to a constant) to the negative of the
+entropy of $\hat{\beta}$. 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 of its estimator.
 
 %As discussed in the next section, in this paper, we work with a modified measure of information function, namely 
 %\begin{align}
@@ -45,7 +53,7 @@ maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq
 B$. We write:
 \begin{equation}\label{eq:non-strategic}
     OPT(V,\mathcal{N}, B) = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid
-    \sum_{i\in S}\leq B\right\}
+    \sum_{i\in S}c_i\leq B\right\}
 \end{equation}
 the best value we can reach under the budget constraint $B$ when selecting
 experiments from the set $\mathcal{N}$.
@@ -116,11 +124,11 @@ $\inf\{c_i: i\in f(c_i, c_{-i})\}$.
 \end{enumerate}
 \end{theorem}
 
-This theorem is particularly useful when designing a truthful mechanism: we
-can focus on designing a monotone allocation function. Then the mechanism will
-be truthful as long as we give each agent her threshold payment. Finally, it
-suffices to prove that the sum of threshold payments does not exceed the budget
-to ensure budget feasibility.
+This theorem is particularly useful when designing a budget feasible truthful
+mechanism: we can focus on designing a monotone allocation function. Then, the
+mechanism will be truthful as long as we give each agent her threshold payment.
+Finally, it suffices to prove that the sum of threshold payments does not
+exceed the budget to ensure budget feasibility.
 
 \begin{comment}
 \subsection{Experimental Design}
-- 
cgit v1.2.3-70-g09d2

