diff options
| -rw-r--r-- | main.tex | 23 |
1 files changed, 12 insertions, 11 deletions
@@ -149,21 +149,22 @@ approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}). \EndIf \end{algorithmic} \end{algorithm} + 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 +presented in Algorithm~\ref{mechanism}, and (b) the payment function which pays each +allocated agent $i$ her threshold payment as described in Myerson's Theorem. The constant $C$ is an absolute +constant that determined in Section~\ref{sec:proofofmainthm} +(see \eqref{eq:c}). + 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. + 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 + The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individiually rational and budget feasible. Furthermore, for any $\varepsilon>0$, the mechanism has complexity $O\left(\text{poly}(n, d, \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that: @@ -180,13 +181,13 @@ In addition, we prove the following lower bound. \begin{theorem}\label{thm:lowerbound} There is no $2$-approximate, truthful, budget feasible, individionally rational mechanism for EDP. \end{theorem} -\stratis{move the proof as appropriate} +%\stratis{move the proof as appropriate} \begin{proof} 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]$ and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must be in the set selected by the mechanism, otherwise the ratio is unbounded, a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity it remains in the solution; by threshold payment, it is paid at least $B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility and individual rationality: hence, the selected set attains a value $\log2$, while the optimal value is $2\log 2$. \end{proof} \subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} -\stratis{individual rationality???} +%\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}. Truthfulness and individual rationality follows from monotonicity and threshold payments. Monotonicity and @@ -301,11 +302,11 @@ Using this lemma, we can complete the proof of Theorem~\ref{thm:main} by showing If the condition on line 3 of the algorithm holds, then: \begin{displaymath} V(i^*) \geq \frac{1}{C}L_{N\setminus \{i\}}(x^*)-\frac{\varepsilon}{C} \geq - \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B) -\frac{\varepsilon}{C} + \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i^*\}, B) -\frac{\varepsilon}{C} \end{displaymath} as $L$ is a fractional relaxation of $V$ on $\mathcal{N}\setminus \{i^*\}$. Also, \begin{displaymath} - OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i\}, B) + V(i^*) + OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i^*\}, B) + V(i^*) \end{displaymath} Hence: \begin{equation}\label{eq:bound1} |