Proof of the first conjecture

1 files changed, 24 insertions, 2 deletions

diff --git a/final/main.tex b/final/main.tex
index 6f751df..0258e07 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -523,10 +523,32 @@ extended, having made the appropriate changes, to the constrained case) as in th
 Lemma~6 from \cite{babaioff} yields the following version of the core
 decomposition lemma:
 
-\begin{conjecture}
+\begin{lemma}
         $\Rev(\hat{x}, D)\leq \Val(D^C_\emptyset) + \sum_A p_A\Rev(\hat{x}_A,
         D^T_A)$.
-\end{conjecture}
+\end{lemma}
+
+\begin{proof}
+    Similarly to the proof of Lemma 6 in \cite{babaioff}, we get:
+    \begin{displaymath}
+        \Rev(\hat{x}, D) \leq \sum_A p_A \Rev(\hat{x}_A, D_A)
+    \end{displaymath}
+    Using Corollary~\ref{cor}, we get that $\Rev(\hat{x}_A, D_A)
+    \leq \Val(D_A^C) + \Rev(\hat{x}_A, D_A^T)$. Hence:
+    \begin{align*}
+        \Rev(\hat{x}, D) &\leq \sum_A p_A\big(\Val(D_A^C) + \Rev(\hat{x}_A,
+        D_A^T) \big)\\
+        &= \sum_A p_A\Val(D_A^C) + \sum_A p_A \Rev(\hat{x}_A,
+        D_A)\\
+        &\leq \sum_A p_A\Val(D_{\emptyset}^C) + \sum_A p_A \Rev(\hat{x}_A,
+        D_A)\\
+        &= \Val(D_{\emptyset}^C) + \sum_A p_A \Rev(\hat{x}_A,
+        D_A)
+    \end{align*}
+    Where the second inequality used that $\Val(D_A^C)\leq
+    \Val(D_{\emptyset}^C)$ and where the last equality used $\sum_A p_A = 1$.
+\end{proof}
+
 
 However, if we keep pushing in this direction, it seems that the approach fails
 when trying to obtain the following: