diff options
| -rw-r--r-- | appendix.tex | 5 | ||||
| -rw-r--r-- | main.tex | 12 | ||||
| -rw-r--r-- | myerson.tex | 18 | ||||
| -rw-r--r-- | paper.tex | 7 |
4 files changed, 20 insertions, 22 deletions
diff --git a/appendix.tex b/appendix.tex index 0f6e6b4..f9564c3 100644 --- a/appendix.tex +++ b/appendix.tex @@ -513,7 +513,8 @@ Formally, there must exist some $\alpha\geq 1$ should be computable in time polynomial in various parameters. %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$? Needed to say something in general, but not in our case where the value function can be computed in polynomial time}. \end{itemize} - +\section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson} +\input{myerson} \section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} \begin{algorithm}[!t] @@ -719,7 +720,7 @@ Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2} gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed -\section{Proof of Theorem \ref{thm:lowerbound}} +\section{Proof of Theorem \ref{thm:lowerbound}}\label{proofoflowerbound} Suppose, for contradiction, that such a mechanism exists. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ @@ -70,13 +70,11 @@ c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}: \begin{theorem}\label{thm:main} \sloppy - For any $\delta>0$ the allocation described in Algorithm~\ref{mechanism}, - along with threshold payments, is $\delta$-truthful, individually rational - and budget feasible. Furthermore, there exists an absolute constant $C$ - such that, for any $\varepsilon>0$, the mechanism runs in time + 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)$ and returns - a set $S^*$ such that: + a set $S^*$ such that % \begin{align*} $ OPT \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+ @@ -84,9 +82,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 value of the constant $C$ is given by \eqref{eq:constant} in -Appendix~\ref{sec:proofofmainthm}. -In addition, we prove the following simple lower bound. +In addition, we prove the following simple lower bound, proved in Appendix~\ref{proofoflowerbound}. \begin{theorem}\label{thm:lowerbound} There is no $2$-approximate, truthful, budget feasible, individually rational diff --git a/myerson.tex b/myerson.tex index bcfedc4..8c80cf6 100644 --- a/myerson.tex +++ b/myerson.tex @@ -10,20 +10,22 @@ other users: We distinguish four cases depending on the value of $s_i(c_i, c_{-i})$ and $s_i'(c_i', c_{-i})$. -Since the mechanism is normalized, if $s_i(c_i, c_{-i})= s_i(c_i', c_{-i})=0$, +\begin{enumerate} +\item $s_i(c_i, c_{-i})= s_i(c_i', c_{-i})=0$. +Since the mechanism is normalized we have $p_i(c_i, c_{-i}) = p_i(c_i', c_{-i})= 0$ and \eqref{eq:local-foobar} is true. - +\item $s_i(c_i', c_{-i}) = s_i(c_i, c_{-i}) = 1$. Note that $i$ is paid her threshold payment when allocated, and since this payment does not depend on $i$'s reported cost, \eqref{eq:local-foobar} is true -(and is in fact an equality) when $s_i(c_i', c_{-i}) = s_i(c_i, c_{-i}) = 1$. - -If $s_i(c_i', c_{-i}) = 0$ and $s_i(c_i, c_{-i}) = 1$, we have $p_i(c_i', +(and is in fact an equality). +\item $s_i(c_i', c_{-i}) = 0$ and $s_i(c_i, c_{-i}) = 1$. + We then have $p_i(c_i', c_{-i}) = 0$ by normalization and \eqref{eq:local-foobar} follows from individual rationality. - -Finally, let us assume that $s_i(c_i', c_{-i}) = 1$ and $s_i(c_i, c_{-i}) = 0$. +\item $s_i(c_i', c_{-i}) = 1$ and $s_i(c_i, c_{-i}) = 0$. By $\delta$-decreasingness of $s_i$, $c_i \geq c_i'+\delta$, and $s_i(c_i, c_{-i}) = 0$ implies that $i$'s threshold payment is less than $c_i$, \emph{i.e.} $p_i(c_i', c_{-i}) \leq c_i$. This last inequality is equivalent to -\eqref{eq:local-foobar} in this final case. +\eqref{eq:local-foobar} in this final case. \qed +\end{enumerate} @@ -41,11 +41,10 @@ \bibliography{notes} \appendix \input{appendix} -\section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson} -\input{myerson} -\section{Non-Truthfulness of the Maximum Operator}\label{sec:non-monotonicity} -\input{counterexample} \section{Extensions}\label{sec:ext} \input{general} +\section{Non-Truthfulness of the Maximum Operator}\label{sec:non-monotonicity} +\input{counterexample} + \end{document} |