From 7ff4a4d46dbd64cd8bc7c07d0c7f11f13779443c Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 10 Jun 2013 19:09:15 +0200 Subject: Moving our two main results to a section preceding the introduction of our mechanism --- appendix.tex | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'appendix.tex') diff --git a/appendix.tex b/appendix.tex index b1d35d6..53bc328 100644 --- a/appendix.tex +++ b/appendix.tex @@ -22,7 +22,8 @@ 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{relax} 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'$. 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$. 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. -- cgit v1.2.3-70-g09d2