diff options
Diffstat (limited to 'proofs.tex')
| -rw-r--r-- | proofs.tex | 43 |
1 files changed, 20 insertions, 23 deletions
@@ -1,26 +1,25 @@ \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} -We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual -rationality follow from monotonicity and threshold payments. Monotonicity and -budget feasibility follow the same steps as the analysis of \citeN{chen}; - for the sake of completeness, we restate their proof in the Appendix. +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 +in the Appendix. The complexity of the mechanism is given by the following lemma. \begin{lemma}[Complexity]\label{lemma:complexity} - For any $\varepsilon > 0$, the complexity of the mechanism is - $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. + For any $\varepsilon > 0$ and any $\delta>0$, the complexity of the mechanism is + $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$ \end{lemma} \begin{proof} The value function $V$ in \eqref{modified} can be computed in time $O(\text{poly}(n, d))$ and the mechanism only involves a linear number of queries to the function $V$. - The function $\log\det$ is concave and self-concordant (see - \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be found - to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$ of iterations of Newton's method. Each iteration can be - done in time $O(\text{poly}(n, d))$. Thus, line 3 of - Algorithm~\ref{mechanism} can be computed in time + + By Proposition~\ref{prop:monotonicity}, line 3 of Algorithm~\ref{mechanism} + can be computed in time $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. Hence the allocation function's complexity is as stated. %Payments can be easily computed in time $O(\text{poly}(n, d))$ as in prior work. @@ -55,28 +54,26 @@ OPT \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\! + \! \varepsilon . \end{equation} -To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to -$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume -that on line 3 of Algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that -$\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been -computed (Lemma~\ref{lemma:complexity} states that this is computed in time -within our complexity guarantee). +To see this, let $L^*_{-i^*}$ be the true maximum value of $L$ subject to +$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line +3 of Algorithm~\ref{mechanism}, we have +$L^*_{-i^*}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{-i^*}+\varepsilon$. -If the condition on line 3 of the algorithm holds, then +If the condition on line 4 of the algorithm holds, then \begin{displaymath} - V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq - \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C} + V(i^*) \geq \frac{1}{C}L^*_{-i^*}-\frac{\varepsilon}{C} \geq + \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}. \end{displaymath} -as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$, +Indeed, $L^*_{-i^*}\geq OPT_{-i^*}$ as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$, hence, \begin{equation}\label{eq:bound1} OPT\leq (1+C)V(i^*) + \varepsilon. \end{equation} -If the condition does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and +If the condition does not hold, by observing that $L^*_{-i^*}\leq L^*_c$ and applying Proposition~\ref{prop:relaxation}, we get \begin{displaymath} - V(i^*) \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C} + V(i^*)\leq \frac{1}{C}L^*_{-i^*} + \frac{\varepsilon}{C} \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}. \end{displaymath} Applying Lemma~\ref{lemma:greedy-bound}, |