diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 43 |
1 files changed, 24 insertions, 19 deletions
diff --git a/appendix.tex b/appendix.tex index bf163b4..a162a4f 100644 --- a/appendix.tex +++ b/appendix.tex @@ -253,14 +253,17 @@ Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed %For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate %approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$. %\end{lemma} -\note{THIBAUT: ARE THE COSTS BELOW DIVIDED BY B? CAN YOU EITHER RENAME THEM OR CARRY THE B AROUND AS APPROPRIATE?} - We proceed by showing that the optimal value of \eqref{eq:perturbed-primal} is close to the optimal value of \eqref{eq:primal} (Lemma~\ref{lemma:proximity}) while being well-behaved with respect to changes of the cost (Lemma~\ref{lemma:monotonicity}). These lemmas together imply Proposition~\ref{prop:monotonicity}. +Note that the choice of $\alpha$ given in Algorithm~\ref{alg:monotone} implies +that $\alpha<\frac{1}{n}$. This in turn implies that the feasible set +$\mathcal{D}_{c, \alpha}$ of \eqref{eq:perturbed-primal} is non-empty: it +contains the strictly feasible point $\lambda=(\frac{1}{n},\ldots,\frac{1}{n})$. + \begin{lemma}\label{lemma:derivative-bounds} Let $\partial_i L(\lambda)$ denote the $i$-th derivative of $L$, for $i\in\{1,\ldots, n\}$, then: \begin{displaymath} @@ -312,7 +315,7 @@ Let us introduce the Lagrangian of problem \eqref{eq:perturbed-primal}: \begin{displaymath} \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi) \defeq L(\lambda) - + \T{\mu}(\lambda-\alpha\mathbf{1}) + \T{\nu}(\mathbf{1}-\lambda) + \xi(1-\T{c}\lambda) + + \T{\mu}(\lambda-\alpha\mathbf{1}) + \T{\nu}(\mathbf{1}-\lambda) + \xi(B-\T{c}\lambda) \end{displaymath} so that: \begin{displaymath} @@ -371,23 +374,23 @@ In particular, $|L^*_c - L^*_{c,\alpha}| \leq \alpha n^2$. Let us first assume that $|M| = 0$, then $\T{\mathbf{1}}\mu^*=0$ and the lemma follows. We will now assume that $|M|\geq 1$. In this case $\T{c}\lambda^* - = 1$, otherwise we could increase the coordinates of $\lambda^*$ in $M$, + = B$, otherwise we could increase the coordinates of $\lambda^*$ in $M$, which would increase the value of the objective function and contradict the optimality of $\lambda^*$. Note also, that $|M|\leq n-1$, otherwise, since - $\alpha< \frac{1}{n}$, we would have $\T{c}\lambda^*\ < 1$, which again + $\alpha< \frac{1}{n}$, we would have $\T{c}\lambda^*\ < B$, which again contradicts the optimality of $\lambda^*$. Let us write: \begin{displaymath} - 1 = \T{c}\lambda^* = \alpha\sum_{i\in M}c_i + \sum_{i\in \bar{M}}\lambda_i^*c_i - \leq \alpha |M| + (n-|M|)\max_{i\in \bar{M}} c_i + B = \T{c}\lambda^* = \alpha\sum_{i\in M}c_i + \sum_{i\in \bar{M}}\lambda_i^*c_i + \leq \alpha |M|B + (n-|M|)\max_{i\in \bar{M}} c_i \end{displaymath} That is: \begin{equation}\label{local-2} - \max_{i\in\bar{M}} c_i \geq \frac{1 - |M|\alpha}{n-|M|}> \frac{1}{n} + \max_{i\in\bar{M}} c_i \geq \frac{B - B|M|\alpha}{n-|M|}> \frac{B}{n} \end{equation} where the last inequality uses again that $\alpha<\frac{1}{n}$. From the KKT conditions, we see that for $i\in M$, $\nu_i^* = 0$ and: \begin{equation}\label{local-3} - \mu_i^* = \xi^*c_i - \partial_i L(\lambda^*)\leq \xi^*c_i\leq \xi^* + \mu_i^* = \xi^*c_i - \partial_i L(\lambda^*)\leq \xi^*c_i\leq \xi^*B \end{equation} since $\partial_i L(\lambda^*)\geq 0$ and $c_i\leq 1$. @@ -400,7 +403,7 @@ In particular, $|L^*_c - L^*_{c,\alpha}| \leq \alpha n^2$. Combining \eqref{local-2}, \eqref{local-3} and \eqref{local-4}, we get that: \begin{displaymath} - \sum_{i\in M}\mu_i^* \leq |M|\xi^* \leq n\xi^*\leq \frac{n}{\max_{i\in\bar{M}} c_i} \leq n^2 + \sum_{i\in M}\mu_i^* \leq |M|\xi^*B \leq n\xi^*B\leq \frac{nB}{\max_{i\in\bar{M}} c_i} \leq n^2 \end{displaymath} This implies that: @@ -413,7 +416,7 @@ In particular, $|L^*_c - L^*_{c,\alpha}| \leq \alpha n^2$. \begin{lemma}\label{lemma:monotonicity} If $c'$ = $(c_i', c_{-i})$, with $c_i'\leq c_i - \delta$, we have: \begin{displaymath} - L^*_{c',\alpha} \geq L^*_{c,\alpha} + \frac{\alpha\delta b}{2^n} + L^*_{c',\alpha} \geq L^*_{c,\alpha} + \frac{\alpha\delta b}{2^nB} \end{displaymath} \end{lemma} @@ -437,7 +440,9 @@ In particular, $|L^*_c - L^*_{c,\alpha}| \leq \alpha n^2$. \begin{displaymath} \xi^* = \inf_{i:\lambda^{'*}_i>\alpha} \frac{\T{x_i}S(\lambda^{'*})^{-1}x_i}{c_i'} \end{displaymath} - with $\lambda^{'*}$ optimal for $(P_{c', \alpha})$. Since $c_i'\leq 1$, using Lemma~\ref{lemma:derivative-bounds}, we get that $\xi^*\geq \frac{b}{2^n}$, which concludes the proof. + with $\lambda^{'*}$ optimal for $(P_{c', \alpha})$. Since $c_i'\leq B$, + using Lemma~\ref{lemma:derivative-bounds}, we get that $\xi^*\geq + \frac{b}{2^nB}$, which concludes the proof. \end{proof} %\subsection*{End of the proof of Proposition~\ref{prop:monotonicity}} @@ -448,15 +453,15 @@ Algorithm~\ref{alg:monotone}. \item using Lemma~\ref{lemma:proximity}: \begin{displaymath} |\hat{L}^*_{c,\alpha} - L^*_c| \leq |\hat{L}^*_{c,\alpha} - L^*_{c,\alpha}| + |L^*_{c,\alpha} - L^*_c| - \leq \alpha\delta + \alpha n^2 = \varepsilon + \leq \frac{\alpha\delta}{B} + \alpha n^2 = \varepsilon \end{displaymath} which proves the $\varepsilon$-accuracy. \item for the $\delta$-decreasingness, let $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, then: \begin{displaymath} - \hat{L}^*_{c',\alpha} \geq L^*_{c',\alpha} - \frac{\alpha\delta b}{2^{n+1}} - \geq L^*_{c,\alpha} + \frac{\alpha\delta b}{2^{n+1}} + \hat{L}^*_{c',\alpha} \geq L^*_{c',\alpha} - \frac{\alpha\delta b}{2^{n+1}B} + \geq L^*_{c,\alpha} + \frac{\alpha\delta b}{2^{n+1}B} \geq \hat{L}^*_{c,\alpha} \end{displaymath} where the first and last inequalities follow from the accuracy of the approximation, and @@ -464,12 +469,12 @@ the inner inequality follows from Lemma~\ref{lemma:monotonicity}. \item the accuracy of the approximation $\hat{L}^*_{c,\alpha}$ is: \begin{displaymath} - A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2)} + A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2B)} \end{displaymath} Note that: \begin{displaymath} - \log\log A^{-1} = O\bigg(\log\log\frac{1}{\varepsilon\delta b} + \log n\bigg) + \log\log A^{-1} = O\bigg(\log\log\frac{B}{\varepsilon\delta b} + \log n\bigg) \end{displaymath} Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed \end{enumerate} @@ -541,7 +546,7 @@ The complexity of the mechanism is given by the following lemma. \begin{lemma}[Complexity]\label{lemma:complexity} 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)$ + $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$ \end{lemma} \begin{proof} @@ -551,7 +556,7 @@ The complexity of the mechanism is given by the following lemma. 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 + $O(\text{poly}(n, d, \log\log \frac{B}{b\varepsilon\delta}))$. 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. \junk{ |