Add notations, minor fixes

1 files changed, 24 insertions, 6 deletions

diff --git a/proof.tex b/proof.tex
index e907518..5c9cb91 100644
--- a/proof.tex
+++ b/proof.tex
@@ -22,6 +22,21 @@
 
 \section{Budget feasible mechanism}
 
+\subsection{Notations}
+
+\begin{itemize}
+    \item If $x\in\mathbf{R}^d$, $x^*$ will denote the transpose of vector $x$.
+        If $(x, y)\in\mathbf{R}^d\times\mathbf{R}^d$, $x^*y$ is the standard
+        inner product of $\mathbf{R}^d$.
+    \item We will often use the following order over symmetric matrices: if $A$
+        and $B$ are two $d\times d$ real symmetric matrices, we write that
+        $A\leq B$ iff:
+        \begin{displaymath}
+            \forall x\in\mathbf{R}^d,\quad x^*Ax \leq x^*Bx 
+        \end{displaymath}
+        That is, iff $B-A$ is symmetric semi-definite positive.
+\end{itemize}
+
 \subsection{Data model}
 \begin{itemize}
     \item set of $n$ users $\mathcal{N} = \{1,\ldots, n\}$
@@ -287,10 +302,12 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     
     Using the following inequalities:
     \begin{gather*}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \geq
-        P_\mathcal{N}^\lambda(S)\\
-        A(S)^{-1} \geq A(S\cup\{i\})^{-1}\\
-        P_\mathcal{N}^\lambda(S\cup\{i\})\geq P_\mathcal{N}^\lambda(S)
+        \forall S\subset\mathcal{N}\setminus\{i\},\quad
+        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq
+        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})\\
+        \forall S\subset\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) 
+        \geq P_\mathcal{N}^\lambda(S)\\
+        \forall S\subset\mathcal{N},\quad A(S)^{-1} \geq A(S\cup\{i\})^{-1}\\
     \end{gather*}
     we get:
     \begin{align*}
@@ -429,7 +446,8 @@ The mechanism is budget feasible.
 
     Then:
     \begin{displaymath}
-        V(S_M) \geq C_{\textrm{max}}\cdot OPT(V, \mathcal{N}, B)
+        OPT(V, \mathcal{N}, B) \leq
+        C_\text{max}\cdot V(S_M) 
     \end{displaymath}
 \end{lemma}
 
@@ -486,7 +504,7 @@ This equation has two solutions. Only one of those is such that:
 \begin{displaymath}
     C\cdot C_\mu(e-1) -5e  +1 \geq 0
 \end{displaymath}
-which is a needed in the proof of the previous lemma. Computing this solution,
+which is needed in the proof of the previous lemma. Computing this solution,
 we can state the main result of this section.
 
 \begin{theorem}