diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 11 |
1 files changed, 6 insertions, 5 deletions
diff --git a/appendix.tex b/appendix.tex index 53bc328..2c83e04 100644 --- a/appendix.tex +++ b/appendix.tex @@ -1,12 +1,12 @@ \begin{lemma}\label{lemma:monotone} -Our mechanism for \EDP{} is monotone and budget feasible. +Our mechanism for \EDP{} is $\delta$-monotone and budget feasible. \end{lemma} \begin{proof} Consider an agent $i$ with cost $c_i$ that is selected by the mechanism, and suppose that she reports - a cost $c_i'\leq c_i$ while all other costs stay the same. + a cost $c_i'\leq c_i-\delta$ while all other costs stay the same. Suppose that when $i$ reports $c_i$, $OPT'_{-i^*} \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$. - By reporting a cost $c_i'\leq c_i$, $i$ may be selected at an earlier iteration of the greedy algorithm. + By reporting cost $c_i'$, $i$ may be selected at an earlier iteration of the greedy algorithm. %using the submodularity of $V$, we see that $i$ will satisfy the greedy %selection rule: %\begin{displaymath} @@ -22,8 +22,9 @@ Our mechanism for \EDP{} is monotone and budget feasible. \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})} \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})} \end{align*} - by the monotonicity and submodularity of $V$. Hence $i\in S_G'$. As - $OPT'_{-i^*}$, is the optimal value of \eqref{eq:primal} under relaxation $L$ when $i^*$ is excluded from $\mathcal{N}$, reducing the costs can only increase this value, so under $c'_i\leq c_i$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$. + by the monotonicity and submodularity of $V$. Hence $i\in S_G'$. By + $\delta$-decreasingness of + $OPT'_{-i^*}$, under $c'_i\leq c_i-\delta$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$. Suppose now that when $i$ reports $c_i$, $OPT'_{-i^*} < C V(i^*)$. Then $s_i(c_i,c_{-i})=1$ iff $i = i^*$. Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor $OPT'_{-i^*} \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone. |