appendix

3 files changed, 61 insertions, 59 deletions

diff --git a/appendix.tex b/appendix.tex
new file mode 100644
index 0000000..2010227
--- /dev/null
+++ b/appendix.tex
@@ -0,0 +1,57 @@
+\begin{lemma}\label{lemma:monotone}
+The mechanism is monotone.
+\end{lemma}
+\begin{proof}
+    Consider an agent $i$ with cost $c_i$ that is
+    selected by the mechanism, and suppose that she reports
+    a cost $c_i'\leq c_i$ while all  other costs stay the same.
+    Suppose that when $i$ reports $c_i$, $L(\xi) \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$.
+     By reporting a cost $c_i'\leq c_i$, $i$ may be selected at an earlier iteration of the greedy algorithm.
+    %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.
+ 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'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have
+    \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*}
+    by the monotonicity and submodularity  of $V$. Hence  $i\in S_G'$. As $L(\xi)$,  is the optimal value of \eqref{relax} under relaxation $L$ when $i^*$ is excluded from $\mathcal{N}$, reducing the costs can only increase this value, so under $c'_i\leq c_i$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$.
+    Suppose now that when $i$ reports $c_i$, $L(\xi) < C V(i^*)$. Then $s_i(c_i,c_{-i})=1$ iff $i = i^*$. 
+    Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor
+    $L(\xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. 
+\end{proof}
+\begin{lemma}\label{lemma:budget-feasibility}
+The mechanism is budget feasible.
+\end{lemma}
+\begin{proof}
+Suppose that $L(\xi) < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible.
+Suppose  that $L(\xi) \geq C V(i^*)$. 
+Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$,  denote by
+$S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. 
+%Chen \emph{et al.}~\cite{chen} show that, 
+Then for any submodular function $V$, and for all $i\in S_G$:
+%the reported cost of an agent selected by the greedy heuristic, and holds for
+%any submodular function $V$:
+\begin{equation}\label{eq:budget}
+   \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0
+\end{equation}
+In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result,
+\eqref{eq:budget}
+implies that the threshold payment of user $i$ is bounded by the above quantity.
+%\begin{displaymath}
+%\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} =  B
+%\end{displaymath}
+Hence, the total payment is bounded by the telescopic sum:
+\begin{displaymath}
+    \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qed
+\end{displaymath}
+\end{proof}
+
+
diff --git a/main.tex b/main.tex
index f1eae87..57e38cf 100644
--- a/main.tex
+++ b/main.tex
@@ -282,72 +282,15 @@ Suppose, for contradiction, that such a mechanism exists. Consider two experimen
 
 We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual
 rationality follows from monotonicity and threshold payments.  Monotonicity and
-budget feasibility follow more or less from the analysis of Chen \emph{et al.} \cite{chen};
-we briefly restate the proofs below for the sake of completeness.
+budget feasibility follow the same steps as the analysis of Chen \emph{et al.} \cite{chen};
+ for the sake of completeness, we briefly restate the proofs in the Appendix.
  Our proof of the approximation ratio uses a bound on our concave relaxation
 $L$ (Lemma~\ref{lemma:relaxation}). This is our main technical
 contribution; the proof of this lemma can be found in Section~\ref{sec:relaxation}.
-\begin{lemma}\label{lemma:monotone}
-The mechanism is monotone.
-\end{lemma}
-\begin{proof}
-    Consider an agent $i$ with cost $c_i$ that is
-    selected by the mechanism, and suppose that she reports
-    a cost $c_i'\leq c_i$ while all  other costs stay the same.
-    Suppose that when $i$ reports $c_i$, $L(\xi) \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$.
-     By reporting a cost $c_i'\leq c_i$, $i$ may be selected at an earlier iteration of the greedy algorithm.
-    %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.
- 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'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have
-    \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*}
-    by the monotonicity and submodularity  of $V$. Hence  $i\in S_G'$. As $L(\xi)$,  is the optimal value of \eqref{relax} under relaxation $L$ when $i^*$ is excluded from $\mathcal{N}$, reducing the costs can only increase this value, so under $c'_i\leq c_i$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$.
-    Suppose now that when $i$ reports $c_i$, $L(\xi) < C V(i^*)$. Then $s_i(c_i,c_{-i})=1$ iff $i = i^*$. 
-    Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor
-    $L(\xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. 
-\end{proof}
-\begin{lemma}\label{lemma:budget-feasibility}
-The mechanism is budget feasible.
-\end{lemma}
-\begin{proof}
-Suppose that $L(\xi) < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible.
-Suppose  that $L(\xi) \geq C V(i^*)$. 
-Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$,  denote by
-$S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. 
-%Chen \emph{et al.}~\cite{chen} show that, 
-Then for any submodular function $V$, and for all $i\in S_G$:
-%the reported cost of an agent selected by the greedy heuristic, and holds for
-%any submodular function $V$:
-\begin{equation}\label{eq:budget}
-   \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0
-\end{equation}
-In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result,
-\eqref{eq:budget}
-implies that the threshold payment of user $i$ is bounded by the above quantity.
-%\begin{displaymath}
-%\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} =  B
-%\end{displaymath}
-Hence, the total payment is bounded by the telescopic sum:
-\begin{displaymath}
-    \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qed
-\end{displaymath}
-\end{proof}
-
 \begin{lemma}\label{lemma:complexity}
     For any $\varepsilon > 0$, the complexity of the mechanism  is
     $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
 \end{lemma}
-
 \begin{proof}
     The value function $V$ in \eqref{modified} can be computed in time
     $O(\text{poly}(n, d))$ and the mechanism only involves a linear
diff --git a/paper.tex b/paper.tex
index 1030960..b3ad102 100644
--- a/paper.tex
+++ b/paper.tex
@@ -43,4 +43,6 @@
 
 \bibliographystyle{abbrv}
 \bibliography{notes}
+\appendix
+\input{appendix}
 \end{document}