Explain that we use threshold payments. Adapt the proof a little bit to take this into account

1 files changed, 26 insertions, 7 deletions

diff --git a/main.tex b/main.tex
index b4c1861..687d23f 100644
--- a/main.tex
+++ b/main.tex
@@ -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).