From 460f799b52b7a4679df9eb843ec22d98b0283dcb Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 30 Oct 2012 19:58:33 +0100
Subject: Proof of the budget feasibility

---
 main.tex | 23 +++++++++++++++++++++--
 1 file changed, 21 insertions(+), 2 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index b089dcc..0c2b633 100644
--- a/main.tex
+++ b/main.tex
@@ -151,10 +151,29 @@ The mechanism is monotone.
 The mechanism is budget feasible.
 \end{lemma}
 
-The proof is the same as in Chen and is given here for the sake of
-completeness.
 \begin{proof}
+Let us denote by $S_M$ the set selected by the greedy heuristic in the
+mechanism of Algorithm~\ref{mechanism}. Let $i\in S_M$, let us also denote by
+$S_i$ the solution set that was selected by the greedy heuristic before $i$ was
+added. Recall from \cite{chen} that the following holds for any submodular
+function: if the point $i$ was selected by the greedy heuristic, then:
+\begin{equation}\label{eq:budget}
+    c_i \leq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_M)} B
+\end{equation}
+
+Assume now that our mechanism selects point $i^*$. In this case, his payement
+his $B$ and the mechanism is budget-feasible.
+
+Otherwise, the mechanism selects the set $S_M$. In this case, \eqref{eq:budget}
+shows that the threshold payement of user $i$ is bounded by:
+\begin{displaymath}
+\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_M)} B
+\end{displaymath}
 
+Hence, the total payement is bounded by:
+\begin{displaymath}
+    \sum_{i\in S_M} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_M)} B \leq B
+\end{displaymath}
 \end{proof}
 
 The following lemma proves that the relaxation $L_\mathcal{N}$ that we are
-- 
cgit v1.2.3-70-g09d2