From 64806a3659109cf595fe3347cc49522c8f536660 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Wed, 15 Aug 2012 18:23:41 -0700
Subject: Notes improvement

---
 notes2.tex | 149 +++++++++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 130 insertions(+), 19 deletions(-)

(limited to 'notes2.tex')

diff --git a/notes2.tex b/notes2.tex
index 51d50ba..92eabb5 100644
--- a/notes2.tex
+++ b/notes2.tex
@@ -5,6 +5,7 @@
 \newtheorem{lemma}{Lemma}
 \newtheorem{fact}{Fact}
 \newtheorem{example}{Example}
+\newtheorem{prop}{Proposition}
 \newcommand{\var}{\mathop{\mathrm{Var}}}
 \newcommand{\condexp}[2]{\mathop{\mathbb{E}}\left[#1|#2\right]}
 \newcommand{\expt}[1]{\mathop{\mathbb{E}}\left[#1\right]}
@@ -18,34 +19,144 @@
 \section{Problem}
 
 \begin{itemize}
-\item  $D = (x_i)_{1\leq i\leq n}$
-\item $(x_i)_{1\leq i\leq n}$ sampled in an i.i.d fashion from $\mu$
+\item  database $D = (X_i)_{1\leq i\leq n}$
+\item $(X_i)_{1\leq i\leq n}\in\big(\mathbf{R^d}\big)^n$ sampled in an i.i.d
+    fashion from the probability distribution $\mu$
 \end{itemize}
 
-There is a function $F$ and you are interested in estimating the value
-$F(\mu)$. We assume that you have an estimation scheme $\tilde{F}$,
-which given a set of data points $S$ returns an estimation
-$\tilde{F}(S)$ which is optimal in some sense. Your also given a
-revenue function $R$ which is a decreasing function of the estimation
-error. Then the value $V$ of the databse is defined by:
+We assume that there is a common variable $P$ which is the underlying
+phenomenon that we are interesting in, and all the variables in the database,
+are noisy realisations of this phenomenon:
 \begin{displaymath}
-  V(D) = \max_{S\subseteq D} R\left(| F(\mu) - \tilde{F} |\right)
+    X_i = P + N_i
 \end{displaymath}
+where the $N_i$ are pairwise independent and also independent from $H$.
 
-\begin{example}
-  
-\end{example}
 
-\begin{fact}
+We are interested in defining the $\emph{value}$ of a subset $S$ of the
+database $D$. The approaches to such a definition can be classified in two main
+families:
+\begin{itemize}
+    \item \emph{Information theoretic:} We use the entropy of $P$ as a measure
+        of the uncertainty. Then the value of a subset $S$ is the decrease of
+        entropy induced by revealing it:
+        \begin{displaymath}
+            V(S) = H(P) - H(P\,|\,S) 
+        \end{displaymath}
+    \item \emph{Statistical:} in this case you are trying to estimate the
+        phenomenon. The variance of the estimation is used as a measure of
+        the uncertainty. The value of a set $S$ can be defined as the average
+        reduction of the variance over all the points in the database once you
+        observe $S$:
+        \begin{displaymath}
+            V(S) = \frac{1}{|D|}\sum_{x\in D} \sigma_x^2 - \sigma_{x|A}^2
+        \end{displaymath}
+\end{itemize}
+
+Once you have defined a notion of value, there are several problems you can
+address:
+\begin{enumerate}
+    \item \emph{budget auctions:} the points in the database are associated
+        with users. Each user $i$ has a cost $c_i$ for revealing his data. You
+        are given a budget $B$ and you want to select a subset $S$ of users and
+        a payment scheme which is truthful. The value of the subset
+        $S$ should be as big as possible with the constraint that the payments
+        should stay within budget.
+    \item \emph{value sharing:} the goal is to find a value sharing method to
+        split the whole value of a subset $S$ among its participants.
+    \item \emph{k-best auctions:} this one is very similar to \emph{budget
+        auctions}, but instead of having a budget constraint, the constraint is
+        on the number of people in the subset $S$.
+\end{enumerate}
+
+These problems have already been studied, and optimal or near-optimal solution
+are already known when the value function is submodular. Fortunately, it can be
+shown that the information theoretic value defined above is submodular.
+
+\section{Submodularity}
+
+In this section, we will consider that we are given a \emph{universe} set $U$.
+A set function $f$ is a function defined on the power set of $U$, $\mathfrak{P}(U)$.
+
+A set function $f$ defined on $\mathfrak{P}(U)$ will be said \emph{increasing} if
+it is increasing with regards to inclusion, that is:
+
+\begin{displaymath}
+  \forall\,S\subseteq T,\quad f(S)\leq f(T)
+\end{displaymath}
+
+A \emph{decreasing} function on $\mathfrak{P}(U)$ is defined similarly.
+
+A set function $f$ defined on $\mathfrak{P}(U)$ is said to be
+\emph{submodular} if it verifies the diminishing returns property, that is,
+the marginal increments when adding a point to a set, is a set decreasing
+function. More formally, for any point $x$ in $U$, we can define the marginal
+increment of $f$ regarding $x$, it is the set function defined as:
+\begin{displaymath}
+    \Delta_x f(S) = f(S\cup\{x\}) - f(S)
+\end{displaymath}
+Then, $f$ is \emph{submodular} iff. for all $x$ in $U$, $\Delta_x f$ is a set
+decreasing function.
 
-  \begin{itemize}
-  \item If $R$ is decreasing then $V$ is increasing in the size of $D$.
-  \item If $R$ is concave then $V$ is supermodular.
-  \end{itemize}
-\end{fact}
+Similarly, a \emph{supermodular} is a function whose marginal increments are set
+increasing functions.
+\begin{prop}
+  Let $R:\mathbf{R}\rightarrow \mathbf{R}$ be a decreasing concave function and
+  $f:\mathfrak{P}(U)\rightarrow\mathbf{R}$ be a decreasing submodular function,
+  then the composed function $R\circ f$ is increasing and supermodular.
+\end{prop}
 
 \begin{proof}
+  The increasingness of $R\circ f$ follows immediately from the decreasingness
+  of $R$ and $f$.
+  
+  For the supermodularity, let $S$ and $T$ be two sets such that $S\subseteq
+  T$. By decreasingness of $f$, we have:
+  \begin{displaymath}
+    \forall\,V,\quad f(T)\leq f(S)\quad\mathrm{and}\quad f(T\cup V)\leq f(S\cup V)
+  \end{displaymath}
+  
+  Thus, by concavity of $R$:
+  \begin{displaymath}\label{eq:base}
+    \forall\,V,\quad\frac{R\big(f(S)\big)-R\big(f(S\cup V)\big)}{f(S)-f(S\cup V)}
+    \leq\frac{R\big(f(T)\big)-R\big(f(T\cup V)\big)}{f(T)-f(T\cup V)}
+  \end{displaymath}
   
+  $f$ is decreasing, so multiplying this last inequality by
+  $f(S)-f(S\cup V)$ and $f(T)-f(T\cup V)$ yields:
+  \begin{multline}
+    \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(T)-f(T\cup V)\big)\\
+    \leq \Big(R\big(f(T)\big)-R\big(f(T\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)
+  \end{multline}
+
+  $f$ is submodular, so:
+  \begin{displaymath}
+    f(T\cup V)-f(T)\leq f(S\cup V) - f(S)
+  \end{displaymath}
+  
+  $R\circ f$ is increasing, so:
+  \begin{displaymath}
+    R\big(f(S)\big)-R\big(f(S\cup V)\big)\leq 0
+  \end{displaymath}
+
+  By combining the two previous inequalities, we get:
+    \begin{multline*}
+    \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)\\
+    \leq \Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(T)-f(T\cup V)\big)
+  \end{multline*}
+
+  Injecting this last inequality into \eqref{eq:base} gives:
+  \begin{multline*}
+    \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)\\
+    \leq \Big(R\big(f(T)\big)-R\big(f(T\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)
+  \end{multline*}
+
+  Dividing left and right by $f(S)-f(S\cup V)$ yields:
+  \begin{displaymath}
+    \forall V,\quad R\big(f(S)\big)-R\big(f(S\cup V)\big)
+    \leq R\big(f(T)\big)-R\big(f(T\cup V)\big)
+  \end{displaymath}
+  which is exactly the supermodularity of $R\circ f$.
 \end{proof}
 
-\end{document}
\ No newline at end of file
+\end{document}
-- 
cgit v1.2.3-70-g09d2

