diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 33 |
1 files changed, 26 insertions, 7 deletions
@@ -130,6 +130,7 @@ approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}). \begin{algorithm}[!t] \caption{Mechanism for \EDP{}}\label{mechanism} \begin{algorithmic}[1] + \State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$ \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$ \State $\xi \gets \argmax_{\lambda\in[0,1]^{n}} \{L_{\mathcal{N}\setminus\{i^*\}}(\lambda) \mid \sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$, with precision $\epsilon>0$ @@ -148,7 +149,18 @@ approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}). \EndIf \end{algorithmic} \end{algorithm} -The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. The constant $C$ is an absolute constant, that we determine in Section~\ref{sec:proofofmainthm} (see \eqref{eq:c}). +The resulting mechanism for \EDP{} is composed of (a) the allocation function +presented in Algorithm~\ref{mechanism}; the constant $C$ is an absolute +constant that we determine in Section~\ref{sec:proofofmainthm} +(see \eqref{eq:c}) (b) the payment function which pays each +allocated agent $i$ her threshold payment as described in Myerson's theorem +(see Theorem~\ref{thm:myerson}) and 0 to unallocated agents. In the case where +$\{i^*\}$ is the allocated set, her threshold payment is $B$ (she would be have +been dropped on line 1 of Algorithm~\ref{mechanism} had she reported a higher +cost). In the case where $S_G$ is the allocated set, threshold payments' +characterization from Singer \cite{singer-mechanisms} gives a formula to +effectively compute these payments. + We can now state our main result: \begin{theorem}\label{thm:main} There exists an absolute constant $C$ such that the mechanism described in Algorithm~\ref{mechanism} is truthful, individiually rational @@ -176,8 +188,10 @@ Suppose, for contradiction, that such a mechanism exists. Consider two experimen \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} \stratis{individual rationality???} %The proof of the properties of the mechanism is broken down into lemmas. -We now present the proof of Theorem~\ref{thm:main}. -Monotonicity and budget feasibility follows from the analysis of Chen \emph{et al.} \cite{chen}; we briefly restate the proofs for the sake of completeness. +We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual +rationality follows from monotonicity and threshold payments. Monotonicity and +budget feasibility follows from the analysis of Chen \emph{et al.} \cite{chen}; +we briefly restate the proofs for the sake of completeness. Our proof of the approximation ratio and uses a bound on our concave relaxation $L_\mathcal{N}$ (Lemma~\ref{lemma:relaxation}). This is our main technical contribution; the proof of this lemma can be found in Section~\ref{sec:relaxation}. @@ -236,7 +250,7 @@ Hence, the total payment is bounded by the telescopic sum: \end{proof} \begin{lemma}\label{lemma:complexity} - For any $\varepsilon > 0$, the complexity of algorithm~\ref{mechanism} is + For any $\varepsilon > 0$, the complexity of the mechanism is $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. \end{lemma} @@ -248,9 +262,14 @@ Hence, the total payment is bounded by the telescopic sum: The function $\log\det$ is concave and self-concordant (see \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be find to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$ of iterations of Newton's method. Each iteration can be - done in time $O(\text{poly}(n, d))$. Thus, line 2 of + done in time $O(\text{poly}(n, d))$. Thus, line 3 of Algorithm~\ref{mechanism} can be computed in time - $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. + $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. Hence the allocation + function's complexity is as stated. + + Using Singer's characterization of the threshold payments + \cite{singer-mechanisms}, one can verify that they can be computed in time + $O(\text{poly}(n, d))$. \end{proof} Finally, we prove the approximation ratio of the mechanism. We use the @@ -275,7 +294,7 @@ Using this lemma, we can complete the proof of Theorem~\ref{thm:main} by showing \leq \frac{14e\!-\!3 + \sqrt{160e^2\!-\!48e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound} \end{align} %\end{lemma} - To see this, let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity + To see this, let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 3 of algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L_{\mathcal{N}\setminus {i^*}}(x^*) \leq \tilde{L}+\varepsilon$ has been computed (lemma~\ref{lemma:complexity} states that this is computed in time within our complexity guarantee). |