summaryrefslogtreecommitdiffstats
path: root/main.tex
diff options
context:
space:
mode:
authorStratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>2012-11-04 16:18:02 -0800
committerStratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>2012-11-04 16:18:02 -0800
commitb27a1e52745d710e78bfc7097496b35a70388629 (patch)
tree404a22f9654e979fc7750dd202d1fe0c499ba223 /main.tex
parent340d8855e7dd38e6c9fef2a8ea81f0418677343d (diff)
downloadrecommendation-b27a1e52745d710e78bfc7097496b35a70388629.tar.gz
proof intro
Diffstat (limited to 'main.tex')
-rw-r--r--main.tex12
1 files changed, 5 insertions, 7 deletions
diff --git a/main.tex b/main.tex
index 657454d..3d89d16 100644
--- a/main.tex
+++ b/main.tex
@@ -182,12 +182,10 @@ Suppose, for contradiction, that such a mechanism exists. Consider two experimen
%The proof of the properties of the mechanism is broken down into lemmas.
We now present the proof of Theorem~\ref{thm:main}.
-Monotonicity and budget feasibility follows from the analysis of Chen \emph{et al.}; we briefly restate the proofs for the sake of completeness.
-\cite{chen}. The proof of the approximation ratio is done in
-lemma~\ref{lemma:approx} and uses a bound on our concave relaxation
-$L_\mathcal{N}$ (lemma~\ref{lemma:relaxation}) which is our main technical
-contribution. The proof of this lemma is done in a dedicated section
-(\ref{sec:relaxation}).
+Monotonicity and budget feasibility follows from the analysis of Chen \emph{et al.} \cite{chen}; we briefly restate the proofs for the sake of completeness.
+ Our proof of the approximation ratio and uses a bound on our concave relaxation
+$L_\mathcal{N}$ (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.
@@ -342,7 +340,7 @@ This solution is:
Placing the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2}
gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
%\end{proof}
-\subsection{Proof of lemma \ref{lemma:relaxation}}\label{sec:relaxation}
+\subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation}
Since $L_\mathcal{N}$ is a relaxation of the value function $V$, we have:
\begin{displaymath}