diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 10 |
1 files changed, 5 insertions, 5 deletions
@@ -57,7 +57,7 @@ To obtain this result, we use the following modified version of Myerson's theore %variant of Myerson's theorem. \begin{lemma}\label{thm:myerson-variant} -\sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is + A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is $\delta$-truthful if: (a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq c_i-\delta$, for any @@ -65,11 +65,8 @@ fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i, c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$. \end{lemma} -\fussy - -We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}: +Lemma~\ref{thm:myerson-variant} allow us to incorporate our relaxation in the above framework, yielding the following theorem: \begin{theorem}\label{thm:main} - \sloppy For any $\delta>0$, and any $\epsilon>0$, there exists a $\delta$-truthful, individually rational and budget feasible mechanim for \EDP{} that runs in time $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$ @@ -82,6 +79,7 @@ We can now state our main result, which is proved in Appendix~\ref{sec:proofofma \simeq 12.98V(S^*) + \varepsilon.$ % \end{align*} \end{theorem} +The proof of the theorem, as well as our proposed mechanism, can be found in Appendix~\ref{sec:proofofmainthm}. In addition, we prove the following simple lower bound, proved in Appendix~\ref{proofoflowerbound}. \begin{theorem}\label{thm:lowerbound} @@ -89,3 +87,5 @@ There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. \end{theorem} + + |