1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsthm,amsfonts}
\usepackage{comment}
\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]}
\newcommand{\norm}[1]{\lVert#1\rVert}
\newcommand{\tr}[1]{#1^*}
\newcommand{\ip}[2]{\langle #1, #2 \rangle}
\newcommand{\mse}{\mathop{\mathrm{MSE}}}
\newcommand{\trace}{\mathop{\mathrm{tr}}}
\begin{document}
\section{Problem}
\begin{itemize}
\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}
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}
X_i = P + N_i
\end{displaymath}
where the $N_i$ are pairwise independent and also independent from $H$.
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.
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}
|
