diff options
| -rw-r--r-- | appendix.tex | 57 | ||||
| -rw-r--r-- | main.tex | 61 | ||||
| -rw-r--r-- | paper.tex | 2 |
3 files changed, 61 insertions, 59 deletions
diff --git a/appendix.tex b/appendix.tex new file mode 100644 index 0000000..2010227 --- /dev/null +++ b/appendix.tex @@ -0,0 +1,57 @@ +\begin{lemma}\label{lemma:monotone} +The mechanism is monotone. +\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. + Suppose that when $i$ reports $c_i$, $L(\xi) \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. + %using the submodularity of $V$, we see that $i$ will satisfy the greedy + %selection rule: + %\begin{displaymath} + % i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\}) + % - V(S)}{c_j} + %\end{displaymath} + %in an earlier iteration of the greedy heuristic. + Denote by $S_i$ + (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$ + (resp. $c_i'$). We have $S_i'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have + \begin{align*} + c_i' & \leq c_i \leq + \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 $L(\xi)$, 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$. + Suppose now that when $i$ reports $c_i$, $L(\xi) < 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 + $L(\xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. +\end{proof} +\begin{lemma}\label{lemma:budget-feasibility} +The mechanism is budget feasible. +\end{lemma} +\begin{proof} +Suppose that $L(\xi) < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible. +Suppose that $L(\xi) \geq C V(i^*)$. +Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$, denote by +$S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. +%Chen \emph{et al.}~\cite{chen} show that, +Then for any submodular function $V$, and for all $i\in S_G$: +%the reported cost of an agent selected by the greedy heuristic, and holds for +%any submodular function $V$: +\begin{equation}\label{eq:budget} + \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0 +\end{equation} +In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result, +\eqref{eq:budget} +implies that the threshold payment of user $i$ is bounded by the above quantity. +%\begin{displaymath} +%\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} = B +%\end{displaymath} +Hence, the total payment is bounded by the telescopic sum: +\begin{displaymath} + \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qed +\end{displaymath} +\end{proof} + + @@ -282,72 +282,15 @@ Suppose, for contradiction, that such a mechanism exists. Consider two experimen We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual rationality follows from monotonicity and threshold payments. Monotonicity and -budget feasibility follow more or less from the analysis of Chen \emph{et al.} \cite{chen}; -we briefly restate the proofs below for the sake of completeness. +budget feasibility follow the same steps as the analysis of Chen \emph{et al.} \cite{chen}; + for the sake of completeness, we briefly restate the proofs in the Appendix. Our proof of the approximation ratio uses a bound on our concave relaxation $L$ (Lemma~\ref{lemma:relaxation}). This is our main technical contribution; the proof of this lemma can be found in Section~\ref{sec:relaxation}. -\begin{lemma}\label{lemma:monotone} -The mechanism is monotone. -\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. - Suppose that when $i$ reports $c_i$, $L(\xi) \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. - %using the submodularity of $V$, we see that $i$ will satisfy the greedy - %selection rule: - %\begin{displaymath} - % i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\}) - % - V(S)}{c_j} - %\end{displaymath} - %in an earlier iteration of the greedy heuristic. - Denote by $S_i$ - (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$ - (resp. $c_i'$). We have $S_i'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have - \begin{align*} - c_i' & \leq c_i \leq - \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 $L(\xi)$, 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$. - Suppose now that when $i$ reports $c_i$, $L(\xi) < 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 - $L(\xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. -\end{proof} -\begin{lemma}\label{lemma:budget-feasibility} -The mechanism is budget feasible. -\end{lemma} -\begin{proof} -Suppose that $L(\xi) < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible. -Suppose that $L(\xi) \geq C V(i^*)$. -Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$, denote by -$S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. -%Chen \emph{et al.}~\cite{chen} show that, -Then for any submodular function $V$, and for all $i\in S_G$: -%the reported cost of an agent selected by the greedy heuristic, and holds for -%any submodular function $V$: -\begin{equation}\label{eq:budget} - \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0 -\end{equation} -In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result, -\eqref{eq:budget} -implies that the threshold payment of user $i$ is bounded by the above quantity. -%\begin{displaymath} -%\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} = B -%\end{displaymath} -Hence, the total payment is bounded by the telescopic sum: -\begin{displaymath} - \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qed -\end{displaymath} -\end{proof} - \begin{lemma}\label{lemma:complexity} For any $\varepsilon > 0$, the complexity of the mechanism is $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. \end{lemma} - \begin{proof} The value function $V$ in \eqref{modified} can be computed in time $O(\text{poly}(n, d))$ and the mechanism only involves a linear @@ -43,4 +43,6 @@ \bibliographystyle{abbrv} \bibliography{notes} +\appendix +\input{appendix} \end{document} |