Fixing issues related to cost nomalization

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{