diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 10 |
1 files changed, 5 insertions, 5 deletions
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} |