diff options
| -rw-r--r-- | appendix.tex | 17 | ||||
| -rw-r--r-- | main.tex | 2 | ||||
| -rw-r--r-- | paper.tex | 3 |
3 files changed, 12 insertions, 10 deletions
diff --git a/appendix.tex b/appendix.tex index 2010227..8e30586 100644 --- a/appendix.tex +++ b/appendix.tex @@ -1,5 +1,5 @@ \begin{lemma}\label{lemma:monotone} -The mechanism is monotone. +The mechanism is monotone and budget feasible. \end{lemma} \begin{proof} Consider an agent $i$ with cost $c_i$ that is @@ -25,13 +25,14 @@ The mechanism is monotone. 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. + $L(\xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone. +%\end{proof} +%\begin{lemma}\label{lemma:budget-feasibility} +%The mechanism is budget feasible. +%\end{lemma} +%\begin{proof} + +To show budget feasibility, 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$. @@ -283,7 +283,7 @@ 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 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. + for the sake of completeness, we restate their proof 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}. @@ -40,9 +40,10 @@ \input{general} %\section{Conclusion} %\input{conclusion} - +\begin{small} \bibliographystyle{abbrv} \bibliography{notes} +\end{small} \appendix \input{appendix} \end{document} |