diff options
| -rw-r--r-- | proof.tex | 49 |
1 files changed, 34 insertions, 15 deletions
@@ -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: |