From 385334421230a9a4f7422817cc2fae224fd561da Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Thu, 4 Jul 2013 18:53:24 -0700 Subject: wording, proof, algo --- appendix.tex | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'appendix.tex') diff --git a/appendix.tex b/appendix.tex index 682fce2..bf163b4 100644 --- a/appendix.tex +++ b/appendix.tex @@ -476,12 +476,12 @@ Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed \section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} -We now present the proof of Theorem~\ref{thm:main}. $\delta$-truthfulness and -individual rationality follow from $\delta$-monotonicity and threshold -payments. $\delta$-monotonicity and budget feasibility follow the same steps as the -analysis of \citeN{chen}; for the sake of completeness, we restate their proof -here. +We now present the proof of Theorem~\ref{thm:main}. We use the notation $OPT_{-i^*}$ to denote the optimal value of \EDP{} when the maximum value element $i^*$ is excluded. We also use $OPT'_{-i^*}$ the approximation computed by the $\delta$-decreasing, $\epsilon$-accurate approximation of $L^*_{c_{-i^*}}$, as defined in Algorithm~\ref{mechanism}. +The properties of $\delta$-truthfulness and +individual rationality follow from $\delta$-monotonicity and threshold +payments. $\delta$-monotonicity and budget feasibility follow similar steps as the +analysis of \citeN{chen}, adapted to account for $\delta$-monotonicity: \begin{lemma}\label{lemma:monotone} Our mechanism for \EDP{} is $\delta$-monotone and budget feasible. \end{lemma} -- cgit v1.2.3-70-g09d2