diff options
| -rw-r--r-- | main.tex | 16 |
1 files changed, 5 insertions, 11 deletions
@@ -150,7 +150,6 @@ The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. Th \EndIf \end{algorithmic} \end{algorithm} - 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 @@ -164,7 +163,6 @@ We can now state our main result: & \simeq 19.68V(S^*) + \varepsilon \end{align*} \end{theorem} - %\stratis{Add lowerbound here too.} Note that this implies we construct a poly-time mechanism with accuracy arbitrarily close to 19.68, by taking $\varepsilon = \ldots$\stratis{fix me}. In addition, we prove the following lower bound. @@ -178,19 +176,15 @@ 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. 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}. - \begin{lemma}\label{lemma:monotone} The mechanism is monotone. \end{lemma} - \begin{proof} Consider an agent $i$ with cost $c_i$ that is selected by the mechanism, and suppose that she reports @@ -217,11 +211,9 @@ The mechanism is monotone. Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor $L_{\mathcal{N}\setminus \{i^*\}}(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_{\mathcal{N}\setminus\{i^*\}}(\xi) < C V(i^*)$. Then the mechanism selects $i^*$; as the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible. Suppose thus that $L_{\mathcal{N}\setminus\{i^*\}}(\xi) \geq C V(i^*)$. @@ -263,15 +255,17 @@ Hence, the total payment is bounded by the telescopic sum: \end{proof} Finally, we prove the approximation ratio of the mechanism. We use the -following lemma, which gives an approximation ratio of the function -$L_\mathcal{N}$. +following lemma, which establishes the optimal fractional relaxation +$L_\mathcal{N}$ is not too far from $OPT(V,\mathcal{N},B)$. \begin{lemma}\label{lemma:relaxation} %\begin{displaymath} $ OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B) + 2\max_{i\in\mathcal{N}}V(i)$ %\end{displaymath} \end{lemma} -Its proof is our main technical contribution, and can be found in Section \ref{sec:relaxation}. +Note that the lower bound $OPT(L_\mathcal{N}, B) \geq OPT(V,\mathcal{N},B) +$ also holds trivially, as $L_{\mathcal{N}}$ is a fractional relaxation of $V$ over $\mathcal{N}$. +The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}. Using this lemma, we can complete the proof of Theorem~\ref{thm:main} by showing that, %\begin{lemma}\label{lemma:approx} %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C %(e-1) -10e +2}\right)\right) |