diff options
| -rw-r--r-- | appendix.tex | 43 | ||||
| -rw-r--r-- | approximation.tex | 9 | ||||
| -rw-r--r-- | definitions.tex | 1 | ||||
| -rw-r--r-- | main.tex | 2 |
4 files changed, 31 insertions, 24 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{ diff --git a/approximation.tex b/approximation.tex index 1a4b44b..c306a75 100644 --- a/approximation.tex +++ b/approximation.tex @@ -183,9 +183,10 @@ Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concav \begin{algorithm}[t] \caption{}\label{alg:monotone} \begin{algorithmic}[1] - \Require{ $B\in \reals_+$,$c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ } - \State $\alpha \gets \min\left(\varepsilon B^{-1}(\delta+n^2)^{-1},\frac{1}{nB}\right) $ - \State Use the barrier method to solve \eqref{eq:perturbed-primal} with accuracy $\varepsilon'=\frac{1}{2^{n+1}}\alpha\delta b$; denote the output by $\hat{L}^*_{c,\alpha}$ + \Require{ $B\in \reals_+$, $c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ } + \State $\alpha \gets \varepsilon (\delta/B+n^2)^{-1}$ + \State Use the barrier method to solve \eqref{eq:perturbed-primal} with + accuracy $\varepsilon'=\frac{1}{2^{n+1}B}\alpha\delta b$; denote the output by $\hat{L}^*_{c,\alpha}$ \State \textbf{return} $\hat{L}^*_{c,\alpha}$ \end{algorithmic} \end{algorithm} @@ -195,7 +196,7 @@ Our construction of a $\delta$-decreasing, $\varepsilon$-accurate approximator o For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$, Algorithm~\ref{alg:monotone} computes a $\delta$-decreasing, $\varepsilon$-accurate approximation of $L^*_c$. The running time of the - algorithm is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$. \note{THIBAUT, IS THERE A BUDGET $B$ IN THE NUMERATOR OF THE LOGLOG TERM?} + algorithm is $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$. \end{proposition} We note that the the execution of the barrier method on the restricted set $\dom_{c,\alpha}$ is necessary. The algorithm's output when executed over the entire domain may not necessarily be $\delta$-decreasing, even when the approximation accuracy is small. This is because costs become saturated when the optimal $\lambda\in \dom_c$ lies at the boundary: increasing them has no effect on the objective. Forcing the optimization to happen ``off'' the boundary ensures that this does not occur, while taking $\alpha$ to be small ensures that this perturbation does not cost much in terms of approximation accuracy. diff --git a/definitions.tex b/definitions.tex index a719fce..7d30dcd 100644 --- a/definitions.tex +++ b/definitions.tex @@ -19,6 +19,7 @@ \newcommand{\tr}[1]{#1^*} \newcommand{\ip}[2]{\langle #1, #2 \rangle} \newcommand{\mse}{\mathop{\mathrm{MSE}}} +\renewcommand{\epsilon}{\varepsilon} \DeclareMathOperator{\trace}{tr} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} @@ -106,7 +106,7 @@ We can now state our main result, which is proved in Appendix~\ref{sec:proofofma along with threshold payments, is $\delta$-truthful, individually rational and budget feasible. Furthermore, there exists an absolute constant $C$ such that, for any $\varepsilon>0$, the mechanism runs in time - $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)$ and returns a set $S^*$ such that: % \begin{align*} |