Add proof of the monotonicity

1 files changed, 33 insertions, 0 deletions

diff --git a/proof.tex b/proof.tex
index c43e5b5..bc57ca0 100644
--- a/proof.tex
+++ b/proof.tex
@@ -35,6 +35,9 @@
             \forall x\in\mathbf{R}^d,\quad x^*Ax \leq x^*Bx 
         \end{displaymath}
         That is, iff $B-A$ is symmetric semi-definite positive.
+    \item Let us recall this property of the ordered defined above: if $A$ and
+        $B$ are two symmetric definite positive matrices such that $A\leq B$,
+        then $A^{-1}\leq B^{-1}$.
 \end{itemize}
 
 \subsection{Data model}
@@ -451,6 +454,36 @@ in the theorem.
 The mechanism is monotone.
 \end{lemma}
 
+\begin{proof}
+    We assume by contradiction that there exists a user $i$ that has been
+    selected by the mechanism and that would not be selected had he reported
+    a cost $c_i'\leq c_i$ (all the other costs staying the same).
+
+    If $i\neq i^*$ and $i$ has been selected, then we are in the case where
+    $L(x^*) \geq C V(i^*)$ and $i$ was included in the result set by the greedy
+    part of the mechanism. By reporting a cost $c_i'\leq c_i$, using the
+    submodularity of $V$, we see that $i$ will satisfy the greedy selection
+    rule:
+    \begin{displaymath}
+        i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\})
+        - V(S)}{c_j}
+    \end{displaymath}
+    in an earlier iteration of the greedy heuristic. Let us denote by $S_i$
+    (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$
+    (resp. $c_i'$). We have $S_i'\subset S_i$. Moreover:
+    \begin{align*}
+        c_i' & \leq c_i \leq
+        \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})}\\
+        & \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})}
+    \end{align*}
+    Hence $i$ will still be included in the result set.
+
+    If $i = i^*$, $i$ is included iff $L(x^*) \leq C V(i^*)$. Reporting $c_i'$
+    instead of $c_i$ does not change the value $V(i^*)$ nor $L(x^*)$ (which is
+    computed over $\mathcal{N}\setminus\{i^*\}$). Thus $i$ is still included by
+    reporting a different cost.
+\end{proof}
+
 \begin{lemma}
 The mechanism is budget feasible.
 \end{lemma}