From d158132a00b3c2a934f9c564a4900f64fa7118a7 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 5 Nov 2012 13:40:26 -0800
Subject: appendix and biblio fonts

---
 appendix.tex | 17 +++++++++--------
 main.tex     |  2 +-
 paper.tex    |  3 ++-
 3 files changed, 12 insertions(+), 10 deletions(-)

diff --git a/appendix.tex b/appendix.tex
index 2010227..8e30586 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -1,5 +1,5 @@
 \begin{lemma}\label{lemma:monotone}
-The mechanism is monotone.
+The mechanism is monotone and budget feasible.
 \end{lemma}
 \begin{proof}
     Consider an agent $i$ with cost $c_i$ that is
@@ -25,13 +25,14 @@ The mechanism is monotone.
     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.
+    $L(\xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone.
+%\end{proof}
+%\begin{lemma}\label{lemma:budget-feasibility}
+%The mechanism is budget feasible.
+%\end{lemma}
+%\begin{proof}
+
+To show budget feasibility, 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$. 
diff --git a/main.tex b/main.tex
index 57e38cf..8937f04 100644
--- a/main.tex
+++ b/main.tex
@@ -283,7 +283,7 @@ 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 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.
+ for the sake of completeness, we restate their proof 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}.
diff --git a/paper.tex b/paper.tex
index b3ad102..295d8d1 100644
--- a/paper.tex
+++ b/paper.tex
@@ -40,9 +40,10 @@
 \input{general}
 %\section{Conclusion}
 %\input{conclusion}
-
+\begin{small}
 \bibliographystyle{abbrv}
 \bibliography{notes}
+\end{small}
 \appendix
 \input{appendix}
 \end{document}
-- 
cgit v1.2.3-70-g09d2