From 56df5c9afe236178aa864040bf809c2878926c33 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Thu, 25 Oct 2012 10:25:14 -0700
Subject: Add marginal contribution lemma

---
 proof.tex | 49 ++++++++++++++++++++++++++++++++++---------------
 1 file changed, 34 insertions(+), 15 deletions(-)

diff --git a/proof.tex b/proof.tex
index 5c9cb91..c43e5b5 100644
--- a/proof.tex
+++ b/proof.tex
@@ -64,22 +64,41 @@
 
 \subsection{Economics}
 
-\begin{itemize}
-    \item Value function: following the experiment design theory, the value of
-        data is the decrease of uncertainty about the model. Common measure of
-        uncertainty, the entropy. Thus, the value of a set $S$ of users is:
-        \begin{displaymath}
-            V(S) = \mathbb{H}(\beta) - \mathbb{H}(\beta|Y_S)
-        \end{displaymath}
-        where $Y_S = \{y_i,\,i\in S\}$ is the set of observations.
+Value function: following the experiment design theory, the value of
+data is the decrease of uncertainty about the model. Common measure of
+uncertainty, the entropy. Thus, the value of a set $S$ of users is:
+\begin{displaymath}
+    V(S) = \mathbb{H}(\beta) - \mathbb{H}(\beta|Y_S)
+\end{displaymath}
+where $Y_S = \{y_i,\,i\in S\}$ is the set of observations.
 
-        In our case (under Gaussian prior):
-        \begin{align*}
-            \forall S\subset\mathcal{N},\; V(S)
-            & = \frac{1}{2}\log\det\left(I_d
-                    + \mu\sum_{i\in S} x_ix_i^*\right)\\
-            & \defeq \frac{1}{2}\log\det A(S)
-        \end{align*}
+In our case (under Gaussian prior):
+\begin{align*}
+    \forall S\subset\mathcal{N},\; V(S)
+    & = \frac{1}{2}\log\det\left(I_d
+        + \mu\sum_{i\in S} x_ix_i^*\right)\\
+    & \defeq \frac{1}{2}\log\det A(S)
+\end{align*}
+
+\begin{lemma}[Marginal contribution]
+    \begin{displaymath}
+        \Delta_i V(S)\defeq V(S\cup\{i\}) - V(S) 
+        = \frac{1}{2}\log\left(1 + \mu x_i^*A(S)^{-1}x_i\right)
+    \end{displaymath}
+\end{lemma}
+
+\begin{proof}
+    We have:
+    \begin{align*}
+        V(S\cup\{i\}) & = \frac{1}{2}\log\det A(S\cup\{i\})\\
+        & = \frac{1}{2}\log\det\left(A(S) + \mu x_i x_i^*\right)\\
+        & = V(S) + \frac{1}{2}\log\det\left(I_d + \mu A(S)^{-1}x_i
+    x_i^*\right)\\
+        & = V(S) + \frac{1}{2}\log\left(1 + \mu x_i^* A(S)^{-1}x_i\right)
+    \end{align*}
+    where the last equality comes from Sylvester's determinant formula.
+\end{proof}
+\begin{itemize}
     \item each user $i$ has a cost $c_i$
     \item the auctioneer has a budget constraint $B$
     \item optimisation problem:
-- 
cgit v1.2.3-70-g09d2