diff options
| -rw-r--r-- | main.tex | 12 |
1 files changed, 5 insertions, 7 deletions
@@ -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} |