Some typo fixes, lemmas for the mechanism properties

1 files changed, 25 insertions, 4 deletions

diff --git a/proof.tex b/proof.tex
index a26c191..b38d7e6 100644
--- a/proof.tex
+++ b/proof.tex
@@ -8,6 +8,7 @@
 \newtheorem{fact}{Fact}
 \newtheorem{example}{Example}
 \newtheorem{prop}{Proposition}
+\newtheorem{theorem}{Theorem}
 \newcommand{\var}{\mathop{\mathrm{Var}}}
 \newcommand{\condexp}[2]{\mathop{\mathbb{E}}\left[#1|#2\right]}
 \newcommand{\expt}[1]{\mathop{\mathbb{E}}\left[#1\right]}
@@ -172,8 +173,8 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is:
     \begin{multline*}
         \frac{c_i}{c_j}\mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}(S',\lambda)}\Big[
-            V(S'\cup\{i\})+f(S'\cup\{i\})\\
-        -V(S'\cup\{i,j\})-f(S')\Big]
+            V(S'\cup\{i\})+V(S'\cup\{i\})\\
+        -V(S'\cup\{i,j\})-V(S')\Big]
     \end{multline*}
     which is positive by submodularity of $V$. Hence, the maximum of
     $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is
@@ -335,10 +336,10 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \State $x^* \gets \argmax_{x\in[0,1]^n} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
                                     \,|\, c(x)\leq\frac{B}{2}\}$
         \Statex
-        \If{$L(x^*) < CV(\{i^*\})$}
+        \If{$L(x^*) < CV(i^*)$}
             \State \textbf{return} $\{i^*\}$
         \Else
-            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(\{j\})}{c_j}$
+            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
             \State $S \gets \emptyset$
             \While{$c_i\leq \frac{B}{2}\frac{V(S\cup\{i\})-V(S)}{V(S\cup\{i\})}$}
                 \State $S \gets S\cup\{i\}$
@@ -349,4 +350,24 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
         \EndIf
     \end{algorithmic}
 \end{algorithm}
+
+\begin{lemma}
+The mechanism is monotone.
+\end{lemma}
+
+\begin{lemma}
+The mechanism is budget feasible.
+\end{lemma}
+
+\begin{lemma}
+    Let us denote by $S_M$ the set returned by the mechanism. Then:
+    \begin{displaymath}
+        V(S_M) \geq C\cdot OPT(V, \mathcal{N}, B)
+    \end{displaymath}
+\end{lemma}
+
+\begin{theorem}
+    The mechanism is individually rational, truthful and has an approximation
+    ratio of
+\end{theorem}
 \end{document}